On the code which has a class in which I implementing a binary tree using an array. This array, named store, stores Node in entries corresponding to
nodes in the tree and null if the node does not exist. Complete the countLeavesmethod so that it returns the number of leaves in this tree.
Code:
import java.util.AbstractSet; import java.util.Arrays; import java.util.Iterator; import java.util.NoSuchElementException; /** * Implementation of an abstract set using an array-based binary tree. This is * used to help teach binary tree\'s and will have more details explained in * future lectures. * * @author William J. Collins * @author Matthew Hertz * @param
Data type (which must be Comparable) of the elements in this tree. */ public class ArrayBinaryTree> extends AbstractSet { /** Entry in the data store where the root node can be found. */ private static final int ROOT = 0; /** Array used to store the nodes which consist of this binary tree. */ protected Node[] store; /** Number of elements within the tree. */ protected int size; /** * Initializes this ArrayBinaryTree object to be empty. This creates the array * in which items will be stored. */ @SuppressWarnings(\"unchecked\") public ArrayBinaryTree() { store = new Node[63]; size = 0; } /** * Initializes this ArrayBinaryTree object to contain a shallow copy of a * specified ArrayBinaryTree object. The worstTime(n) is O(n), where n is the * number of elements in the specified ArrayBinaryTree object. * * @param otherTree The tree which will be copied to create our new tree, */ @SuppressWarnings(\"unchecked\") public ArrayBinaryTree(ArrayBinaryTree otherTree) { store = (Node[]) Arrays.copyOf(otherTree.store, otherTree.store.length); size = otherTree.size; } public int countLeaves() { } /** * Returns the size of this ArrayBinaryTree object. * * @return the size of this ArrayBinaryTree object. */ @Override public int size() { return size; } /** * Returns an iterator that will return the elements in this ArrayBinaryTree, * but without any specific ordering. * * @return Iterator positioned at the smallest element in this ArrayBinaryTree * object. */ @Override public Iterator iterator() { return new ArrayTreeIterator(); } /** * Determines if there is at least one element in this ArrayBinaryTree object * that equals a specified element. The worstTime(n) is O(n) and * averageTime(n) is O(log n). * * @param obj - the element sought in this ArrayBinaryTree object. * @return true - if there is an element in this ArrayBinaryTree object that * equals obj; otherwise, return false. * @throws ClassCastException - if obj cannot be compared to the elements in * this ArrayBinaryTree object. * @throws NullPointerException - if obj is null. */ @Override public boolean contains(Object obj) { return getEntry(obj) != null; } /** * Ensures that this ArrayBinaryTree object contains a specified element. The * worstTime(n) is O(n) for this addition. * * @param element Element we want to be certain is contained within this * ArrayBinaryTree * @return True if the element had not been in ArrayBinaryTree and so was just * added; false if the element was already in the ArrayBinaryTree and * so did not need to be added or was null and so cannot be added. */ @Override public boolean add(E element) { // Null objects cannot be added to this Collection if (element == null) { return false; } // Handle the easy case when the tree has no elements if (isEmpty()) { Node root = new Node(element, ROOT); store[ROOT] = root; size++ ; return true; } // Handle the most common case -- adding the element to the end of the tree. else { int idx = ROOT; // Find the location where this element should be added in the tree while (true) { int comp = element.compareTo(store[idx].element); // The Set ADT definition only allows the Collection to contain a single // copy of an element; if this element had been previously added, we // should just return false if (comp == 0) { return false; } // If it is smaller, we should traverse to the left child else if (comp < 0) { idx = (idx * 2) + 1; } // Otherwise it must be larger, so we should traverse to the right child else { idx = (idx * 2) + 2; } // When the array is not large enough to hold the new element at the // location at which it needs to be added
Homework Sourse
