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