我无法理解这种二叉搜索树方法如何对节点进行计数,我已经在网上查看了很多示例,但是我找不到可以准确解释所发生情况的示例。
这是一个例子:
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 值是如何在递归调用中递增的?
最佳答案
你应该考虑递归的结束。
假设您有一个没有子节点的节点。
left
和 right
都将为 null
,因此您将不会进行递归调用。
你会回来的
leftNodes + rightNodes + 1; // 0 + 0 + 1 == 1
现在,假设您有一棵简单的树,由一个根、一个左 child 和一个右 child 组成。
当您为该树的根调用 nodes()
时,left
和 right
都不为空,因此我们将调用left.nodes()
和 right.nodes()
。由于左右子节点都是叶节点(即它们没有子节点),因此对两者的递归调用都将返回 1,如上所述。
因此,当递归调用返回时,我们将返回
leftNodes + rightNodes + 1; // 1 + 1 + 1 == 3
这是我们树中的节点数。
关于java - 了解二叉搜索树计数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/54746184/