我很难理解这种二叉搜索树方法是如何计算节点的,我在网上查看了许多示例,但是找不到一个可以确切说明正在发生什么的示例。
这是一个例子:
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()的调用的返回值。
递归调用将再次通过节点方法,再次将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
现在,假设您有一棵简单的树,该树由一个根,一个左子代和一个右子代组成。
当您为该树的根调用
nodes()
时,left
和right
都不为空,因此我们将同时调用left.nodes()
和right.nodes()
。由于左子节点和右子节点都是叶节点(即它们没有子节点),因此对它们的递归调用将返回1,如上所述。因此,当递归调用返回时,我们将返回
leftNodes + rightNodes + 1; // 1 + 1 + 1 == 3
这是我们树中的节点数。