BST 中的节点计数

Question

我一直在这一行收到 java.lang.WhosebugError：

count += countNodes(current.leftChild);

当我尝试计算 BST 中的节点总数时。有人可以告诉我为什么会出现该错误吗？提前致谢！

public int countNodes(Node node){
        if(root == null){
            System.out.println("The tree is empty!");
            return -1;
        }
        else{
            int count = 1;
            Node current = root;
            while(current.leftChild != null){
                count += countNodes(current.leftChild);
            }
            while(current.rightChild != null){
                count += countNodes(current.rightChild);
            }
            return count;
        }
    }

Answer 1

尝试一下我认为它应该有效

public int countNodes(Node root){
    if(root == null){
        System.out.println("The tree is empty!");
        return 0;
    } 
    else{
        Node current = root;
        int count = 0 
        if(current.leftChild != null){
            count +=  countNodes(current.leftChild)+1;
        }
        if(current.rightChild != null){
            count += countNodes(current.rightChild)+1;
        }
        return count;
    }
}

你从根到叶进行递归。查看您使用 while 循环的代码。问题是在这个递归中，你是通过递归而不是 while 循环进入深度的。

你把左边树的运算结果加到右边的运算中。递归的停止条件是当根没有孩子时。

当

  current.rightChild == null && current.leftChild == null

可能是我把count的init弄糊涂了。检查一下..

Answer 2

我发现您的原始代码有两个问题。

首先是在查看左右子树时使用while语句。由于您永远不会更改 current 的值，因此这些循环将永远运行。

第二个问题是您使用了一个名为 node 的参数，但从未使用过它。相反，在方法主体中，您引用了另一个变量 root。这就是导致 WhosebugError 的原因。

将 whiles 更改为 ifs 应该有助于无限循环，重命名一些变量以便您使用函数的参数值应该可以解决堆栈溢出问题。

作为旁注，当节点为 null 而不是 -1 时，您可能希望 return 为零。这样，您就可以进行递归调用而不必检查子节点是否为空，更重要的是，当树中的节点为零时，函数会这样说。现在，零节点的树看起来有 -1 个节点。

Answer 3

//^_^

public int getCount(){
    return getCount(root);
}

public int getCount(BSTNode<T> p){
    if(p == null){
        return 0;
    }
    else{
        int count = 1;
        BSTNode<T> current = p;
        while(current.left != null){
            count += getCount(current.left);
        }
        while(current.right != null){
            count += getCount(current.right);
        }
        return count;
    }
}

BST 中的节点计数

Counting nodes in BST

java

stack-overflow

binary-search-tree