Dans cet article, nous discuterons du parcours inverse dans la structure des données.
Si nous voulons parcourir les nœuds dans l’ordre croissant, alors nous utilisons le parcours dans l’ordre. Voici les étapes requises pour le parcours dans l'ordre :
- Visitez tous les nœuds du sous-arbre de gauche
- Visitez le nœud racine
- Visitez tous les nœuds du sous-arbre de droite
Les structures de données linéaires telles que la pile, le tableau, la file d'attente, etc. n'ont qu'un seul moyen de parcourir les données. Mais dans les structures de données hiérarchiques telles que arbre, il existe plusieurs façons de parcourir les données. Ici, nous allons discuter d'une autre façon de parcourir la structure de données arborescente, c'est-à-dire le parcours dans l'ordre.
Il existe deux approches utilisées pour le parcours dans l'ordre :
- Parcours dans l'ordre utilisant la récursivité
- Parcours dans l'ordre à l'aide d'une méthode itérative
Une technique de parcours dans l'ordre suit le Racine gauche droite politique. Ici, Left Root Right signifie que le sous-arbre gauche du nœud racine est traversé en premier, puis le nœud racine, puis le sous-arbre droit du nœud racine est traversé. Ici, le nom de l'ordre lui-même suggère que le nœud racine se situe entre les sous-arbres gauche et droit.
Nous discuterons du parcours dans l'ordre en utilisant à la fois des techniques récursives et itératives. Commençons par le parcours dans l'ordre utilisant la récursivité.
Parcours dans l'ordre utilisant la récursivité
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Exemple de parcours dans l'ordre
Voyons maintenant un exemple de parcours dans l'ordre. Il sera plus facile de comprendre la procédure de parcours dans l'ordre à l'aide d'un exemple.
java entier en chaîne
Les nœuds de couleur jaune ne sont pas encore visités. Maintenant, nous allons parcourir les nœuds de l'arbre ci-dessus en utilisant le parcours dans l'ordre.
- Ici, 40 est le nœud racine. Nous nous déplaçons vers le sous-arbre gauche de 40, c'est-à-dire 30, et il a également le sous-arbre 25, donc nous passons à nouveau au sous-arbre gauche de 25, soit 15. Ici, 15 n'a pas de sous-arbre, donc imprimer 15 et se déplacer vers son nœud parent, 25.
- Maintenant, imprimer 25 et passez au sous-arbre droit de 25.
- Maintenant, imprimer 28 et passez au nœud racine de 25 qui est 30.
- Ainsi, le sous-arbre gauche de 30 est visité. Maintenant, imprimer 30 et passer au bon enfant de 30 ans.
- Maintenant, imprimer 35 et passez au nœud racine de 30.
- Maintenant, imprimer le nœud racine 40 et déplacez-vous vers son sous-arbre droit.
- Parcourez maintenant de manière récursive le sous-arbre droit de 40, soit 50.
50 ont un sous-arbre, donc parcourez d'abord le sous-arbre gauche de 50 qui est 45. 45 n'a pas d'enfants, donc imprimer 45 et passez à son nœud racine.
- Maintenant imprimer 50 et déplacez-vous vers le sous-arbre droit de 50, soit 60.
- Maintenant, parcourez récursivement le sous-arbre droit de 50 qui est 60. 60 a un sous-arbre, donc parcourez d'abord le sous-arbre gauche de 60 qui est 55. 55 n'a pas d'enfants, donc imprimer 55 et passez à son nœud racine.
- Maintenant imprimer 60 et déplacez-vous vers le sous-arbre droit de 60, soit 70.
- Maintenant imprimer 70.
Une fois le parcours dans l'ordre terminé, le résultat final est -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Complexité du parcours Inorder
La complexité temporelle du parcours Inorder est Sur), où 'n' est la taille de l'arbre binaire.
Alors que la complexité spatiale du parcours dans l’ordre est O(1), si nous ne considérons pas la taille de la pile pour les appels de fonction. Sinon, la complexité spatiale du parcours inverse est Oh), où « h » est la hauteur de l'arbre.
Implémentation du parcours Inorder
Voyons maintenant l'implémentation du parcours inverse dans différents langages de programmation.
Programme: Écrivez un programme pour implémenter le parcours inverse en langage C.
date locale java
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; } Sortir
Programme: Écrivez un programme pour implémenter le parcours inverse en C++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); cout<<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine('The Inorder traversal of given binary tree is - '); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Sortir
Programme: Écrivez un programme pour implémenter le parcours inverse en Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + ' '); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } Sortir
Donc, c'est tout à propos de l'article. J'espère que l'article vous sera utile et informatif.