c++ - 检查树故障的算法

Question

我写这段代码是为了检查有多少节点只剩下儿子

template <class T>
int Tree<T>::onlyLeftSon(Node<T> * current) //check how many left son there are on trehh
{
    if (current == NULL) //empty tree or we finish the tree
        return 0;

    return ( onlyLeftSon(current->left) + onlyLeftSon(current->right) ); // return the sum from left and right

    if (!current->left && !current->right) //if this node not have sons
        return 0;

    if (current->left && !current->right) //if this node not has only left son
        return 1;


}

这个返回0 为什么？

Answer 1

无条件声明:

    return ( onlyLeftSon(current->left) + onlyLeftSon(current->right) );

总是在 current == NULL 检查失败后发生。这意味着您将始终将 onlyLeftSon 计算为 所有 情况下的两个子节点的总和，current == NULL 情况除外，其中你返回 0。 0 + 0 将始终为零。

您可能想要的是:

template <class T>
int Tree<T>::onlyLeftSon(Node<T> * current)
{
    if (current == NULL) //empty tree or we finish the tree
        return 0;

    if (!current->left && !current->right) //if this node not have sons
        return 0;

    if (current->left && !current->right) //if this node not has only left son
        return 1;

    return ( onlyLeftSon(current->left) + onlyLeftSon(current->right) );
}

---

此时，该算法似乎正在计算父树只有左叶的树中的叶数。这与计算左叶数或一般的左子节点数不同:

    a
  /   \
 b     c

上面的树将返回 onlyLeftSon(tree) == 0。为什么？

• 当 current == a 时，我们有:
  • current != NULL、current->left != NULL 和 current->right != NULL。
  • 因此，没有一个 if 语句成功，我们递归到 b 和 c。
  • b 和 c 都返回 0，因为它们都没有 child 。

这就是你想要做的吗？还是您要总体上计算每个左叶？