了解二叉搜索树计数

Question

我无法理解这种二叉搜索树方法是如何计算节点的，我在网上查看了许多示例，但是我找不到一个可以准确解释正在发生的事情的示例。

这是一个例子：

public int nodes() {

    int leftNodes = 0;

    if (left != null) {

        leftNodes = left.nodes();

    }

    int rightNodes = 0;

    if (right != null) {

        rightNodes = right.nodes();

    }

    return leftNodes + rightNodes + 1;

}

这就是我理解这种方法的过程的方式，也许有人可以帮助我理解我哪里出错了。

1. 该方法是从其自身外部从一个 BTS 对象调用的；“tree.nodes() 等”。

2. int leftNodes 被声明并设置为 0。

3. 如果有左节点（假设有），那么leftNodes的值将被赋值给nodes()调用的返回值；

4. 递归调用将再次通过 nodes 方法，再次将 leftNodes 分配为零。

所以我不明白 leftNodes 变量在哪里递增？似乎它只是再次通过该方法递归，但值没有改变，从我看到的 leftNodes 和 rightNodes 将始终为 0。

我发现了另一个 BTS 计数的例子，这个使用 C++

int CountNodes(node*root)

{

if(root==NULL)

    return 0;

if(root->left!=NULL)

{

    n=n+1;

    n=CountNodes(root->left);

}

if(root->right!=NULL)

{

    n=n+1;

    n=CountNodes(root->right);

}

return n;

}

我发现这种方法更容易遵循，因为每次找到节点时 n 显然都会增加。

我的问题是 leftNodes/rightNodes 值是如何在递归调用中递增的？

Answer 1

您应该考虑递归的结束。假设您有一个没有子节点的节点。两者都left将right是null，因此您将不会进行递归调用。你会回来的leftNodes + rightNodes + 1; // 0 + 0 + 1 == 1现在，假设您有一个简单的树，它由一个根、一个左孩子和一个右孩子组成。当您调用nodes()该树的根时，两者left和right都不为空，因此我们将调用两者left.nodes()和right.nodes()。由于左右子节点都是叶节点（即它们没有子节点），因此对两者的递归调用都将返回 1，如上所述。因此，当递归调用返回时，我们将返回leftNodes + rightNodes + 1; // 1 + 1 + 1 == 3这是我们树中的节点数。

Answer 2

变量leftNodes和rightNodes是方法的局部变量，nodes()这意味着对于方法的每次调用，这些变量都有不同的实例。因此，当您递归调用该方法（left.nodes()例如）时，leftNodes递归调用之前和之后的值是相同的，因为它（调用）将具有leftNodes(and rightNodes) 的一个实例。

Answer 3

这是一个基本的实现inorder traversal。对于每个节点，它都会转到左子节点，直到没有左子节点为止（由于递归，就像在每次访问节点时将其推入堆栈一样）。然后它对堆栈顶部重复相同的过程，直到堆栈中没有元素为止（再次注意，与递归相比，堆栈用于使事情变得更简单）。这样做时，它基本上将其访问的每个节点的总和增加一。