Les méthodes de traversée des arbres sont des techniques utilisées pour visiter systématiquement tous les nœuds dans une structure de données arborescentes. Comprendre ces méthodes est essentiel pour diverses applications telles que la recherche, le tri et l'évaluation de l'expression.

Précommande Traversal

Le précommandement traverse le nœud racinaire d'abord, puis le sous-arbre gauche est récursivement traversé, suivi du sous-arbre droit. Cette méthode est utile pour copier des arbres ou créer des expressions préfixes.

Par exemple, étant donné l'arbre:


/
B C
/
D E F

La séquence de passage précommande est : A, B, D, E, C, F.

Inorder Traversal

Inorder traversal visite le sous-arbre gauche d'abord, puis le noeud racine, et enfin le sous-arbre droit. Cette méthode est couramment utilisée pour les arbres de recherche binaire pour récupérer les données dans l'ordre trié.

En utilisant le même arbre, la séquence de traversée de l'ordre est : D, B, E, A, C, F.

Traverse de la poste

La traversée de la postorder visitait le sous-arbre gauche, puis le sous-arbre droit, et enfin le nœud racine. Cette approche est utile pour supprimer les arbres ou évaluer les expressions postfixes.

Pour l'arbre d'exemple, la séquence de traversée postcommande est : D, E, B, F, C, A.

Calculs pratiques

Considérez l'arbre:

1
/
2 3
/
4 5 6

Transbordement précommande: 1, 2, 4, 5, 3, 6

Traversée en ordre: 4, 2, 5, 1, 3, 6

Transbordement de la poste: 4, 5, 2, 6, 3, 1