防止堆棧溢出錯誤

Question

當測試方法numberOfNodeAtLevel而不是獲取返回值時，出現堆棧溢出錯誤。爲什麼是這樣？我該如何預防呢？這個方法應該讓我知道在樹的特定層上有多少個節點。

public class BST<E extends Comparable<E>> { 
    int height = 0; 
    protected TreeNode<E> root; 
    protected int size = 0; 

    /** Create a default binary tree */ 
    public BST() { 
    } 

    /** Create a binary tree from an array of objects */ 
    public BST(E[] objects) { 
    for (int i = 0; i < objects.length; i++) 
     insert(objects[i]); 
    } 

    /** Returns true if the element is in the tree */ 
    public boolean search(E e) { 
    TreeNode<E> current = root; // Start from the root 

    while (current != null) { 
     if (e.compareTo(current.element) < 0) { 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     current = current.right; 
     } 
     else // element matches current.element 
     return true; // Element is found 
    } 

    return false; 
    } 

    /** Insert element o into the binary tree 
    * Return true if the element is inserted successfully */ 
    public boolean insert(E e) { 
    if (root == null) 
     root = createNewNode(e); // Create a new root 
    else { 
     // Locate the parent node 
     TreeNode<E> parent = null; 
     TreeNode<E> current = root; 
     while (current != null) 
     if (e.compareTo(current.element) < 0) { 
      parent = current; 
      current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
      parent = current; 
      current = current.right; 
     } 
     else 
      return false; // Duplicate node not inserted 

     // Create the new node and attach it to the parent node 
     if (e.compareTo(parent.element) < 0) 
     parent.left = createNewNode(e); 
     else 
     parent.right = createNewNode(e); 
    } 

    size++; 
    return true; // Element inserted 
    } 

    protected TreeNode<E> createNewNode(E e) { 
    return new TreeNode<E>(e); 
    } 

    /** Inorder traversal from the root*/ 
    public void inorder() { 
    inorder(root); 
    } 

    /** Inorder traversal from a subtree */ 
    protected void inorder(TreeNode<E> root) { 
    if (root == null) return; 
    inorder(root.left); 
    System.out.print(root.element + " "); 
    inorder(root.right); 
    } 

    /** Postorder traversal from the root */ 
    public void postorder() { 
    postorder(root); 
    } 

    /** Postorder traversal from a subtree */ 
    protected void postorder(TreeNode<E> root) { 
    if (root == null) return; 
    postorder(root.left); 
    postorder(root.right); 
    System.out.print(root.element + " "); 
    } 

    /** Preorder traversal from the root */ 
    public void preorder() { 
    preorder(root); 
    } 

    /** Preorder traversal from a subtree */ 
    protected void preorder(TreeNode<E> root) { 
    if (root == null) return; 
    System.out.print(root.element + " "); 
    preorder(root.left); 
    preorder(root.right); 
    } 

    /** This inner class is static, because it does not access 
     any instance members defined in its outer class */ 
    public static class TreeNode<E extends Comparable<E>> { 
    protected E element; 
    protected TreeNode<E> left; 
    protected TreeNode<E> right; 

    public TreeNode(E e) { 
     element = e; 
    } 
    } 

    /** Get the number of nodes in the tree */ 
    public int getSize() { 
    return size; 
    } 

    /** Returns the root of the tree */ 
    public TreeNode<E> getRoot() { 
    return root; 
    } 

    /** Returns a path from the root leading to the specified element */ 
    public java.util.ArrayList<TreeNode<E>> path(E e) { 
    java.util.ArrayList<TreeNode<E>> list = 
     new java.util.ArrayList<TreeNode<E>>(); 
    TreeNode<E> current = root; // Start from the root 

    while (current != null) { 
     list.add(current); // Add the node to the list 
     if (e.compareTo(current.element) < 0) { 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     current = current.right; 
     } 
     else 
     break; 
    } 

    return list; // Return an array of nodes 
    } 

    /** Delete an element from the binary tree. 
    * Return true if the element is deleted successfully 
    * Return false if the element is not in the tree */ 
    public boolean delete(E e) { 
    // Locate the node to be deleted and also locate its parent node 
    TreeNode<E> parent = null; 
    TreeNode<E> current = root; 
    while (current != null) { 
     if (e.compareTo(current.element) < 0) { 
     parent = current; 
     current = current.left; 
     } 
     else if (e.compareTo(current.element) > 0) { 
     parent = current; 
     current = current.right; 
     } 
     else 
     break; // Element is in the tree pointed at by current 
    } 

    if (current == null) 
     return false; // Element is not in the tree 

    // Case 1: current has no left children 
    if (current.left == null) { 
     // Connect the parent with the right child of the current node 
     if (parent == null) { 
     root = current.right; 
     } 
     else { 
     if (e.compareTo(parent.element) < 0) 
      parent.left = current.right; 
     else 
      parent.right = current.right; 
     } 
    } 
    else { 
     // Case 2: The current node has a left child 
     // Locate the rightmost node in the left subtree of 
     // the current node and also its parent 
     TreeNode<E> parentOfRightMost = current; 
     TreeNode<E> rightMost = current.left; 

     while (rightMost.right != null) { 
     parentOfRightMost = rightMost; 
     rightMost = rightMost.right; // Keep going to the right 
     } 

     // Replace the element in current by the element in rightMost 
     current.element = rightMost.element; 

     // Eliminate rightmost node 
     if (parentOfRightMost.right == rightMost) 
     parentOfRightMost.right = rightMost.left; 
     else 
     // Special case: parentOfRightMost == current 
     parentOfRightMost.left = rightMost.left;  
    } 

    size--; 
    return true; // Element inserted 
    } 

    /** Obtain an iterator. Use inorder. */ 
    public java.util.Iterator<E> iterator() { 
    return new InorderIterator(); 
    } 

    // Inner class InorderIterator 
    private class InorderIterator implements java.util.Iterator<E> { 
    // Store the elements in a list 
    private java.util.ArrayList<E> list = 
     new java.util.ArrayList<E>(); 
    private int current = 0; // Point to the current element in list 

    public InorderIterator() { 
     inorder(); // Traverse binary tree and store elements in list 
    } 

    /** Inorder traversal from the root*/ 
    private void inorder() { 
     inorder(root); 
    } 

    /** Inorder traversal from a subtree */ 
    private void inorder(TreeNode<E> root) { 
     if (root == null)return; 
     inorder(root.left); 
     list.add(root.element); 
     inorder(root.right); 
    } 

    /** More elements for traversing? */ 
    public boolean hasNext() { 
     if (current < list.size()) 
     return true; 

     return false; 
    } 

    /** Get the current element and move to the next */ 
    public E next() { 
     return list.get(current++); 
    } 

    /** Remove the current element */ 
    public void remove() { 
     delete(list.get(current)); // Delete the current element 
     list.clear(); // Clear the list 
     inorder(); // Rebuild the list 
    } 
    } 

    /** Remove all elements from the tree */ 
    public void clear() { 
    root = null; 
    size = 0; 
    } 

    public double treeHeight(){ 
     double level = this.getSize(); 
     if (level ==0) 
      return 0; 
     if (level < 2){ 
      return level; 
     } 
     if(level == 2){ 
      return 2; 
     } 
     else 
     while (level >= 2){ 
      height++; 
      level = level/2; 
     } 
    return height++; 
    } 

    public double numberOfNodeAtLevel(TreeNode node, double current,double desired){ 
     TreeNode<E> currentNode = root; 
     if (currentNode == null){ 
      return 0; 
     } 
     if (currentNode.equals(node)){ 
     return 1;} 

     else return numberOfNodeAtLevel(currentNode.left, current+1, desired)+ 
        numberOfNodeAtLevel(currentNode.right, current+1, desired); 


    } 





    public static void main(String[] args){ 
     BST <String> c = new BST<String>(); 
     c.insert("50"); 
     c.insert("25"); 
     c.insert("55"); 
     c.insert("13"); 
     c.insert("65"); 
     c.insert("10"); 
     c.insert("14"); 
     c.insert("54"); 
    TreeNode<String> h = new TreeNode <String>(null); 

    System.out.println(c.numberOfNodeAtLevel(h,0,1)); 


    } 
} 

Answer 1

在遞歸調用中問題是TreeNode<E> currentNode = root。

嘗試：

public int numberOfNodeAtLevel(int desired){ 
    return numberOfNodeAtLevelRecursive(root, 0, desired); 
} 
private int numberOfNodeAtLevelRecursive(TreeNode node, int current, 
            int desired) { 
    // do the recursion 
}