对二叉搜索树中的节点进行计数

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);
}