Java - data structures P1 Suppose we want to create a method for the class Binar
ID: 3827590 • Letter: J
Question
Java - data structures
P1
Suppose we want to create a method for the class BinaryTree (file BinaryTree.java) that counts the number of times an object occurs in the tree.
a. Write the method
public int count1(T anObject)
which calls the private recursive method
private int count1(BinaryNode rootNode, T anObject)
to count the number of occurrences of anObject
b. Write the method
public int count2(T anObject)
that counts the number of occurrences of anObject and that uses one of the iterators of the binary tree.
Compare the efficiencies of the previous the two methods count1 and count2 using big O notation. Add your answer as a comment before the function definition
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
import java.util.Iterator; import java.util.NoSuchElementException; import java.util.Stack; // for nodeStack 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(); } // Runtime: O(n) public int count1(T anObject) { return count1(root, anObject); } private int count1(BinaryNode rootNode, T anObject) { if (rootNode = null) { return 0; } if (rootNode.getData.equals(anObject)) { return 1; } return count1(rootNode.getLeftChild, anObject) + count1(rootNode.getRightChild); } //Runtime O(n) public int count2(T anObject) { InorderIterator iterator = new InorderIterator(); int count = 0; while (iterator.hasNext() == true) { if (iterator.next().equals(anObject) count++; } return count; } public boolean isIsomorphic(BinaryTree otherTree) { BinaryNode thisRoot = root; return isIsomorphic(thisRoot, otherTree.root); } //checks whether two binary trees have the same structure and the same values private isIsomorphic(BinaryNode root1, BinaryNode root2) { boolean same = true; if((root1.getRightChild() == null && root1.getLeftChild() == null) && (root2.getRightChild() == null && root2.getLeftChild() == null)) return same; if(!root1.equals(root2)) same = false; return (isIsomorphic(root1.getRightChild(), root2.getRightChild()) == isIsomorphic(root1.getLeftChild(), root2.getLeftChild()) ? true:false); } 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 { private Stack nodeStack; private BinaryNode currentNode; public InorderIterator() { nodeStack = new Stack (); currentNode = root; } // end default constructor public boolean hasNext() { return !nodeStack.isEmpty() || (currentNode != null); } // end hasNext public T next() { BinaryNode 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 BinaryTreeRelated Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.