Une question sur l'obtention du nombre de nœuds dans un arbre binaire

Question

J'ai écrit deux fonctions (pseudo-code) pour calculer le nombre de nœuds et la hauteur de l'arbre d'un arbre binaire, étant donné la racine de l'arbre. Plus important encore, l'arbre binaire est représenté en tant que premier format chiled/next frère.

si

struct TreeNode 
{ 
    Object element; 
    TreeNode *firstChild; 
    TreeNode *nextSibling; 
} 

Calculer le nombre de nœuds:

public int countNode(TreeNode root) 
{ 
    int count=0; 
    while(root!=null) 
    { 
     root= root.firstChild; 
     count++; 
    } 

     return count; 
} 

public int countHeight(TreeNode root) 
{ 
    int height=0; 
    while(root!=null) 
    { 
     root= root.nextSibling; 
     height++; 
    } 

    return height; 

}

C'est l'un des problèmes que j'ai vu sur un livre d'algorithme, et ma solution ci-dessus semble avoir quelques problèmes, aussi je n'ai pas tout à fait compris les points d'utilisation de cette représentation First Brain/First enfant de Binary Tree, pourriez-vous me donner quelques idées et commentaires, s'il vous plaît? À la votre!

Answer 1

L'utilisation des frères et soeurs suivant et premier enfant peut être probablement visualisé comme ceci:

A1 -- A2 -- A3 
|  |  
|  B1 -- B2 -- B3 
|   | 
D1 -- D2 C1 

Les lignes horizontales dans le diagramme représentent nextSibling et les lignes verticales correspondent à la liaison firstChild. Pour certains problèmes, cela peut être une visualisation naturelle (mais pour d'autres problèmes, vous pouvez préférer l'arborescence habituelle avec deux sous-nœuds - ils sont équivalents).

Votre pseudo-code semble manquer quelque chose, car vous ne comptez vraiment rien. Je suppose que vous vouliez avoir count++, respectivement height++ dans la boucle while. Quoi qu'il en soit, pour compter le nombre de nœuds, vous devez ajouter le nombre de nœuds de l'enfant ainsi que le nombre de nœuds au même niveau (frères et sœurs). Pour les arbres assez petits, cela peut être fait de manière récursive:

public int countNode(TreeNode root) { 
    if (root == null) return 0; 
    return 1 + countNodes(root.firstChild) 
      + countNodes(root.nextSibling); 
} 

Pour les structures de données plus importantes, vous aurez besoin de stocker les noeuds « à traiter » dans une pile en mémoire pour éviter tout débordement de pile (sic!)

Pour compter la hauteur, vous devez d'abord décider comment la hauteur est définie. Est-ce le chemin lorsque vous suivez les liens firstChild (c'est A1 -> D1) ou voulez-vous le plus long chemin dans l'arbre (n'importe où) (ce qui serait A1 -> A2 -> B1 -> B2 -> C1). Dans le premier cas, votre implémentation serait correcte. Dans le second cas, vous auriez besoin d'une fonction récursive similaire à celle des noeuds de comptage (au lieu d'ajouter, vous choisiriez le sous-arbre plus grand).

Answer 2

Bien que littéralement correct, «premier enfant» et «frère droit» peuvent être un peu confus. Si vous remplacez ceux avec «enfant gauche» et «enfant droit», je pense que vous serez en mesure de le comprendre un peu mieux.

Answer 3

Pour comprendre la récurrence, il faut d'abord comprendre la récursivité.

public int countNode(TreeNode root) 
{ 
    if (root==null) { 
     return 0; 
    } else { 
     return countNode(root.firstChild) + countNode(root.nextSibling) + 1; 
    } 
} 

public int countHeight(TreeNode root) 
{ 
    if (root==null) { 
     return 0; 
    } else { 
     return max(countHeight(root.firstChild), 
        countHeight(root.nextSibling)) + 1; 
    } 
} 

Si l'arbre est nul, il ne contient aucun noeud et n'a pas de hauteur.

Si l'arbre n'est pas nul, il est supérieur d'un noeud à son sous-arbre plus grand et contient tous les nœuds des deux sous-arbres, plus le nœud qui contient les deux sous-arbres.

Lisez le livre de Dave Touretzky sur LISP.Dave enseigne la récursivité en utilisant des histoires de dragon, et le dragon est en fait un bon professeur.