Structure des données et algorithmes - Traversée des arbres

La traversée est un processus permettant de visiter tous les nœuds d'un arbre et peut également imprimer leurs valeurs. Parce que tous les nœuds sont connectés via des bords (liens), nous partons toujours du nœud racine (tête). Autrement dit, nous ne pouvons pas accéder de manière aléatoire à un nœud dans un arbre. Il y a trois façons que nous utilisons pour traverser un arbre -

• Traversée en ordre
• Précommander Traversal
• Traversée post-commande

Généralement, nous parcourons une arborescence pour rechercher ou localiser un élément ou une clé donné dans l'arborescence ou pour imprimer toutes les valeurs qu'il contient.

Traversée en ordre

Dans cette méthode de traversée, le sous-arbre gauche est visité en premier, puis la racine et plus tard le sous-arbre droit. Nous devons toujours nous rappeler que chaque nœud peut représenter un sous-arbre lui-même.

Si un arbre binaire est parcouru in-order, la sortie produira des valeurs de clé triées dans un ordre croissant.

Nous partons de A, et en suivant le parcours dans l'ordre, nous nous déplaçons vers son sous-arbre gauche B. Best également parcouru dans l'ordre. Le processus se poursuit jusqu'à ce que tous les nœuds soient visités. La sortie de la traversée en ordre de cet arbre sera -

D → B → E → A → F → C → G

Algorithme

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Visit root node.
Step 3 − Recursively traverse right subtree.

Précommander Traversal

Dans cette méthode de traversée, le nœud racine est visité en premier, puis le sous-arbre gauche et enfin le sous-arbre droit.

Nous partons de A, et après la traversée de pré-commande, nous visitons d'abord A lui-même, puis passez à son sous-arbre gauche B. Best également parcouru en pré-commande. Le processus se poursuit jusqu'à ce que tous les nœuds soient visités. La sortie de la traversée de pré-ordre de cet arbre sera -

A → B → D → E → C → F → G

Algorithme

Until all nodes are traversed −
Step 1 − Visit root node.
Step 2 − Recursively traverse left subtree.
Step 3 − Recursively traverse right subtree.

Traversée post-commande

Dans cette méthode de traversée, le nœud racine est visité en dernier, d'où le nom. Nous traversons d'abord le sous-arbre gauche, puis le sous-arbre droit et enfin le nœud racine.

Nous partons de A, et après le parcours post-ordre, nous visitons d'abord le sous-arbre de gauche B. Best également traversée après la commande. Le processus se poursuit jusqu'à ce que tous les nœuds soient visités. La sortie du parcours post-ordre de cet arbre sera -

D → E → B → F → G → C → A

Algorithme

Until all nodes are traversed −
Step 1 − Recursively traverse left subtree.
Step 2 − Recursively traverse right subtree.
Step 3 − Visit root node.

Pour vérifier l'implémentation en C de la traversée d'arbres, veuillez cliquer ici .