java - 计算二叉搜索树中的节点数

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

你把这种方式搞得太复杂了。面向对象编程的基本思想是，您相信对象会完成它们知道答案的工作。所以如果我是 parent ，我可以数自己，我也让我的 child 数自己，等等。

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