, ben, bir ağacın dedeler bulmalıyız bu Exemple I, sayı 12 (O sadece iki veya sahip olduğu tek dede ihtiyacım var

Question

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

sadece iki veya üç Grandchildrens kaç büyükbabaları bulmak üç torun).

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; 

} 

Ne yazık ki çalışmıyor ... Herkes bu konuda bana yardımcı olabilir:

Bu defa denedim nedir?

Answer 1

Verimli bir yaklaşım, bir çift sonucu yinelemeli olarak döndürmektir. Orada C++ bir çift dönmek için daha şık yolu vardır, ama pointer tarafından girdi aracılığıyla bir çıkış dönen eski kludgy C yolunu kullanacağız:

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); } 

fonksiyon birlikte iki şey yapar. Basit iş, *child_count'u artırarak, ebeveyninin torunlarını saymaya yardımcı olur ve aynı zamanda, t içinde birikerek ana işi yinelemeli olarak yapar.

---

şu yolu anlamak daha kolay olabilir, ancak daha az zarif:

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

Eğer çocuk sayma fonksiyonları bir çift, çocukları sayar diğeri sayar birini tanıtmak, bu daha kolay olur torunlar:

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); 
    } 
}