c++ - 在“二叉树”中，找到多少个祖父只有两个或三个孙子

                                   8
                                /      \
                              4         12
                             / \         / \
                           3    6       2   1
                          / \   / \    /   / \
                         7  10 13 15  5   9  11
                                             /
                                            14

我需要找到一棵树的祖父，在这个例子中，我只有一个12号祖父(我需要他只有两个或三个孙子)。

这是我到目前为止尝试过的:

int T(struct node * tree){
    int t = 0;
    if (tree == NULL)
        return 0;
    if (tree->left && tree->right)
    {    //In this case i check if we NOT have all the four grandchildrens.
        if (!((tree->left->left) && (tree->left->right) && (tree->right->left) && (tree->right->right)))
        {
            t =  1 + T(tree->left) + T(tree->right);
            T(tree->left);
            T(tree->right);

        }
        else
       {
            T(tree->left);
            T(tree->right);
        }

    }

    return t;

}

不幸的是，它不起作用...有人可以帮我吗？

最佳答案

一种有效的方法是递归返回一对结果。在C++中有更优雅的方法来返回一对，但是我将使用旧的kludgy C方法来通过指针的输入返回一个输出:

int T2(struct node * tree, int* child_count)
{
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( tree->left )
    {
       ++ *child_count;
       t += T2( tree->left, &g );
    }
    if ( tree->right )
    {
       ++ *child_count;
       t += T2( tree->right, &g );
    }
    if ( g==2 || g==3 )
       ++t;
    return t;
}

int T(struct node * tree) {int dummy; return T2(tree, &dummy); }

该函数一起执行两件事。简单的工作是通过增加*child_count来帮助计算其 parent 的孙子孙女，并且通过累加t来递归地完成主要工作。

以下方法可能更容易理解，但不太优雅:

int T(struct node * tree)
{
    struct node *c;
    int t = 0;  // Count the things we are supposed to count
    int g = 0;  // Count grandchildren of the current node
    if (tree == NULL)
        return 0;
    if ( (c=tree->left) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( (c=tree->right) != NULL )
    {
       g += (c->left != NULL) + (c->right != NULL);
       t += T( c );
    }
    if ( g==2 || g==3 )
       ++t;
    return t;
}