Neriadkový prechod je definovaný ako typ technika prechodu cez strom ktorý sa riadi vzorom Left-Root-Right, takže:
- Najprv sa prejde ľavý podstrom
- Potom sa prejde koreňový uzol tohto podstromu
- Nakoniec sa prejde pravý podstrom
Neriadkový prechod
Algoritmus pre postupný prechod binárneho stromu
Algoritmus pre prechod v poradí je znázornený takto:
Inorder (koreň):
- Postupujte podľa krokov 2 až 4, kým root != NULL
- V poradí (koreň -> vľavo)
- Napíšte root -> údaje
- Inorder (koreň -> vpravo)
- Koniec slučky
Ako funguje Inorder Traversal of Binary Tree?
Zvážte nasledujúci strom:
Príklad binárneho stromu
Ak vykonáme prechod v tomto binárnom strome, prechod bude nasledujúci:
Krok 1: Prechod prejde z 1 do svojho ľavého podstromu, t. j. 2, potom z 2 do svojho ľavého koreňa podstromu, t. j. 4. Teraz 4 nemá žiadny ľavý podstrom, takže bude navštívený. Tiež nemá žiadny pravý podstrom. Takže už žiadne prechádzanie od 4
Uzol 4 je navštívený
Krok 2: Keďže ľavý podstrom 2 je úplne navštívený, teraz číta údaje uzla 2 a potom sa presunie do pravého podstromu.
Uzol 2 je navštívený
Krok 3: Teraz sa prejde pravý podstrom 2, t. j. presunie sa do uzla 5. Pre uzol 5 nie je žiadny ľavý podstrom, takže sa navštívi a potom sa prechod vráti, pretože neexistuje pravý podstrom uzla 5.
Uzol 5 je navštívený
Krok 4: Keďže je ľavý podstrom uzla 1, navštívi sa samotný koreň, t. j. uzol 1.
Uzol 1 je navštívený
Krok 5: Je navštívený ľavý podstrom uzla 1 a samotný uzol. Takže teraz sa prejde pravý podstrom 1, t.j. presunie sa do uzla 3. Keďže uzol 3 nemá žiadny ľavý podstrom, bude navštívený.
Uzol 3 je navštívený
pivot pandyKrok 6: Navštívi sa ľavý podstrom uzla 3 a samotný uzol. Prejdite teda do pravého podstromu a navštívte uzol 6. Teraz sa prechod končí, pretože všetky uzly prešli.
Celý strom je prejdený
Takže poradie prechodu uzlov je 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program na implementáciu Inorder Traversal binárneho stromu:
Nižšie je uvedená implementácia kódu prechodu podľa poradia:
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->vľavo);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->správny); } // Kód ovládača int main() { struct 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); // Volanie funkcie 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);> |
>
>Výkon
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Vysvetlenie:
Ako funguje inorder traversal
Analýza zložitosti:
Časová zložitosť: O(N), kde N je celkový počet uzlov. Pretože aspoň raz prejde cez všetky uzly.
Pomocný priestor: O(1), ak sa neberie do úvahy priestor zásobníka rekurzie. V opačnom prípade O(h), kde h je výška stromu
- V najhoršom prípade h môže byť rovnaký ako N (keď je strom skosený strom)
- V najlepšom prípade h môže byť rovnaký ako pokojne (keď je strom úplný strom)
Prípady použitia Inorder Traversal:
V prípade BST (Binary Search Tree), ak kedykoľvek vznikne potreba dostať uzly do neklesajúceho poradia, najlepším spôsobom je implementovať prechod podľa poradia.
Súvisiace články:
- Typy prechodov cez stromy
- Iteratívne prechádzanie poradia
- Zostavte binárny strom z prechodu predobjednávky a poradia
- Morris traversal pre neriadený traverz stromu
- Neriadkový prechod bez rekurzie