代码之家 › 专栏 › 技术社区 › user4833678

统计BST中的节点

binary-search-tree stack-overflow java

user4833678 · 技术社区 · 10 年前

我一直在 java.lang.StackOverflowError 在这一行:

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

3 回复 | 直到 10 年前

Alon 10 年前

试试这个,我觉得应该行得通

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的初始化。检查一下。。

Henry Walter 10 年前

我看到你的原始代码有两个问题。

第一个是你使用 while 语句。因为你从不改变 current ,这些循环将永远运行。

第二个问题是,您需要一个名为 node ,但永远不要使用它。相反,在方法体中,您引用了另一个变量 root 。这是导致StackOverflowError的原因。

更改 虽然 s到 if s应该有助于实现无限循环,重命名一些变量,以便使用函数的参数值,从而解决堆栈溢出问题。

作为补充说明,当节点为空而不是-1时,您可能希望返回零。这样,您可以进行递归调用,而不必检查子节点的空值,更重要的是,当树中没有节点时,函数会这样说。现在,一个没有节点的树看起来有-1个节点。

Ahmed Alrusaini 8 年前

//^_^

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

推荐文章