了解二叉搜索树计数

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;}这就是我理解这种方法的过程的方式，也许有人可以帮助我理解我哪里出错了。该方法是从其自身外部从一个 BTS 对象调用的；“tree.nodes() 等”。int leftNodes 被声明并设置为 0。如果有左节点（假设有），那么leftNodes的值将被赋值给nodes()调用的返回值；递归调用将再次通过 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。对于每个节点，它都会转到左子节点，直到没有左子节点为止（由于递归，就像在每次访问节点时将其推入堆栈一样）。然后它对堆栈顶部重复相同的过程，直到堆栈中没有元素为止（再次注意，与递归相比，堆栈用于使事情变得更简单）。这样做时，它基本上将其访问的每个节点的总和增加一。