Dans ce didacticiel, vous découvrirez différentes techniques de traversée d'arbres. En outre, vous trouverez des exemples de travail de différentes méthodes de traversée d'arbres en C, C ++, Java et Python.
Traverser un arbre signifie visiter chaque nœud de l'arbre. Vous pouvez, par exemple, vouloir ajouter toutes les valeurs de l'arborescence ou trouver la plus grande. Pour toutes ces opérations, vous devrez visiter chaque nœud de l'arbre.
Les structures de données linéaires telles que les tableaux, les piles, les files d'attente et les listes liées n'ont qu'un seul moyen de lire les données. Mais une structure de données hiérarchique comme un arbre peut être traversée de différentes manières.
Traversée d'arbre
Réfléchissons à la façon dont nous pouvons lire les éléments de l'arbre dans l'image ci-dessus.
En partant du haut, de gauche à droite
1 -> 12 -> 5 -> 6 -> 9
En partant du bas, de gauche à droite
5 -> 6 -> 12 -> 9 -> 1
Bien que ce processus soit assez simple, il ne respecte pas la hiérarchie de l'arbre, seulement la profondeur des nœuds.
Au lieu de cela, nous utilisons des méthodes de parcours qui prennent en compte la structure de base d'un arbre ie
struct node ( int data; struct node* left; struct node* right; )
Le nœud de structure pointé par left et right peut avoir d'autres enfants de gauche et de droite, nous devrions donc les considérer comme des sous-arbres au lieu de sous-nœuds.
Selon cette structure, chaque arbre est une combinaison de
- Un nœud transportant des données
- Deux sous-arbres
Sous-arborescence gauche et droite
N'oubliez pas que notre objectif est de visiter chaque nœud, nous devons donc visiter tous les nœuds du sous-arbre, visiter le nœud racine et visiter également tous les nœuds du sous-arbre approprié.
Selon l'ordre dans lequel nous faisons cela, il peut y avoir trois types de parcours.
Traversée en ordre
- Tout d'abord, visitez tous les nœuds du sous-arbre de gauche
- Puis le nœud racine
- Visitez tous les nœuds dans le bon sous-arbre
inorder(root->left) display(root->data) inorder(root->right)
Parcours de précommande
- Visiter le nœud racine
- Visitez tous les nœuds dans le sous-arbre de gauche
- Visitez tous les nœuds dans le bon sous-arbre
display(root->data) preorder(root->left) preorder(root->right)
Traversée post-commande
- Visitez tous les nœuds dans le sous-arbre de gauche
- Visitez tous les nœuds dans le bon sous-arbre
- Visitez le nœud racine
postorder(root->left) postorder(root->right) display(root->data)
Visualisons le parcours dans l'ordre. Nous partons du nœud racine.
Sous-arborescence gauche et droite
Nous traversons d'abord le sous-arbre gauche. Nous devons également nous rappeler de visiter le nœud racine et le bon sous-arbre lorsque cet arbre est terminé.
Mettons tout cela dans une pile pour que nous nous souvenions.
Empiler
Maintenant, nous traversons le sous-arbre pointé sur le HAUT de la pile.
Encore une fois, nous suivons la même règle d'inorder
Sous-arbre gauche -> racine -> sous-arbre droit
Après avoir traversé le sous-arbre de gauche, il nous reste
Pile finale
Puisque le nœud "5" n'a pas de sous-arborescences, nous l'imprimons directement. Après cela, nous imprimons son parent "12" puis le bon enfant "6".
Tout mettre sur une pile a été utile car maintenant que le sous-arbre gauche du nœud racine a été traversé, nous pouvons l'imprimer et aller au sous-arbre droit.
Après avoir parcouru tous les éléments, nous obtenons la traversée en ordre comme
5 -> 12 -> 6 -> 1 -> 9
Nous n'avons pas à créer la pile nous-mêmes car la récursivité maintient le bon ordre pour nous.
Exemples Python, Java et C / C ++
Python Java C C + # Tree traversal in Python class Node: def __init__(self, item): self.left = None self.right = None self.val = item def inorder(root): if root: # Traverse left inorder(root.left) # Traverse root print(str(root.val) + "->", end='') # Traverse right inorder(root.right) def postorder(root): if root: # Traverse left postorder(root.left) # Traverse right postorder(root.right) # Traverse root print(str(root.val) + "->", end='') def preorder(root): if root: # Traverse root print(str(root.val) + "->", end='') # Traverse left preorder(root.left) # Traverse right preorder(root.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) print("Inorder traversal ") inorder(root) print("Preorder traversal ") preorder(root) print("Postorder traversal ") postorder(root)
// Tree traversal in Java class Node ( int item; Node left, right; public Node(int key) ( item = key; left = right = null; ) ) class BinaryTree ( // Root of Binary Tree Node root; BinaryTree() ( root = null; ) void postorder(Node node) ( if (node == null) return; // Traverse left postorder(node.left); // Traverse right postorder(node.right); // Traverse root System.out.print(node.item + "->"); ) void inorder(Node node) ( if (node == null) return; // Traverse left inorder(node.left); // Traverse root System.out.print(node.item + "->"); // Traverse right inorder(node.right); ) void preorder(Node node) ( if (node == null) return; // Traverse root System.out.print(node.item + "->"); // Traverse left preorder(node.left); // Traverse right preorder(node.right); ) public static void main(String() args) ( BinaryTree tree = new BinaryTree(); tree.root = new Node(1); tree.root.left = new Node(12); tree.root.right = new Node(9); tree.root.left.left = new Node(5); tree.root.left.right = new Node(6); System.out.println("Inorder traversal"); tree.inorder(tree.root); System.out.println("Preorder traversal "); tree.preorder(tree.root); System.out.println("Postorder traversal"); tree.postorder(tree.root); ) )
// Tree traversal in C #include #include struct node ( int item; struct node* left; struct node* right; ); // Inorder traversal void inorderTraversal(struct node* root) ( if (root == NULL) return; inorderTraversal(root->left); printf("%d ->", root->item); inorderTraversal(root->right); ) // preorderTraversal traversal void preorderTraversal(struct node* root) ( if (root == NULL) return; printf("%d ->", root->item); preorderTraversal(root->left); preorderTraversal(root->right); ) // postorderTraversal traversal void postorderTraversal(struct node* root) ( if (root == NULL) return; postorderTraversal(root->left); postorderTraversal(root->right); printf("%d ->", root->item); ) // Create a new Node struct node* createNode(value) ( struct node* newNode = malloc(sizeof(struct node)); newNode->item = value; newNode->left = NULL; newNode->right = NULL; return newNode; ) // Insert on the left of the node struct node* insertLeft(struct node* root, int value) ( root->left = createNode(value); return root->left; ) // Insert on the right of the node struct node* insertRight(struct node* root, int value) ( root->right = createNode(value); return root->right; ) int main() ( struct node* root = createNode(1); insertLeft(root, 12); insertRight(root, 9); insertLeft(root->left, 5); insertRight(root->left, 6); printf("Inorder traversal "); inorderTraversal(root); printf("Preorder traversal "); preorderTraversal(root); printf("Postorder traversal "); postorderTraversal(root); )
// Tree traversal in C++ #include using namespace std; struct Node ( int data; struct Node *left, *right; Node(int data) ( this->data = data; left = right = NULL; ) ); // Preorder traversal void preorderTraversal(struct Node* node) ( if (node == NULL) return; cout left); preorderTraversal(node->right); ) // Postorder traversal void postorderTraversal(struct Node* node) ( if (node == NULL) return; postorderTraversal(node->left); postorderTraversal(node->right); cout left); cout right); ) int main() ( struct Node* root = new Node(1); root->left = new Node(12); root->right = new Node(9); root->left->left = new Node(5); root->left->right = new Node(6); cout << "Inorder traversal "; inorderTraversal(root); cout << "Preorder traversal "; preorderTraversal(root); cout << "Postorder traversal "; postorderTraversal(root);
