Java - data structures

P2

Suppose we want to create a method for the class BinaryTree that decides whether two trees have the same structure. Two trees t1 and t2 have the same structure if:

- If one has a left child, then both have left children and the left children are isomorphic, AND

- if one has a right child, then both have right children and the right children are isomorphic

The header of the method is:

public boolean isIsomorphic(BinaryTree otherTree)

Write this method, using a private recursive method of the same name.

BinaryTree.java

//package TreePackage; import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack ; // for Stack

public class BinaryTree { protected BinaryNode root; public BinaryTree() { root = null; } // end default constructor public BinaryTree(T rootData) { root = new BinaryNode(rootData); } // end constructor

public BinaryTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end constructor

public void setTree(T rootData) { root = new BinaryNode(rootData); } // end setTree public void setTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { privateSetTree(rootData, leftTree, rightTree); } // end setTree

private void privateSetTree(T rootData, BinaryTree leftTree, BinaryTree rightTree) { root = new BinaryNode(rootData);

if (leftTree != null) root.setLeftChild(leftTree.root); if (rightTree != null) root.setRightChild(rightTree.root); }

public T getRootData () { T rootData = null; if (root != null) rootData = root.getData(); return rootData; } public boolean isEmpty () { return root == null; } public void clear (){ root = null; } // getHeight and getNumberOfNodes call same functions in BinaryNode public int getHeight () { return root.getHeight (); } public int getNumberOfNodes () { return root.getNumberOfNodes (); } public void inorderTraversal() { Stack> nodeStack = new Stack>(); BinaryNode currentNode = root; while (!nodeStack.empty() || currentNode != null) { while(currentNode != null) { nodeStack.push(currentNode); currentNode = currentNode.getLeftChild(); } if(!nodeStack.empty()) { BinaryNode nextNode = nodeStack.pop(); System.out.println(nextNode.getData()); currentNode = nextNode.getRightChild(); } } } public Iterator getPreorderIterator() { return new PreorderIterator(); } public Iterator getInorderIterator() { return new InorderIterator(); } private class PreorderIterator implements Iterator { private Stack> nodeStack; public PreorderIterator() { nodeStack = new Stack>(); if (root != null) nodeStack.push(root); } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty(); } // end hasNext public T next() { BinaryNode nextNode; if (hasNext()) { nextNode = nodeStack.pop(); BinaryNode leftChild = nextNode.getLeftChild(); BinaryNode rightChild = nextNode.getRightChild(); // push into stack in reverse order of recursive calls if (rightChild != null) nodeStack.push(rightChild); if (leftChild != null) nodeStack.push(leftChild); } else { throw new NoSuchElementException(); } return nextNode.getData(); } // end next public void remove() { throw new UnsupportedOperationException(); } // end remove } // end PreorderIterator private class InorderIterator implements Iterator < T > { private Stack< BinaryNode< T >> nodeStack; private BinaryNode< T > currentNode; public InorderIterator () { nodeStack = new Stack < BinaryNode< T>> (); currentNode = root; } // end default constructor

public boolean hasNext () { return !nodeStack.isEmpty () || (currentNode != null); } // end hasNext

public T next () { BinaryNode< T > nextNode = null; // find leftmost node with no left child while (currentNode != null) { nodeStack.push (currentNode); currentNode = currentNode.getLeftChild (); } // end while // get leftmost node, then move to its right subtree if (!nodeStack.isEmpty ()) { nextNode = nodeStack.pop (); currentNode = nextNode.getRightChild (); } else throw new NoSuchElementException (); return nextNode.getData (); } // end next public void remove () { throw new UnsupportedOperationException (); } // end remove

} // end InorderIterator } // end BinaryTree

BinaryNode.java

//package TreePackage; class BinaryNode { private T data; private BinaryNode left; private BinaryNode right;

public BinaryNode() { this(null); // call next constructor } // end default constructor

public BinaryNode(T dataPortion) { this(dataPortion, null, null); // call next constructor } // end constructor

public BinaryNode(T dataPortion, BinaryNode leftChild, BinaryNode rightChild) { data = dataPortion; left = leftChild; right = rightChild; } // end constructor

public T getData() { return data; } // end getData

public void setData(T newData) { data = newData; } // end setData

public BinaryNode getLeftChild() { return left; } // end getLeftChild

public void setLeftChild(BinaryNode leftChild) { left = leftChild; } // end setLeftChild

public boolean hasLeftChild() { return left != null; } // end hasLeftChild

public boolean isLeaf() { return (left == null) && (right == null); } // end isLeaf public BinaryNode getRightChild() { return right; } // end getLeftChild

public void setRightChild(BinaryNode rightChild) { right = rightChild; } // end setLeftChild

public boolean hasRightChild() { return right != null; } // end

public int getHeight() { return getHeight(this); // call private getHeight } // end getHeight private int getHeight(BinaryNode node) { int height = 0; if (node != null) height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); return height; } // end getHeight public int getNumberOfNodes() { int leftNumber = 0; int rightNumber = 0; if (left != null) leftNumber = left.getNumberOfNodes(); if (right != null) rightNumber = right.getNumberOfNodes(); return 1 + leftNumber + rightNumber; } // end getNumberOfNodes public BinaryNode copy() { BinaryNode newRoot = new BinaryNode(data);

if (left != null) newRoot.left = left.copy(); if (right != null) newRoot.right = right.copy(); return newRoot; } // end copy } // end BinaryNode