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 { private T data; private BinaryNode left; private BinaryNode 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 leftChild, BinaryNode 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 getLeftChild() { return left; } // end getLeftChild

public void setLeftChild(BinaryNode 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 getRightChild() { return right; } // end getLeftChild

public void setRightChild(BinaryNode 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 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 copy() { BinaryNode newRoot = new BinaryNode(data);

if (left != null) newRoot.left = left.copy(); if (right != null) newRoot.right = right.copy(); return newRoot; } // end copy } // end BinaryNode