V tomto článku se budeme zabývat procházením řádků v datové struktuře.
Pokud chceme procházet uzly ve vzestupném pořadí, pak použijeme inorder traversal. Následují kroky potřebné pro průchod pořadím:
- Navštivte všechny uzly v levém podstromu
- Navštivte kořenový uzel
- Navštivte všechny uzly v pravém podstromu
Lineární datové struktury, jako je zásobník, pole, fronta atd., mají pouze jeden způsob, jak data procházet. Ale v hierarchických datových strukturách jako např strom, existuje několik způsobů, jak data procházet. Zde budeme diskutovat o dalším způsobu procházení stromové datové struktury, tj. o procházení podle pořadí.
Existují dva přístupy používané pro průchod řádem:
- Průchod pořadí pomocí rekurze
- Průchod pořadí pomocí Iterativní metody
Následuje technika neuspořádaného procházení Levý kořen Pravý politika. Zde Left Root Right znamená, že se nejprve projde levý podstrom kořenového uzlu, poté kořenový uzel a poté pravý podstrom kořenového uzlu. Zde samotný název pořadí naznačuje, že kořenový uzel se nachází mezi levým a pravým podstromem.
Budeme diskutovat o průchodu mezi řádky pomocí rekurzivních i iteračních technik. Začněme nejprve procházením řádků pomocí rekurze.
Průchod pořadí pomocí rekurze
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Příklad průchodu pořadí
Nyní se podívejme na příklad procházení nepořádku. Na příkladu bude snazší pochopit postup průchodu řádem.
Uzly se žlutou barvou zatím nejsou navštěvovány. Nyní budeme procházet uzly výše uvedeného stromu pomocí inorder traversal.
- Zde je 40 kořenový uzel. Přesuneme se do levého podstromu 40, to je 30, a má také podstrom 25, takže se opět přesuneme do levého podstromu 25, to je 15. Zde 15 nemá žádný podstrom, takže tisknout 15 a přesunout se směrem k jeho nadřazenému uzlu, 25.
- Nyní, tisknout 25 a přesuňte se do pravého podstromu 25.
- Nyní, tisknout 28 a přesuňte se do kořenového uzlu 25, což je 30.
- Je tedy navštíven levý podstrom 30. Nyní, tisknout 30 a přestěhovat se do správného 30letého dítěte.
- Nyní, tisknout 35 a přesuňte se do kořenového uzlu 30.
- Nyní, vytisknout kořenový uzel 40 a přesuňte se do jeho pravého podstromu.
- Nyní rekurzivně projděte pravý podstrom 40, což je 50.
50 má podstrom, takže nejprve projděte levý podstrom 50, což je 45. 45 nemá žádné potomky, takže tisk 45 a přesunout se do jeho kořenového uzlu.
- Nyní tisknout 50 a přesuňte se do pravého podstromu 50, to je 60.
- Nyní rekurzivně projděte pravý podstrom 50, což je 60. 60 má podstrom, takže nejprve projděte levý podstrom 60, což je 55. 55 nemá žádné potomky, takže tisk 55 a přesunout se do jeho kořenového uzlu.
- Nyní tisk 60 a přesuňte se do pravého podstromu 60, což je 70.
- Nyní tisk 70.
Po dokončení průchodu pořadím je konečný výstup -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Složitost průchodu Inorderem
Časová složitost Inorder traversal je Na), kde 'n' je velikost binárního stromu.
Zatímco prostorová složitost průchodu řádem je O(1), pokud neuvažujeme velikost zásobníku pro volání funkcí. V opačném případě je prostorová složitost průchodu řádem Ach), kde 'h' je výška stromu.
Implementace Inorder traversal
Nyní se podívejme na implementaci inorder traversal v různých programovacích jazycích.
Program: Napište program pro implementaci inorder traversal v jazyce 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ýstup
Program: Napište program pro implementaci 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ýstup
Program: Napište program pro implementaci inorder traversal v Javě.
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ýstup
Tak to je k článku vše. Doufám, že vám článek bude užitečný a informativní.