Java - data structures P2 Suppose we want to create a method for the class Binar
ID: 3826575 • 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
{
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<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> 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<T> leftChild,
BinaryNode<T> 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<T> getLeftChild()
{
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode<T> 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<T> getRightChild()
{
return right;
} // end getLeftChild
public void setRightChild(BinaryNode<T> 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<T> 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<T> copy()
{
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if (left != null)
newRoot.left = left.copy();
if (right != null)
newRoot.right = right.copy();
return newRoot;
} // end copy
} // end BinaryNode
Explanation / Answer
//Added new Methods
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack ; // for Stack
public class BinaryTree<T>
{
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 = (T) 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<BinaryNode<T>> 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<BinaryNode<T>> 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 (T) 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
public boolean isIsomorphic(BinaryTree<T> otherTree){
return isIsomorphic(this.root, otherTree.root);
}
private boolean isIsomorphic(BinaryNode<T> n1, BinaryNode<T> 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.getData().equals(n2.getData()))
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.getLeftChild(), n2.getLeftChild()) &&
isIsomorphic(n1.getRightChild(), n2.getRightChild()))
|| (isIsomorphic(n1.getLeftChild(), n2.getRightChild()) &&
isIsomorphic(n1.getRightChild(), n2.getLeftChild()));
}
} // end BinaryTree
class BinaryNode<T>
{
private T data;
private BinaryNode<T> left;
private BinaryNode<T> 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<T> leftChild,
BinaryNode<T> 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<T> getLeftChild()
{
return left;
} // end getLeftChild
public void setLeftChild(BinaryNode<T> 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<T> getRightChild()
{
return right;
} // end getLeftChild
public void setRightChild(BinaryNode<T> 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<T> 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<T> copy()
{
BinaryNode<T> newRoot = new BinaryNode<T>(data);
if (left != null)
newRoot.left = left.copy();
if (right != null)
newRoot.right = right.copy();
return newRoot;
} // end copy
} // end BinaryNode
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.