Explorer la traversée d'arbres en JavaScript : Inorder, Preorder et Postorder avec des exemples

La traversée d'arbres est un concept fondamental en informatique qui consiste à visiter systématiquement chaque nœud d'une structure de données arborescente. Grâce à la traversée d'arbres, nous pouvons traiter les nœuds dans un ordre prédéterminé, facilitant les opérations telles que la recherche, le tri et l'évaluation des expressions.

Dans cet article, nous allons explorer trois des méthodes de parcours d'arbres les plus utilisées : inorder, preorder et postorder.

Grâce à des exemples clairs et concis implémentés en JavaScript, vous acquerrez une solide compréhension de ces techniques de traversée.

Définition de l'arborescence

Avant de plonger dans les algorithmes de parcours d'arbre, définissons la structure que nous utiliserons pour l'arbre binaire. L'arborescence sera composée de nœuds, où chaque nœud contient une valeur et des références à ses nœuds enfants gauche et droit.

 function TreeNode(val = 0, left = null, right = null) { this.val = val; this.left = left; this.right = right; }

Maintenant que nous avons défini la structure arborescente, nous pouvons continuer à explorer les trois méthodes de parcours d'arbre.

Parcours dans l'ordre

La traversée dans l'ordre suit le modèle suivant de visite des nœuds dans un arbre binaire - l'algorithme traverse d'abord le sous-arbre gauche, puis visite le nœud actuel et traverse enfin le sous-arbre droit. Cela garantit que les nœuds sont visités dans l'ordre croissant si l'arbre représente une structure de données triée.

 A / \ BC / \ / \ DEFG // Inorder traversal result: D -> B -> E -> A -> F -> C -> G

Traversée récursive dans l'ordre

1. Vérifiez si le nœud actuel est nul. Si oui, reviens.

   
   

2. Appelez récursivement la fonction sur le sous-arbre de gauche.

   
   

3. Visitez le nœud actuel.

   
   

4. Appelez récursivement la fonction sur le sous-arbre de droite.

 function inorderRecursive(tree) { const result = []; function inorderTraverse(node) { if (!node) return; inorderTraverse(node.left); result.push(node.val); inorderTraverse(node.right); } inorderTraverse(tree); return result; }

Traversée d'ordre non récursif

1. Initialisez une pile vide et définissez le nœud actuel sur la racine de l'arborescence.

   
   

2. Itérer tant que la pile n'est pas vide ou que le nœud actuel n'est pas nul.

   • Poussez tous les nœuds de gauche sur la pile jusqu'à atteindre un enfant gauche nul.

   • Extrayez un nœud de la pile, visitez-le et définissez le nœud actuel sur son enfant droit.

     
     

3. Répétez l'étape 2 jusqu'à ce que la pile soit vide et que le nœud actuel soit nul.

 function inorderRecursive(tree) { const stack = []; const result = []; let currentNode = tree; while (currentNode || stack.length) { while (currentNode) { stack.push(currentNode); currentNode = currentNode.left; } const node = stack.pop(); result.push(node.val); currentNode = node.right; } return result; }

Traversée de précommande

Dans la traversée de préordre, l'algorithme visite d'abord le nœud actuel, puis traverse le sous-arbre gauche et traverse enfin le sous-arbre droit. Cet ordre garantit que les nœuds sont visités de manière "descendante", en partant de la racine et en se déplaçant vers les feuilles.

 A / \ BC / \ / \ DEFG // Preorder traversal result: A -> B -> D -> E -> C -> F -> G

Traversée de précommande récursive

1. Vérifiez si le nœud actuel est nul. Si oui, reviens.

   
   

2. Visitez le nœud actuel.

   
   

3. Appelez récursivement la fonction sur le sous-arbre de gauche.

   
   

4. Appelez récursivement la fonction sur le sous-arbre de droite.

   
   

 function preorderRecursive(tree) { const result = []; function preorderTraverse(node) { if (!node) return; result.push(node.val); preorderTraverse(node.left); preorderTraverse(node.right); } preorderTraverse(tree); return result; }

Traversée de précommande non récursive

1. Commencez avec une pile vide et poussez le nœud racine sur la pile.

   
   

2. Initialisez un tableau vide pour stocker le résultat du parcours de préordre.

   
   

3. Entrez une boucle while qui s'exécute jusqu'à ce que la pile soit vide.

   
   

4. Extrayez un nœud de la pile et visitez-le en ajoutant sa valeur au tableau de résultats.

   
   

5. Si le nœud a un enfant droit, poussez l'enfant droit sur la pile.

   
   

6. Si le nœud a un enfant gauche, poussez l'enfant gauche sur la pile.

   
   

7. Répétez les étapes 3 à 6 jusqu'à ce que la pile soit vide.

 function preorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack.pop(); result.push(node.val); if (node.right) stack.push(node.right); if (node.left) stack.push(node.left); } return result; }

Traversée de post-commande

Dans ce parcours, l'algorithme parcourt d'abord le sous-arbre gauche, puis le sous-arbre droit, et visite enfin le nœud actuel. Cet ordre garantit que les nœuds sont visités de manière "ascendante", en partant des feuilles et en se déplaçant vers la racine.

 A / \ BC / \ / \ DEFG // Postorder traversal result: D -> E -> B -> F -> G -> C -> A

Traversée post-ordre récursive

1. Vérifiez si le nœud actuel est nul. Si oui, reviens.

   
   

2. Appelez récursivement la fonction sur le sous-arbre de gauche.

   
   

3. Appelez récursivement la fonction sur le sous-arbre de droite.

   
   

4. Visitez le nœud actuel.

 function postorderRecursive(tree) { const result = []; function postorderTraverse(node) { if (!node) return; postorderTraverse(node.left); postorderTraverse(node.right); result.push(node.val); } postorderTraverse(tree); return result; }

Traversée de post-ordre non récursive

1. Commencez avec une pile vide et poussez le nœud racine sur la pile.

   
   

2. Initialisez un tableau vide pour stocker le résultat de la traversée post-ordre.

   
   

3. Entrez une boucle while qui s'exécute jusqu'à ce que la pile soit vide.

   
   

4. Obtenez le nœud supérieur de la pile (sans le supprimer).

   
   

5. Si le nœud a un enfant gauche, poussez l'enfant gauche sur la pile et définissez l'enfant gauche du nœud actuel sur null.

   
   

6. Si le nœud a un enfant droit, poussez l'enfant droit sur la pile et définissez l'enfant droit du nœud actuel sur null.

   
   

7. Si le nœud n'a ni enfant gauche ni droit, il s'agit d'un nœud feuille. Extrayez le nœud de la pile et ajoutez sa valeur au tableau de résultats.

   
   

8. Répétez les étapes 4 à 7 jusqu'à ce que la pile soit vide.

 function postorderTraversal(root) { if (!root) return []; const stack = [root]; const result = []; while (stack.length) { const node = stack[stack.length - 1]; if (node.left) { stack.push(node.left); node.left = null; } else if (node.right) { stack.push(node.right); node.right = null; } else { result.push(stack.pop().val); } } return result; }

Conclusion

J'espère que vous avez maintenant une compréhension claire des différences entre la traversée inorder, preorder et postorder en JavaScript. Avec les connaissances et les exemples fournis, vous êtes maintenant équipé pour appliquer efficacement ces techniques à vos propres tâches et projets.