V tomto článku budeme diskutovať o prechode poradia v dátovej štruktúre.
Ak chceme prejsť cez uzly vo vzostupnom poradí, tak použijeme inorder traversal. Nasledujú kroky potrebné na prechod v poradí:
- Navštívte všetky uzly v ľavom podstrome
- Navštívte koreňový uzol
- Navštívte všetky uzly v pravom podstrome
Lineárne dátové štruktúry, ako je zásobník, pole, front atď., majú iba jeden spôsob prechodu dát. Ale v hierarchických dátových štruktúrach ako napr strom, existuje viacero spôsobov, ako prechádzať dátami. Tu budeme diskutovať o ďalšom spôsobe prechodu stromovej dátovej štruktúry, t.j. prechode podľa poradia.
Existujú dva prístupy používané na prechod v poradí:
príkaz touch v linuxe
- Priebeh poradia pomocou rekurzie
- Priebeh poradia pomocou iteračnej metódy
Nasleduje technika neriadeného prechodu Ľavý Koreň Pravý politika. Tu Left Root Right znamená, že najprv sa prejde ľavý podstrom koreňového uzla, potom koreňový uzol a potom sa prejde pravý podstrom koreňového uzla. Tu už samotný názov poradia naznačuje, že koreňový uzol sa nachádza medzi ľavým a pravým podstromom.
Budeme diskutovať o inorder traversal pomocou rekurzívnych aj iteračných techník. Začnime najskôr prechodom po poradí pomocou rekurzie.
Priebeh poradia pomocou rekurzie
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Príklad prechodu poradia
Teraz sa pozrime na príklad prechodu v poradí. Na príklade bude jednoduchšie pochopiť postup prechodu poradia.
Uzly so žltou farbou zatiaľ nie sú navštevované. Teraz budeme prechádzať uzlami vyššie uvedeného stromu pomocou inorder traversal.
- Tu je 40 koreňový uzol. Presunieme sa do ľavého podstromu 40, to je 30, a má tiež podstrom 25, takže sa opäť presunieme do ľavého podstromu 25, to je 15. Tu 15 nemá žiadny podstrom, takže vytlačiť 15 a posuňte sa smerom k svojmu rodičovskému uzlu, 25.
- teraz vytlačiť 25 a presuňte sa do pravého podstromu 25.
- teraz vytlačiť 28 a presuňte sa do koreňového uzla 25, čo je 30.
- Takže je navštívený ľavý podstrom 30. teraz vytlačiť 30 a presťahovať sa k správnemu dieťaťu vo veku 30 rokov.
- teraz vytlačiť 35 a presuňte sa do koreňového uzla 30.
- teraz vytlačiť koreňový uzol 40 a presuňte sa do jeho pravého podstromu.
- Teraz rekurzívne prejdite pravým podstromom 40, čo je 50.
50 má podstrom, takže najprv prejdite ľavým podstromom 50, čo je 45. 45 nemá potomkov, takže tlač 45 a presuňte sa do jeho koreňového uzla.
- Teraz vytlačiť 50 a presuňte sa do pravého podstromu 50, čo je 60.
- Teraz rekurzívne prejdite pravým podstromom 50, čo je 60. 60 má podstrom, takže najprv prejdite ľavým podstromom 60, čo je 55. 55 nemá potomkov, takže vytlačiť 55 a presuňte sa do jeho koreňového uzla.
- Teraz tlač 60 a presuňte sa do pravého podstromu 60, čo je 70.
- Teraz tlač 70.
Po dokončení prechodu objednávky je konečný výstup -
očíslovať abecedu
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Zložitosť prechodu Inorder
Časová zložitosť prechodu Inorder je O(n), kde 'n' je veľkosť binárneho stromu.
Zatiaľ čo priestorová zložitosť prechodu usporiadaním je O(1), ak neberieme do úvahy veľkosť zásobníka pre volania funkcií. V opačnom prípade je priestorová náročnosť prechodu v poriadku O(h), kde 'h' je výška stromu.
Implementácia Inorder traversal
Teraz sa pozrime na implementáciu inorder traversal v rôznych programovacích jazykoch.
Program: Napíšte program na implementáciu prechodu príkazov v jazyku 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; } Výkon
25 zo 100
Program: Napíšte program na implementáciu inorder traversal v 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></'
></'> Výkon
Program: Napíšte program na implementáciu inorder traversal v Jave.
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(); } } Výkon
linuxové skratky
Tak, to je o článku všetko. Dúfam, že článok bude pre vás užitočný a poučný.