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