TRAVERSÉE DANS L'ORDRE DE L'ARBRE BINAIRE

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);> > }> }>

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