Inordnergjennomgang er definert som en type tre-traverseringsteknikk som følger venstre-rot-høyre-mønsteret, slik at:
- Det venstre undertreet krysses først
- Deretter krysses rotnoden for det undertreet
- Til slutt krysses det høyre undertreet
Inordnergjennomgang
Algoritme for Inorder Traversal av binært tre
Algoritmen for inorder-gjennomgang vises som følger:
Inorder (root):
- Følg trinn 2 til 4 til root != NULL
- I rekkefølge (root -> venstre)
- Skriv root -> data
- I rekkefølge (root -> høyre)
- Sluttløkke
Hvordan fungerer Inorder Traversal of Binary Tree?
Tenk på følgende tre:
Eksempel på binært tre
Hvis vi utfører en inorder-gjennomgang i dette binære treet, vil gjennomgangen være som følger:
Trinn 1: Traverseringen vil gå fra 1 til venstre undertre, dvs. 2, deretter fra 2 til venstre undertrerot, dvs. 4. Nå har ikke 4 noe venstre undertre, så det vil bli besøkt. Den har heller ikke noe rett undertre. Så ingen mer kryssing fra 4
Node 4 er besøkt
Steg 2: Ettersom venstre undertre av 2 besøkes fullstendig, leser den nå data fra node 2 før den flytter til høyre undertre.
Node 2 er besøkt
Trinn 3: Nå vil det høyre undertreet av 2 bli krysset, dvs. flytte til node 5. For node 5 er det ikke noe venstre undertre, så det blir besøkt, og etter det kommer traverseringen tilbake fordi det ikke er noe høyre undertre av node 5.
Node 5 er besøkt
Trinn 4: Som det venstre undertreet til node 1 er, vil selve roten, dvs. node 1, besøkes.
Node 1 er besøkt
Trinn 5: Venstre undertre av node 1 og selve noden besøkes. Så nå vil høyre undertre av 1 bli krysset, dvs. flytte til node 3. Siden node 3 ikke har noe venstre undertre, så blir det besøkt.
Node 3 er besøkt
Trinn 6: Det venstre undertreet til node 3 og selve noden besøkes. Så traverser til høyre undertre og besøk node 6. Nå avsluttes traverseringen ettersom alle nodene krysses.
Hele treet krysses
Så rekkefølgen for kryssing av noder er 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program for å implementere Inorder Traversal of Binary Tree:
Nedenfor er kodeimplementeringen av inorder-gjennomgangen:
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->venstre);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->Ikke sant); } // Driverkode int main() { struct Node* root = new Node(1); root->venstre = ny node(2); root->right = ny node(3); root->venstre->venstre = ny node(4); root->venstre->høyre = ny node(5); root->right->right = ny node(6); // Function call cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
konvertering fra dato til streng
// 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)> |
>
>
java er tom
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);> |
>
>Produksjon
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Forklaring:
Hvordan inorder-traversering fungerer
Kompleksitetsanalyse:
Tidskompleksitet: O(N) hvor N er det totale antallet noder. Fordi den krysser alle nodene minst én gang.
Hjelpeplass: O(1) hvis ingen rekursjonsstabelplass vurderes. Ellers O(h) hvor h er høyden på treet
- I verste fall, h kan være det samme som N (når treet er et skjevt tre)
- I beste fall, h kan være det samme som rolig (når treet er et komplett tre)
Bruk tilfeller av Inorder Traversal:
Når det gjelder BST (Binary Search Tree), hvis det noen gang er behov for å få nodene i ikke-avtagende rekkefølge, er den beste måten å implementere en inorder-gjennomgang.
Relaterte artikler:
- Typer trekryssinger
- Iterativ gjennomgang av rekkefølge
- Konstruer binært tre fra preorder og inorder traversal
- Morris-traversering for uordnet kryssing av treet
- Uordnet traversering uten rekursjon