Java - data structures P2 Suppose we want to create a method for the class Binar
ID: 3825802 • Letter: J
Question
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<T> 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<T>
{
protected BinaryNode<T> root;
public BinaryTree() {
root = null;
} // end default constructor
public BinaryTree(T rootData) {
root = new BinaryNode<T>(rootData);
} // end constructor
public BinaryTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree) {
privateSetTree(rootData, leftTree, rightTree);
} // end constructor
public void setTree(T rootData)
{
root = new BinaryNode<T>(rootData);
} // end setTree
public void setTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
privateSetTree(rootData, leftTree, rightTree);
} // end setTree
private void privateSetTree(T rootData, BinaryTree<T> leftTree,
BinaryTree<T> rightTree)
{
root = new BinaryNode<T>(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<T>
public int getHeight () {
return root.getHeight ();
}
public int getNumberOfNodes () {
return root.getNumberOfNodes ();
}
public void inorderTraversal() {
Stack<BinaryNode<T>> nodeStack = new Stack<BinaryNode<T>>();
BinaryNode<T> currentNode = root;
while (!nodeStack.empty() || currentNode != null) {
while(currentNode != null) {
nodeStack.push(currentNode);
currentNode = currentNode.getLeftChild();
}
if(!nodeStack.empty()) {
BinaryNode<T> nextNode = nodeStack.pop();
System.out.println(nextNode.getData());
currentNode = nextNode.getRightChild();
}
}
}
public Iterator<T> getPreorderIterator() {
return new PreorderIterator();
}
public Iterator<T> getInorderIterator() {
return new InorderIterator();
}
private class PreorderIterator implements Iterator<T> {
private Stack<BinaryNode<T>> nodeStack;
public PreorderIterator() {
nodeStack = new Stack<BinaryNode<T>>();
if (root != null)
nodeStack.push(root);
} // end default constructor
public boolean hasNext() {
return !nodeStack.isEmpty();
} // end hasNext
public T next() {
BinaryNode<T> nextNode;
if (hasNext()) {
nextNode = nodeStack.pop();
BinaryNode<T> leftChild = nextNode.getLeftChild();
BinaryNode<T> 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
Explanation / Answer
There are few things missing from the code given -
- There is no information about the structure of each Node in the Binary Tree.
- No information about how to check this class - there is no "main" method here..
- No information about this method - public boolean isIsomorphic(BinaryTree<T> otherTree) in the given class.
As you are trying to find Isomorphic morphic property between two BinaryTrees, I have written a small program for the same as below.
You can use the isIsomorphic method from this program and include in your program.
// An iterative java program to solve tree isomorphism problem
/* A binary tree node has data, pointer to left and right children */
class Node
{
int data;
Node left, right;
Node(int item)
{
data = item;
left = right;
}
}
class BinaryTree
{
Node root1, root2;
// For the first call to this method from main method,
// Node 1 is root node of BinaryTree 1 and
// Node 2 is root node of BinaryTree 2.
boolean isIsomorphic(Node n1, Node n2)
{
// Both roots are NULL, trees isomorphic by definition
if (n1 == null && n2 == null)
return true;
// Exactly one of the n1 and n2 is NULL, trees not isomorphic
if (n1 == null || n2 == null)
return false;
if (n1.data != n2.data)
return false;
// There are two possible cases for n1 and n2 to be isomorphic
// Case 1: The subtrees rooted at these nodes have NOT been "Flipped".
// Both of these subtrees have to be isomorphic.
// Case 2: The subtrees rooted at these nodes have been "Flipped"
return (isIsomorphic(n1.left, n2.left) &&
isIsomorphic(n1.right, n2.right))
|| (isIsomorphic(n1.left, n2.right) &&
isIsomorphic(n1.right, n2.left));
}
// Driver program to test above functions
public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
// Let us create trees shown in above diagram
tree.root1 = new Node(1);
tree.root1.left = new Node(2);
tree.root1.right = new Node(3);
tree.root1.left.left = new Node(4);
tree.root1.left.right = new Node(5);
tree.root1.right.left = new Node(6);
tree.root1.left.right.left = new Node(7);
tree.root1.left.right.right = new Node(8);
tree.root2 = new Node(1);
tree.root2.left = new Node(3);
tree.root2.right = new Node(2);
tree.root2.right.left = new Node(4);
tree.root2.right.right = new Node(5);
tree.root2.left.right = new Node(6);
tree.root2.right.right.left = new Node(8);
tree.root2.right.right.right = new Node(7);
if (tree.isIsomorphic(tree.root1, tree.root2) == true)
System.out.println("Yes");
else
System.out.println("No");
}
}
OUTPUT:
Yes.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.