、2つまたは3 grandchildrens

Question

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

を持っている私は、彼は2つだけかを持っていることを必要とする（数12、このexempleで私が唯一の祖父を持つ、木の祖父を見つける必要があるどのように多くの祖父見つけます3人の孫）。

これは私がこれまで試したものです：

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; 

} 

残念ながら、それは動作しません...誰もがこれで私を助けることができますか？

Answer 1

1つの効率的なアプローチは、結果のペアを再帰的に返すことです。そこC++でのペアを返すために、よりエレガントな方法がありますが、私は、ポインタによって入力を通じて1つの出力を返すの古い場しのぎ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); } 

機能は一緒に2つのことを行います。単純な仕事は、*child_countをインクリメントして親の孫を数えるのに役立ち、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; 
} 

Answer 2

あなたは子供計数機能の夫婦、子供とカウント1をカウント1を導入した場合にこれが容易になります孫：

int children(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    int count = 0; 
    if (tree->left) 
    { 
     count += 1; 
    } 
    if (tree->right) 
    { 
     count += 1; 
    } 
    return count; 
} 

int grandchildren(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    return children(tree->left) + children(tree->right); 
} 

int grandparents(node* tree) 
{ 
    if (!tree) 
    { 
     return 0; 
    } 
    int count = grandchildren(tree); 
    if (count == 2 || count == 3) 
    { 
     return 1 + grandparents(tree->left) + grandparents(tree->right); 
    } 
    else 
    { 
     return grandparents(tree->left) + grandparents(tree->right); 
    } 
}