Traversées d'arbres (ordre, précommande et postcommande) avec exemples
Sarah Chen
Qu’est-ce que la traversée d’arbres ?
Dans la structure de données arborescente, la traversée signifie visiter les nœuds d'une manière spécifique. Il existe des types de traversées de nœuds2. Généralement, ce type de parcours est basé sur l'arbre binaire. Un arbre binaire signifie que chaque nœud peut avoir un maximum de 2 nœuds.
Un arbre binaire est une structure de données bien connue. Il existe également un arbre de recherche binaire (BST). Ce type de parcours est utilisé à diverses fins. Le parcours par ordre de niveau, il est utilisé pour calculer la profondeur entre deux nœuds. Il existe un autre type d'arbre appelé « AVL », dans lequel il est nécessaire de calculer la hauteur d'un nœud. Nous pouvons représenter un arbre binaire dans le tableau, mais pour optimiser la mémoire, nous utiliserons une structure et un pointeur pour référencer le nœud suivant.
Types de traversée d’arbres
Comme nous l'avons discuté arbres binaires, nous discutons maintenant des différents types de traversées. Selon les types, il existe deux types de parcours. Nous avons mentionné précédemment la nécessité d'un ordre de niveau ou d'une traversée en largeur. Maintenant Traversée en profondeur d'abord comme l'ordre de publication est utilisé pour la suppression d'un nœud (nous en discuterons plus tard), la précommande est utilisée pour copier un arbre binaire et « inorder » parcourra l'arbre de manière non décroissante.
- Traversée en largeur d'abord
- Traversée en profondeur d'abord
- Parcours de pré-commande
- Traversée post-commande
- Traversée dans l'ordre
Traversée en largeur d'abord
C'est également connu sous le nom de parcours par ordre de niveau. Considérons l'arbre suivant pour démontrer le parcours par ordre de niveau.
Nous allons donc partir du nœud racine « 1 ». Il sera marqué comme niveau 1. Ensuite, l'algorithme ira à tous les enfants du nœud actuel. Nous allons visiter les nœuds 2 et 3 maintenant. Ils seront marqués au niveau 2.
Après cela, comme nous avons 2 nœuds au niveau 2, nous rendrons également visite à leurs enfants. Nous allons donc visiter 5,6,8,7 et les marquer comme niveau 3. Voici une chose sans mention,
Niveau du nœud = niveau du nœud parent + 1
Niveau 1 : 1
Niveau 2 : 2 3
Niveau 3 : 5 6 8 7
Un algorithme similaire est utilisé pour le BFS (Recherche en largeur d'abord).
Voici le pseudocode pour le parcours de l'ordre des niveaux :
level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
current_node = Q.pop()
print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
Q.push(current_node.left)
if current_node.right is not NULL:
Q.push(current_node.right)
Arbre de Bianry traversant dans l'ordre
Prenons le même exemple que précédemment. Dans ce type de parcours, nous visitons d’abord le sous-arbre de gauche, puis la racine et enfin le sous-arbre de droite. Pour faciliter la mémorisation, nous pouvons dire que l'ordre va comme gauche-racine-droite.
Pour l’arbre entier, disons que la racine est 1. Maintenant l’algorithme suivra :
- Visitez le sous-arbre gauche du nœud 1.
- Le nœud actuel est 2 (car c'est le sous-arbre gauche de 1)
- Visitez le sous-arbre gauche de 2. Le nœud actuel sera 5 cette fois.
- En passant à 5, il n'a pas d'enfants, donc le nœud 5 sera marqué comme visité. Il reviendra au nœud parent ; qui vaut 2.
- Comme le sous-arbre gauche de 2 est visité, 2 sera désormais également visité.
- Vue d'ensemble algorithme déplacera le nœud actuel vers le sous-arbre droit du nœud 2, qui est le nœud 6. Après avoir visité le nœud 6. Il se déplacera vers son nœud parent 2.
- Au fur et à mesure que le nœud 2 est visité, nous allons maintenant visiter le parent de 2 ; qui est le nœud 1.
- Après cela, nous visiterons le bon sous-arbre.
Le parcours final ressemblera donc à ceci :
Dans l'ordre : 5 → 2 → 6 → 1 → 8 → 3 → 7
Voici le pseudocode pour le parcours dans l'ordre :
InOrder(node):
if node is not null:
InOrder(node.left)
print node.value
InOrder(node.right)
Il s'agit de l'algorithme récursif pour le parcours dans l'ordre. Pour le Arbre de recherche binaire (BST), Le parcours dans l'ordre donne le tableau de valeurs triées.
Traversée post-commande
Dans ce parcours, nous traverserons d'abord le sous-arbre le plus à gauche, puis le sous-arbre le plus à droite après la racine. Toutes les traversées seront en Post-Order. Montrons un exemple :
Ici pour root = 1,
- Nous allons d'abord passer au sous-arbre de gauche. La racine deviendra donc 2.
- Ensuite, 2 a quitté le sous-arbre, nous allons donc passer au nœud 5. Maintenant, la racine est 5.
- Il n’a pas de sous-arbre gauche, ni de sous-arbre droit. Nous allons donc maintenant marquer le nœud 5 comme visité et passer à son nœud parent.
- Maintenant, la racine est 2 et son sous-arbre gauche est complètement visité. Nous allons maintenant passer à son sous-arbre droit. La racine devient donc 6.
- Comme le nœud 6 n'a pas de sous-arbre gauche et droit, nous marquerons le nœud 6 visité et passerons à son nœud parent 2.
- Désormais, les sous-arbres gauche et droit sont visités pour le nœud 2. Il sera également marqué comme visité.
- Nous allons passer au parent du nœud 2, qui est le nœud 1.
- Le sous-arbre de gauche est visité pour la racine 1. De la même manière, nous allons visiter le sous-arbre de droite.
Le cercle marqué est le sous-arbre de droite. Nous allons maintenant visiter le sous-arbre de droite comme nous avons visité le sous-arbre de gauche. Après cela, nous visiterons le nœud. Le parcours final sera donc :
Post-commande : 5 → 6 → 2 → 8 → 7 → 3 → 1
Voici le pseudocode pour le parcours post-commande :
PostOrder(node):
if node is not null:
PostOrder(node.left)
PostOrder(node.right)
print node.value
Précommande Traversal
Pour le parcours de précommande, l'algorithme visitera d'abord le nœud racine, après quoi il se déplacera respectivement vers les sous-arbres gauche et droit. Pour faciliter la compréhension, nous pouvons penser à des visites de parcours de précommande comme racine → gauche-droite.
Alors, sélectionnons le nœud 1 comme racine.
- Selon l'algorithme, la racine sera découverte en premier, puis le sous-arbre gauche et enfin le sous-arbre droit.
- Nous allons donc visiter la racine 1. Ensuite, nous passerons à son sous-arbre gauche. La racine devient 2.
- Nous allons visiter le nœud 2 et passer à son sous-arbre gauche. La racine devient donc 3.
- On visite le nœud 3, puis on passe à son nœud parent. Maintenant, le nœud 2 et son sous-arbre gauche sont visités. Il est temps de visiter le bon sous-arbre.
- Nous allons passer au sous-arbre de droite, la racine devient 4. Nous visiterons 4. Comme 4 n'a pas de nœud enfant, nous passerons à son parent.
- Maintenant, la racine est 2 et elle est visitée avec ses sous-arbres gauche et droit. Nous allons donc passer à son nœud parent. Maintenant, la racine devient 1.
- De même, nous visiterons le sous-arbre de droite.
Précommande : 1 → 2 → 3 → 4 → 5 → 6 → 7
Voici le pseudocode pour le parcours post-commande :
PreOrder(node):
if node is not null:
print node.value
PreOrder(node.left)
PreOrder(node.right)
Mise en œuvre dans Python
class Node:
def __init__(self, item):
self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
if root:
postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
if root:
print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
queue = list()
queue.append(root)
while len(queue) & gt;
0:
current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
queue.append(current.left)
if current.right:
queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)
Sortie :
LevelOrder traversal: 1 2 3 4 5 6 7 Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1
Implémentation en C
#include <stdio.h>
#include <stdlib.h>
struct node {
int value;
struct node* left;
struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
if (root == NULL) return;
InOrder(root->left);
printf("%d ", root->value);
InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
if (root == NULL) return;
printf("%d ", root->value);
PreOrder(root->left);
PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
if (root == NULL) return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
struct node* newNode = malloc(sizeof(struct node));
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
struct node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Inorder traversal:\t");
InOrder(root);
printf("\PreOrder traversal:\t");
PreOrder(root);
printf("\nPostOrder traversal:\t");
PostOrder(root);
}
Production:
Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1
Implémentation de C++ (En utilisant std:queue pour l'ordre des niveaux)
#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
int value;
struct node* left;
struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
if (root == NULL) return;
InOrder(root->left);
printf("%d ", root->value);
InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
if (root == NULL) return;
printf("%d ", root->value);
PreOrder(root->left);
PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
if (root == NULL) return;
PostOrder(root->left);
PostOrder(root->right);
printf("%d ", root->value);
}
void LevelOrder(struct node* root){
std::queue<struct node*> Q;
Q.push(root);
while(!Q.empty()){
struct node* current = Q.front();
Q.pop();
printf("%d ",current->value);
if(current->left)
Q.push(current->left);
if(current->right)
Q.push(current->right);
}
}
// Create a new Node
struct node* createNode(int value) {
struct node* newNode = new node();
newNode->value = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
int main() {
struct node* root = createNode(1);
root->left = createNode(2);
root->right = createNode(3);
root->left->left = createNode(4);
root->left->right = createNode(5);
root->right->left = createNode(6);
root->right->right = createNode(7);
printf("Level Order traversal:\t");
LevelOrder(root);
printf("\nInorder traversal:\t");
InOrder(root);
printf("\nPreOrder traversal:\t");
PreOrder(root);
printf("\nPostOrder traversal:\t");
PostOrder(root);
}
LevelOrder traversal: 1 2 3 4 5 6 7 Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1
