In Albero binario, trovare quanti nonni hanno solo due o tre grandchildrens

Question

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

Ho bisogno di trovare i nonni di un albero, in questo exemple ho un solo nonno, numero 12 (ho bisogno che lui ha solo due o tre nipoti).

Questo è ciò che ho provato finora:

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; 

} 

Purtroppo non funziona ... Qualcuno mi può aiutare con questo?

Answer 1

Un approccio efficace consiste nel restituire ricorsivamente un paio di risultati. Ci sono più eleganti modi per restituire un paio in C++, ma io uso il vecchio modo kludgy C di tornare un uscita tramite un ingresso da puntatore:

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

La funzione fa due cose insieme. Il lavoro semplice è che aiuta a contare i nipoti dei suoi genitori incrementando *child_count e anche ricorsivamente fa il lavoro principale accumulando in t.

---

seguente modo potrebbe essere più facile da capire, ma è meno elegante:

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

Questo diventa più facile se si introduce un paio di funzioni bambino di conteggio, quella che conta i bambini e uno che conta nipoti:

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