Prehod po vrstnem redu je opredeljena kot vrsta tehnika prečkanja drevesa ki sledi vzorcu Left-Root-Right, tako da:
- Najprej se prečka levo poddrevo
- Nato se prečka korensko vozlišče za to poddrevo
- Končno se prečka desno poddrevo
Prehod po vrstnem redu
Algoritem za prečkanje po vrstnem redu binarnega drevesa
Algoritem za prečkanje po vrstnem redu je prikazan takole:
V vrstnem redu (koren):
- Sledite korakom od 2 do 4, dokler ni root != NULL
- Po vrstnem redu (koren -> levo)
- Zapiši root -> data
- V vrstnem redu (koren -> desno)
- Končna zanka
Kako deluje Inorder Traversal of Binary Tree?
Razmislite o naslednjem drevesu:
napaka: ni bilo mogoče najti ali naložiti glavnega razreda
Primer binarnega drevesa
Če izvedemo prehod po nevrstnem redu v tem binarnem drevesu, bo prehod naslednji:
Korak 1: Prehod bo šel od 1 do njegovega levega poddrevesa, tj. 2, nato od 2 do njegovega levega korena poddrevesa, tj. 4. Zdaj 4 nima levega poddrevesa, zato bo obiskano. Prav tako nima nobenega desnega poddrevesa. Torej nič več prečkanja od 4
Vozlišče 4 je obiskano
2. korak: Ker je levo poddrevo 2 obiskano v celoti, zdaj prebere podatke vozlišča 2, preden se premakne na svoje desno poddrevo.
Vozlišče 2 je obiskano
3. korak: Zdaj bo prečkano desno poddrevo 2, tj. premakniti se na vozlišče 5. Za vozlišče 5 ni levega poddrevesa, zato je obiskano in po tem se prečkanje vrne, ker ni desnega poddrevesa vozlišča 5.
Vozlišče 5 je obiskano
4. korak: Ker je levo poddrevo vozlišča 1, bo obiskan sam koren, tj. vozlišče 1.
Vozlišče 1 je obiskano
5. korak: Levo poddrevo vozlišča 1 in samo vozlišče je obiskano. Torej bo zdaj prečkano desno poddrevo 1, tj. premaknilo se bo na vozlišče 3. Ker vozlišče 3 nima levega poddrevesa, bo obiskano.
Vozlišče 3 je obiskano
6. korak: Obiskano je levo poddrevo vozlišča 3 in samo vozlišče. Torej pojdite do desnega poddrevesa in obiščite vozlišče 6. Zdaj se prečkanje konča, ko so prečkana vsa vozlišča.
Prehodi se celotno drevo
Vrstni red prečkanja vozlišč je torej 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program za izvajanje Inorder Traversal binarnega drevesa:
Spodaj je implementacija kode prečkanja po vrstnem redu:
C++
java povezljivost
// 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->levo);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->prav); } // Koda gonilnika int main() { struct Node* root = new Node(1); root->left = novo vozlišče(2); root->desno = novo vozlišče(3); root->left->left = novo vozlišče(4); koren->levo->desno = novo vozlišče(5); root->desno->desno = novo vozlišče(6); // Klic funkcije 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
java ubežni znaki
# 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#
narediti lupinski skript izvršljiv
// 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);> >}> }> |
>
>
najboljši avtomobili na svetu
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);> |
>
>Izhod
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Pojasnilo:
Kako deluje prečkanje po vrstnem redu
Analiza kompleksnosti:
Časovna zapletenost: O(N), kjer je N skupno število vozlišč. Ker vsaj enkrat prečka vsa vozlišča.
Pomožni prostor: O(1), če ni upoštevan noben prostor rekurzijskega sklada. V nasprotnem primeru O(h), kjer je h višina drevesa
- V najslabšem primeru h lahko enako kot N (ko je drevo poševno drevo)
- V najboljšem primeru h lahko enako kot miren (ko je drevo popolno drevo)
Primeri uporabe Inorder Traversal:
Če je v primeru BST (binary search Tree) kadar koli treba dobiti vozlišča v nepadajočem vrstnem redu, je najboljši način implementacija prehoda po nevrstnem redu.
Povezani članki:
- Vrste prečkanja dreves
- Iterativno prečkanje po vrstnem redu
- Konstruirajte binarno drevo iz predvrstnega in nevrstnega prehoda
- Morrisovo prečkanje za neurejeno prečkanje drevesa
- Prehod po vrstnem redu brez rekurzije