logo

TechCodeview

Inorder genomgång av binärt träd

Inorder genomgång definieras som en typ av trädtraverseringsteknik som följer vänster-rot-höger-mönstret, så att:

  • Det vänstra underträdet korsas först
  • Sedan korsas rotnoden för det underträdet
  • Slutligen korsas det högra underträdet
Inorder genomgång

Inorder genomgång



Algoritm för Inorder Traversal av binärt träd

Algoritmen för övergång av inorder visas enligt följande:

Inorder (root):

  1. Följ steg 2 till 4 tills root != NULL
  2. Inordning (root -> vänster)
  3. Skriv root -> data
  4. Inorder (root -> höger)
  5. Slutslinga

Hur fungerar Inorder Traversal of Binary Tree?

Tänk på följande träd:



Exempel på binärt träd

Exempel på binärt träd

Om vi ​​utför en ordningsgenomgång i det här binära trädet, så kommer övergången att vara som följer:

Steg 1: Traverseringen kommer att gå från 1 till dess vänstra underträd, dvs. 2, sedan från 2 till dess vänstra underträdsrot, d.v.s. 4. Nu har 4 inget vänster underträd, så det kommer att besökas. Den har inte heller något rätt underträd. Så ingen mer övergång från 4



Nod 4 besöks

Nod 4 besöks

Steg 2: Eftersom det vänstra underträdet av 2 besöks fullständigt, läser det nu data från nod 2 innan det flyttas till sitt högra underträd.

konvertera strängdatum
Nod 2 besöks

Nod 2 besöks

Steg 3: Nu kommer det högra underträdet av 2 att korsas, dvs flytta till nod 5. För nod 5 finns det inget vänster underträd, så det besöks och efter det kommer genomgången tillbaka eftersom det inte finns något höger underträd av nod 5.

Nod 5 besöks

Nod 5 besöks

Steg 4: Som det vänstra underträdet av nod 1 är, kommer själva roten, d.v.s. nod 1 att besökas.

Nod 1 besöks

Nod 1 besöks

Steg 5: Vänster underträd av nod 1 och själva noden besöks. Så nu kommer det högra underträdet av 1 att korsas, dvs flytta till nod 3. Eftersom nod 3 inte har något vänster underträd så får den besök.

Nod 3 besöks

Nod 3 besöks

Steg 6: Det vänstra underträdet av nod 3 och själva noden besöks. Så gå till höger underträd och besök nod 6. Nu avslutas genomgången när alla noder korsas.

Hela trädet korsas

Hela trädet korsas

Så ordningen för korsning av noder är 4 -> 2 -> 5 -> 1 -> 3 -> 6 .

Program för att implementera Inorder Traversal of Binary Tree:

Nedan är kodimplementeringen av inordergenomgången:

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änster);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->höger); } // Drivrutinskod 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->vänster->höger = ny Node(5); root->right->right = new Node(6); // Funktionsanrop cout<< 'Inorder traversal of binary tree is: '; printInorder(root); return 0; }> 

>

vad är desktop.ini 
>

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#




css första barn
// 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);> 

>

harald baldr 
>

Produktion 

Inorder traversal of binary tree is: 4 2 5 1 3 6>

Förklaring:

Hur inorder-traversal fungerar

Hur inorder-traversal fungerar

Komplexitetsanalys:

Tidskomplexitet: O(N) där N är det totala antalet noder. Eftersom den korsar alla noder minst en gång.
Hjälputrymme: O(1) om inget rekursionsstackutrymme beaktas. Annars O(h) där h är trädets höjd

  • I värsta fall, h kan vara samma som N (när trädet är ett skevt träd)
  • I bästa fall, h kan vara samma som lugna (när trädet är ett komplett träd)

Användningsfall av Inorder Traversal:

När det gäller BST (Binary Search Tree), om någon gång det finns ett behov av att få noderna i icke-minskande ordning, är det bästa sättet att implementera en inorder-traversal.

Relaterade artiklar:

  • Typer av trädgenomföringar
  • Iterativ övergång av ordningsföljd
  • Konstruera binärt träd från förorder och inorder genomgång
  • Morris-traversal för inorder-traversering av träd
  • Inordergenomgång utan rekursion