c++ - 用于计算 BST 中具有两个子节点的节点数的递归函数

Question

我需要实现这个递归函数，它将以 BST 为根，并递归计算其中有两个孩子的节点数，但我不确定我的逻辑是否正确？

我的逻辑是：

1. 如果叶子或空，我们返回 0
2. 您检查是否有两个孩子的节点我们添加一个并再次调用它的左右孩子
3. 否则，如果一个节点没有两个子节点，则在其左右子树上调用而不添加

这是我的函数实现 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);

}

标签： c++algorithmtreebinary-search-tree

Answer 1

即使您的节点没有两个孩子，您也需要汇总计数。if 之后的两次 count 调用基本上没有被使用。你可以像这样修复它：

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。无论如何，所有其他节点都会添加到结果中。

我希望这是您要的信息！