在 Java 中查找 BST 的大小

Question

我正在尝试使用这段代码查找 BST 的大小。

public static void main(String[] args) {

        BST bst = new BST();
        int [] arr = {12, 15,7,3,81, 9};
        for (int i = 0; i <arr.length; i++) {
            bst.add(arr[i]);
        }

        System.out.print(size(bst.root));

    }
    public static int size(Node node){
        if (node != null) {
            return size(node.left) +1 + size(node.right) + 1;
        }else
            return 0;
    }

我得到的答案是 12，这是第一个 element.What 我做错了吗？

Answer 1

你重复计算了。这里只需要一个+1。

Answer 2

你得到 12 的原因是你的代码 returns 是树中元素数量的两倍（其中有 6 个）。 12也恰好是第一个元素纯属巧合。

return 语句应为：

return 1 + size(node.left) + size(node.right);

即此节点加上左子树的大小加上右子树的大小。

你的第二个+1是错误的。

在 Java 中查找 BST 的大小

Finding the size of a BST in Java

java

binary-search-tree