Parcours dans l'ordre est défini comme un type de technique de traversée d'arbre qui suit le modèle Gauche-Racine-Droite, tel que :
- Le sous-arbre de gauche est parcouru en premier
- Ensuite, le nœud racine de ce sous-arbre est parcouru
- Enfin, le sous-arbre droit est parcouru
Parcours dans l'ordre
Algorithme pour la traversée en ordre de l'arbre binaire
L'algorithme de parcours dans l'ordre est présenté comme suit :
Dans l'ordre (racine) :
- Suivez les étapes 2 à 4 jusqu'à ce que root != NULL
- Dans l'ordre (racine -> gauche)
- Écrire racine -> données
- Dans l'ordre (racine -> droite)
- Fin de la boucle
Comment fonctionne la traversée en ordre de l'arbre binaire ?
Considérons l'arbre suivant :
Exemple d'arbre binaire
Si nous effectuons un parcours dans l’ordre dans cet arbre binaire, alors le parcours sera le suivant :
Étape 1: Le parcours ira de 1 à son sous-arbre gauche, c'est-à-dire 2, puis de 2 à la racine de son sous-arbre gauche, c'est-à-dire 4. Maintenant, 4 n'a plus de sous-arbre gauche, il sera donc visité. Il n’a pas non plus de sous-arbre droit. Donc plus de traversée à partir de 4
Le nœud 4 est visité
Étape 2: Comme le sous-arbre gauche de 2 est visité complètement, il lit désormais les données du nœud 2 avant de passer à son sous-arbre droit.
Le nœud 2 est visité
Étape 3: Maintenant, le sous-arbre droit de 2 sera parcouru, c'est-à-dire passer au nœud 5. Pour le nœud 5, il n'y a pas de sous-arbre gauche, il est donc visité et après cela, le parcours revient car il n'y a pas de sous-arbre droit du nœud 5.
Le nœud 5 est visité
Étape 4: Comme le sous-arbre gauche du nœud 1 est, la racine elle-même, c'est-à-dire le nœud 1, sera visitée.
Le nœud 1 est visité
Étape 5 : Le sous-arbre gauche du nœud 1 et le nœud lui-même sont visités. Alors maintenant, le sous-arbre droit de 1 sera parcouru, c'est-à-dire passer au nœud 3. Comme le nœud 3 n'a pas de sous-arbre gauche, il sera visité.
Le nœud 3 est visité
Étape 6 : Le sous-arbre gauche du nœud 3 et le nœud lui-même sont visités. Traversez donc vers le sous-arbre droit et visitez le nœud 6. Maintenant, le parcours se termine lorsque tous les nœuds sont traversés.
L'arbre complet est parcouru
L’ordre de parcours des nœuds est donc 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Programme pour implémenter la traversée en ordre de l'arbre binaire :
Vous trouverez ci-dessous l'implémentation du code du parcours inorder :
C++
// C++ program for inorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> >int> data;> >struct> Node *left, *right;> >Node(>int> v)> >{> >data = v;> >left = right = NULL;> >}> };> // Function to print inorder traversal> void> printInorder(>struct> Node* node)> {> >if> (node == NULL)> >return>;> >// First recur on left subtree> >printInorder(node->à gauche);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->droite); } // Code du pilote int main() { struct Node* root = new Node(1); racine->gauche = new Node(2); racine->droite = new Node(3); racine->gauche->gauche = new Node(4); racine->gauche->droite = new Node(5); racine->droite->droite = new Node(6); // Appel de fonction cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
// Java program for inorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> >int> data;> >Node left, right;> >Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Main class> class> GFG {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >System.out.print(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> main(String[] args)> >{> >Node root =>new> Node(>1>);> >root.left =>new> Node(>2>);> >root.right =>new> Node(>3>);> >root.left.left =>new> Node(>4>);> >root.left.right =>new> Node(>5>);> >root.right.right =>new> Node(>6>);> >// Function call> >System.out.println(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> // This code is contributed by prasad264> |
>
>
Python3
# Structure of a Binary Tree Node> class> Node:> >def> __init__(>self>, v):> >self>.data>=> v> >self>.left>=> None> >self>.right>=> None> # Function to print inorder traversal> def> printInorder(node):> >if> node>is> None>:> >return> ># First recur on left subtree> >printInorder(node.left)> ># Now deal with the node> >print>(node.data, end>=>' '>)> ># Then recur on right subtree> >printInorder(node.right)> # Driver code> if> __name__>=>=> '__main__'>:> >root>=> Node(>1>)> >root.left>=> Node(>2>)> >root.right>=> Node(>3>)> >root.left.left>=> Node(>4>)> >root.left.right>=> Node(>5>)> >root.right.right>=> Node(>6>)> ># Function call> >print>(>'Inorder traversal of binary tree is:'>)> >printInorder(root)> |
>
>
C#
// C# program for inorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> >public> int> data;> >public> Node left, right;> >public> Node(>int> v)> >{> >data = v;> >left = right =>null>;> >}> }> // Class to store and print inorder traversal> public> class> BinaryTree {> >// Function to print inorder traversal> >public> static> void> printInorder(Node node)> >{> >if> (node ==>null>)> >return>;> >// First recur on left subtree> >printInorder(node.left);> >// Now deal with the node> >Console.Write(node.data +>' '>);> >// Then recur on right subtree> >printInorder(node.right);> >}> >// Driver code> >public> static> void> Main()> >{> >Node root =>new> Node(1);> >root.left =>new> Node(2);> >root.right =>new> Node(3);> >root.left.left =>new> Node(4);> >root.left.right =>new> Node(5);> >root.right.right =>new> Node(6);> >// Function call> >Console.WriteLine(> >'Inorder traversal of binary tree is: '>);> >printInorder(root);> >}> }> |
caractère Java en chaîne
>
>
Javascript
// JavaScript program for inorder traversals> // Structure of a Binary Tree Node> class Node {> >constructor(v) {> >this>.data = v;> >this>.left =>null>;> >this>.right =>null>;> >}> }> // Function to print inorder traversal> function> printInorder(node) {> >if> (node ===>null>) {> >return>;> >}> > >// First recur on left subtree> >printInorder(node.left);> > >// Now deal with the node> >console.log(node.data);> > >// Then recur on right subtree> >printInorder(node.right);> }> // Driver code> const root =>new> Node(1);> root.left =>new> Node(2);> root.right =>new> Node(3);> root.left.left =>new> Node(4);> root.left.right =>new> Node(5);> root.right.right =>new> Node(6);> // Function call> console.log(>'Inorder traversal of binary tree is: '>);> printInorder(root);> |
>
>Sortir
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Explication:
Comment fonctionne le parcours dans l'ordre
Analyse de complexité :
Complexité temporelle : O(N) où N est le nombre total de nœuds. Parce qu'il traverse tous les nœuds au moins une fois.
Espace auxiliaire : O(1) si aucun espace de pile de récursion n’est pris en compte. Sinon, O(h) où h est la hauteur de l'arbre
- Au pire des cas, h peut être le même que N (quand l'arbre est un arbre de travers)
- Dans le meilleur des cas, h peut être le même que calme (quand l'arbre est un arbre complet)
Cas d'utilisation de Inorder Traversal :
Dans le cas du BST (Binary Search Tree), si à tout moment il est nécessaire d'obtenir les nœuds dans un ordre non décroissant, le meilleur moyen est d'implémenter un parcours dans l'ordre.
Articles Liés:
- Types de traversées d’arbres
- Parcours itératif dans l'ordre
- Construire un arbre binaire à partir d'un parcours de pré-ordre et d'ordre in-order
- Traversée de Morris pour la traversée en ordre de l'arbre
- Parcours dans l'ordre sans récursion