我需要实现这个递归函数,它将获取 BST 的根并递归计算其中有两个孩子的节点数,但我不确定我的逻辑是否正确?
我的逻辑是:
- 如果叶子或空,我们返回 0
- 您检查一个节点是否有两个子节点,我们添加一个节点并在其左右子节点上再次调用
- 否则,如果一个节点没有两个子节点,则调用其左右子树而不添加
这是我的函数实现 ps:假设 BinarySearchTree 类中的所有内容都实现了:
int count(BinarySearchTree *root )
{
if(root== nullptr)
{
return 0;
}
if(root->right != nullptr and root->left!= nullptr)
{
return 1+count(root->right)+count(root->left);
}
count(root->right);
count(root->left);
}
即使您的节点没有两个子节点,您也需要对计数进行汇总。你之后的两个计数调用 if 基本上不使用。 你可以这样修复它:
int count(BinarySearchTree *root )
{
if (root== nullptr)
{
return 0;
}
int countForThisNode = root->right != nullptr and root->left!= nullptr;
return countForThisNode + count(root->right) + count(root->left);
}
在这种情况下,countForThisNode
对于要计数的节点,为 1,否则为 0。无论如何,所有其他节点都会添加到结果中。
我希望这是您要求的信息!
您的函数具有未定义的行为,因为控件可以转移到右大括号而不返回任何内容。
count(root->right);
count(root->left);
}
对于初学者,由于列表未更改,因此参数应具有限定符const
。
该函数可以通过以下方式简单得多
unsigned int count( const BinarySearchTree *root )
{
return root == nullptr ? 0
: ( root->left && root->right ) + count( root->left )
+ count( root->right );
}
实现此函数的一种简单方法:
-
从节点的标准枚举开始(可以是前缀、中缀、后缀,没关系(;
-
修改它,以便在每个节点上,如果有两个子节点,则增加计数器。
请注意,您需要查看整个树,因为它的一部分可以通过单子节点访问。
visit(root):
if root.left != null:
visit(root.left)
if root.right != null:
visit(root.right)
成为
visit(root):
count= root.left != null and root.right != null
if root.left != null:
count+= visit(root.left)
if root.right != null:
count+= visit(root.right)
return count