une fonction récursive pour calculer la hauteur de l'arbre n-aéré

Question

J'ai besoin de votre aide pour résoudre ces problèmes. Je résolus en studio visuel une fonction récursive pour calculer la hauteur de l'arbre n-aire. Quand je l'ai testé dans un petit arbre, cela m'a donné la valeur de la hauteur. Cependant, lorsque j'ai compilé le code d'une plus grande quantité de données, l'exécution a pris plus de 3 jours sans résultats. La fonction i utilisé est le suivant:

unsigned int Height(NaryNode *root) 
{ 
    unsigned int HeightMax = 0; 
    unsigned i; 
    for (i = 0; i < root->nchild; i++) 
    { 
     if (Height(root->child[i])>HeightMax) 
     HeightMax = Height(root->child[i]); 
    } 
    return (HeightMax + 1); 
} 

Nous vous remercions à l'avance ..

Answer 1

Vous calculez la hauteur deux fois pour chaque sous-arbre.
Si l'arbre est profond, cela va prendre beaucoup de temps.

Pour simplifier, supposons que chaque noeud ne possède qu'un seul enfant.

Ensuite, à partir de la racine, vous calculez deux fois la hauteur de son enfant.
Pour chacun de ces calculs, vous calculez la hauteur de l'enfant de cet enfant deux fois - c'est quatre appels de fonction.
Pour chacun de ces quatre, vous faites deux calculs - c'est huit.

Pour chaque niveau vers le bas, vous doubler le nombre d'appels à Height, et calculer la hauteur d'un arbre avec 32 nœuds enfant unique a besoin de plus de quatre appels de fonction milliards. Enregistrez le résultat de Height(root->child[i]) dans une variable.

Answer 2

Eh bien, vous appelez la même fonction récursive avec le même paramètre deux fois, cela va rendre les choses assez lent.

unsigned int Height(NaryNode *root) 
{ 
    unsigned int HeightMax = 0; 
    unsigned i; 
    for (i = 0; i < root->nchild; i++) 
    { 
     auto currHeigth = Height(root->child[i]) 
     if (currHeight > HeightMax) 
     HeightMax = currHeight; 
    } 
    return (HeightMax + 1); 
} 

vous donnera une énorme accélération.