algorithme récursif pour arbre

Question

Duplicate possible:
the # of internal nodes

Je prends cours qui est la structure de données dans CS. J'ai cette question qui demande un algorithme récursif qui détermine la hauteur de l'arbre en fonction du ROOT NODE de l'arbre. Je vais vous expliquer ce qui est l'arbre et le noeud racine:

        root 
           /\ 
        internal node internal node 
         /\     \ 
      external node internal node  external node 
           /    
          external node 

ce que je l'ai fait jusqu'à présent est:

entrée
• : int r (r = le nœud racine) T est l'arbre
• sortie: int h (h = la hauteur de l'arbre)

• hauteur (T, R):

• si r est un noeud racine de T, puis

• retour 1
• autre
• h < --- 1
• pour chaque enfant de w r en T faire
• h < --- max (h, hauteur (T, w))

• retour 1 + h

que ce que je reçois jusqu'à présent ....

Answer 1

Puisqu'il s'agit de devoirs, je ne veux pas donner la solution, mais voici un indice utile. Concentrez-vous sur le sommet de l'arbre, avec votre nœud racine et les enfants juste en dessous. Si vous connaissez les hauteurs des sous-arbres, comment cela vous aide-t-il à calculer la hauteur de l'arbre parent?

Dans l'exemple que vous avez donné, imaginez que vous connaissiez les hauteurs (marquée avec [crochets]) des sous-arbres et voulait trouver la hauteur de l'arbre racine:

       root[?] 
          /\ 
       internal node[3] internal node[2] 
        /\     \ 
     external node internal node  external node 
          /    
         external node 

Une autre astuce est que votre code aura la structure suivante, qui est commune à recursive programs. Vous aurez un cas de base puis une étape inductive dans laquelle vous représentez votre problème en termes de sous-problèmes plus petits.

int height(Node root) { 
    // The base case is that the node has no children, so it is a tree of height 1. 
    if (root has no children) return 1; 

    // Otherwise, apply the hint from above. Remember, you can call this height() 
    // function on the children of the root! 
}