logo

TechCodeview

Neriadený prechod binárneho stromu

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

Neriadkový prechod



Algoritmus pre postupný prechod binárneho stromu

Algoritmus pre prechod v poradí je znázornený takto:

Inorder (koreň):

  1. Postupujte podľa krokov 2 až 4, kým root != NULL
  2. V poradí (koreň -> vľavo)
  3. Napíšte root -> údaje
  4. Inorder (koreň -> vpravo)
  5. Koniec slučky

Ako funguje Inorder Traversal of Binary Tree?

Zvážte nasledujúci strom:



Príklad binárneho stromu

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ý

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ý

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ý

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ý

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ý

Uzol 3 je navštívený

pivot pandy

Krok 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ý

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

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