En aquest article, parlarem del recorregut en ordre en l'estructura de dades.
Si volem recórrer els nodes en ordre ascendent, utilitzarem el recorregut inorder. A continuació es mostren els passos necessaris per a la travessa en ordre:
- Visiteu tots els nodes del subarbre esquerre
- Visiteu el node arrel
- Visiteu tots els nodes del subarbre dret
Les estructures de dades lineals com ara pila, matriu, cua, etc., només tenen una manera de recórrer les dades. Però en estructures de dades jeràrquiques com ara arbre, hi ha diverses maneres de recórrer les dades. Aquí parlarem d'una altra manera de recórrer l'estructura de dades de l'arbre, és a dir, el recorregut en ordre.
Hi ha dos enfocaments utilitzats per a la travessa en ordre:
- Travessa en ordre utilitzant Recursió
- Travessa en ordre mitjançant un mètode iteratiu
Una tècnica de recorregut inordre segueix el Esquerra Arrel Dreta política. Aquí, Left Root Right significa que es recorre primer el subarbre esquerre del node arrel, després el node arrel i després el subarbre dret del node arrel. Aquí, el propi nom d'ordre suggereix que el node arrel es troba entre els subarbres esquerre i dret.
Discutirem el recorregut en ordre utilitzant tant tècniques recursives com iteratives. Comencem primer amb el recorregut en ordre utilitzant recursivitat.
Travessa en ordre utilitzant recursivitat
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Exemple de travessa en ordre
Ara, vegem un exemple de travessa en ordre. Serà més fàcil entendre el procediment de travessa en ordre utilitzant un exemple.
document.queryselector
Els nodes amb color groc encara no es visiten. Ara, travessarem els nodes de l'arbre anterior utilitzant el recorregut en ordre.
- Aquí, 40 és el node arrel. Ens movem al subarbre esquerre de 40, és a dir, 30, i també té el subarbre 25, així que tornem al subarbre esquerre de 25, que és 15. Aquí, 15 no té cap subarbre, així que imprimir 15 i avançar cap al seu node pare, 25.
- Ara, imprimir 25 i moveu-vos al subarbre dret de 25.
- Ara, imprimir 28 i moveu-vos al node arrel de 25, que és 30.
- Per tant, es visita el subarbre esquerre de 30. Ara, imprimir 30 i passar al nen dret de 30.
- Ara, imprimir 35 i moveu-vos al node arrel de 30.
- Ara, imprimir el node arrel 40 i moure's al seu subarbre dret.
- Ara travessa de manera recursiva el subarbre dret de 40, que és 50.
50 tenen subarbre, així que primer travessa el subarbre esquerre de 50, que és 45. 45 no té fills, així que imprimir 45 i es mou al seu node arrel.
- Ara imprimir 50 i moveu-vos al subarbre dret de 50, que és 60.
- Ara travessa de manera recursiva el subarbre dret de 50 que és 60. 60 tenen subarbre, així que primer travessa el subarbre esquerre de 60 que és 55. 55 no té fills, així que imprimir 55 i es mou al seu node arrel.
- Ara imprimir 60 i moveu-vos al subarbre dret de 60, que és 70.
- Ara imprimir 70.
Després de completar el recorregut en ordre, la sortida final és -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Complexitat del recorregut de l'ordre
La complexitat temporal del recorregut de l'ordre és O(n), on 'n' és la mida de l'arbre binari.
Mentre que, la complexitat espacial del recorregut en ordre és O(1), si no tenim en compte la mida de la pila per a les trucades de funció. En cas contrari, la complexitat espacial del recorregut en ordre és O(h), on 'h' és l'alçada de l'arbre.
diff en Python
Implementació del recorregut Inorder
Ara, anem a veure la implementació del recorregut en ordre en diferents llenguatges de programació.
Programa: Escriu un programa per implementar el recorregut en ordre en llenguatge C.
#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; } Sortida
Programa: Escriu un programa per implementar el recorregut en ordre 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></'
></'> Sortida
Programa: Escriu un programa per implementar el recorregut en ordre 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(); } } Sortida
Per tant, això és tot sobre l'article. Espero que l'article us sigui útil i informatiu.