计算二叉搜索树中的节点

Question

我需要创建一个递归方法,将二进制搜索树的根节点作为参数.然后,此递归方法将返回整个二叉搜索树中节点总数的int值.

这是我到目前为止:

public class BinarySearchTree<E> extends AbstractSet<E>
{
protected Entry<E> root; 


//called by the main method
public int nodes()
{
    return nodes(root);
}       

//nodes() will count and return the nodes in the binary search tree

private int nodes(Entry<E> current)
{    
    if(current.element != null)
    { 
        if(current.left == null && current.right == null)
        {
            if(current.element == root.element)
            return 1;                   

            deleteEntry(current);              
            return 1 + nodes(current.parent);
        }
        else if(current.left != null && current.right == null)        
            return nodes(current.left);

        else if(current.left == null && current.right != null)
            return nodes(current.right);

        else if(current.left != null && current.right != null)
            return nodes(current.left) + nodes(current.right);      
    } else return 1;
    return 0;
}

main方法调用如下节点:

        System.out.println ("\nThis section finds the number of nodes "
             + "in the tree"); 

        System.out.println ("The BST has " + bst.nodes() + " nodes");

所以我按顺序运行搜索,一旦我到达没有孩子的节点,我将删除当前节点并返回到父节点并继续.我运行了上面的方法的调试,当程序最终计数并删除根节点左侧和右侧的所有节点并尝试返回1时,程序崩溃并使用NullPointerException().

这是我的实验室,方法必须是递归的.

我现在很迷茫,有谁知道我做错了什么？

Answer 1

你这样做太复杂了.面向对象编程的基本思想是,您可以信任对象来完成他们知道答案的工作.因此,如果我是父母,我可以自己计算,我让我的孩子自己计算,等等.

private int nodes(Entry<E> current) {   
  // if it's null, it doesn't exist, return 0 
  if (current == null) return 0;
  // count myself + my left child + my right child
  return 1 + nodes(current.left) + nodes(current.right);
}