在 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，这是第一个元素。我做错了什么？

Answer 1

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

return声明应为：

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

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

您拥有的第二个+1是错误的。

Answer 2

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