logo

TechCodeview

Inorder Traversal

I den här artikeln kommer vi att diskutera inordningsövergången i datastruktur.

Om vi ​​vill korsa noderna i stigande ordning, så använder vi inordningsgenomgången. Följande är stegen som krävs för övergången av inorder:

  • Besök alla noder i det vänstra underträdet
  • Besök rotnoden
  • Besök alla noder i det högra underträdet

Linjära datastrukturer som stack, array, kö etc. har bara ett sätt att gå igenom data. Men i hierarkiska datastrukturer som t.ex träd, det finns flera sätt att gå igenom data. Här kommer vi att diskutera ett annat sätt att korsa träddatastrukturen, dvs.

Det finns två tillvägagångssätt som används för övergången av inorden:

  • Inorder genomgång med hjälp av rekursion
  • Inordna genomgång med en iterativ metod

En ordningsgenomgångsteknik följer Vänster rot Höger politik. Här betyder Left Root Right att det vänstra underträdet av rotnoden korsas först, sedan rotnoden och sedan det högra underträdet av rotnoden. Här antyder själva ordningsnamnet att rotnoden kommer in mellan det vänstra och det högra underträdet.

Vi kommer att diskutera ordningsgenomgången med både rekursiva och iterativa tekniker. Låt oss först börja med inorder-traversal med hjälp av rekursion.

Inordna traversering med hjälp av rekursion

 Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively

Exempel på övergång av inorder

Låt oss nu se ett exempel på ordningsföljd. Det kommer att bli lättare att förstå proceduren för inorderövergång med hjälp av ett exempel.

Inorder Traversal

Noderna med gul färg är inte besökta ännu. Nu kommer vi att korsa noderna i ovanstående träd genom att använda inorder-traversal.

  • Här är 40 rotnoden. Vi flyttar till det vänstra underträdet av 40, det vill säga 30, och det har också underträdet 25, så vi flyttar återigen till det vänstra underträdet på 25 som är 15. Här har 15 inget underträd, så tryck 15 och flytta mot sin föräldernod, 25.
    Inorder Traversal
  • Nu, tryck 25 och flytta till höger underträd av 25.
    Inorder Traversal
  • Nu, tryck 28 och flytta till rotnoden på 25, det vill säga 30.
    Inorder Traversal
  • Så vänster underträd på 30 besöks. Nu, tryck 30 och flytta till rätt barn på 30.
    Inorder Traversal
  • Nu, tryck 35 och flytta till rotnoden på 30.
    Inorder Traversal
  • Nu, skriv ut rotnod 40 och flytta till dess högra underträd.
    Inorder Traversal
  • Passera nu rekursivt det högra underträdet av 40, det vill säga 50.
    50 har underträd så gå först igenom det vänstra underträdet på 50, dvs. 45. 45 har inga barn, så tryck 45 och flytta till dess rotnod.
    Inorder Traversal
  • Nu tryck 50 och flytta till höger underträd av 50 som är 60.
    Inorder Traversal
  • Passera nu rekursivt det högra underträdet av 50 som är 60. 60 har underträdet, så kör först det vänstra underträdet på 60 som är 55. 55 har inga barn, så tryck 55 och flytta till dess rotnod.
    Inorder Traversal
  • Nu tryck 60 och flytta till höger underträd av 60 som är 70.
    Inorder Traversal
  • Nu tryck 70.
    Inorder Traversal

Efter slutförandet av inorderövergången är den slutliga utmatningen -

{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}

Komplexiteten av Inorder-traversering

Tidskomplexiteten för Inorder-traversering är På), där 'n' är storleken på ett binärt träd.

Medan rymdkomplexiteten av inorder-traversering är O(1), om vi inte tar hänsyn till stackstorleken för funktionsanrop. I annat fall är rymdkomplexiteten av inorder-traversering Åh), där 'h' är trädets höjd.

Implementering av Inorder-traversering

Låt oss nu se implementeringen av inorder-traversal i olika programmeringsspråk.

Program: Skriv ett program för att implementera ordningsövergång i C-språk.

 #include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root->left); printf(' %d ', root->element); traverseInorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
 The Inorder traversal of given binary tree is -
'); traverseInorder(root); return 0; }

Produktion

Inorder Traversal

Program: Skriv ett program för att implementera inorder-traversal i C++.

 #include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node-&gt;element = val; Node-&gt;left = NULL; Node-&gt;right = NULL; return (Node); } /*function to traverse the nodes of binary tree in Inorder*/ void traverseInorder(struct node* root) { if (root == NULL) return; traverseInorder(root-&gt;left); cout&lt;<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root-&gt;right = createNode(49); root-&gt;left-&gt;left = createNode(24); root-&gt;left-&gt;right = createNode(34); root-&gt;left-&gt;left-&gt;left = createNode(14); root-&gt;left-&gt;left-&gt;right = createNode(27); root-&gt;right-&gt;left = createNode(44); root-&gt;right-&gt;right = createNode(59); root-&gt;right-&gt;right-&gt;left = createNode(54); root-&gt;right-&gt;right-&gt;right = createNode(69); cout&lt;<'
 the inorder traversal of given binary tree is -
'; traverseinorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-14.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); Console.Write(node.value + &apos; &apos;); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(36); bt.root.left = new Node(26); bt.root.right = new Node(46); bt.root.left.left = new Node(21); bt.root.left.right = new Node(31); bt.root.left.left.left = new Node(11); bt.root.left.left.right = new Node(24); bt.root.right.left = new Node(41); bt.root.right.right = new Node(56); bt.root.right.right.left = new Node(51); bt.root.right.right.right = new Node(66); Console.WriteLine(&apos;The Inorder traversal of given binary tree is - &apos;); bt.traverseInorder(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-15.webp" alt="Inorder Traversal"> <p> <strong>Program:</strong> Write a program to implement inorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + &apos; &apos;); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println(&apos;The Inorder traversal of given binary tree is - &apos;); pt.traverseInorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/15/inorder-traversal-16.webp" alt="Inorder Traversal"> <p>So, that&apos;s all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'>

Produktion

Inorder Traversal

Program: Skriv ett program för att implementera inorder-traversal i Java.

 class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class InorderTraversal { Node root; InorderTraversal() { root = null; } void traverseInorder(Node node) { if (node == null) return; traverseInorder(node.left); System.out.print(node.value + &apos; &apos;); traverseInorder(node.right); } void traverseInorder() { traverseInorder(root); } public static void main(String args[]) { InorderTraversal pt = new InorderTraversal(); pt.root = new Node(35); pt.root.left = new Node(25); pt.root.right = new Node(45); pt.root.left.left = new Node(20); pt.root.left.right = new Node(30); pt.root.left.left.left = new Node(10); pt.root.left.left.right = new Node(23); pt.root.right.left = new Node(40); pt.root.right.right = new Node(55); pt.root.right.right.left = new Node(50); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println(&apos;The Inorder traversal of given binary tree is - &apos;); pt.traverseInorder(); System.out.println(); } }

Produktion

Inorder Traversal

Så det handlar om artikeln. Hoppas artikeln kommer att vara användbar och informativ för dig.