I denne artikkelen vil vi diskutere inordergjennomgang i datastruktur.
kall javascript-funksjon fra html
Hvis vi ønsker å krysse nodene i stigende rekkefølge, bruker vi inordre-traversal. Følgende er trinnene som kreves for gjennomgang av inordre:
- Besøk alle nodene i det venstre undertreet
- Besøk rotnoden
- Besøk alle nodene i det høyre undertreet
Lineære datastrukturer som stack, array, queue, etc., har bare én måte å krysse dataene på. Men i hierarkiske datastrukturer som f.eks tre, det er flere måter å krysse dataene på. Her vil vi diskutere en annen måte å krysse tredatastrukturen på, dvs. gjennomgang av uorden.
Det er to tilnærminger som brukes for inordnovergangen:
- Inorder traversering ved hjelp av rekursjon
- Inorder traversering ved hjelp av en iterativ metode
En uordnet traverseringsteknikk følger Venstre rot Høyre Politikk. Her betyr Venstre rot Høyre at det venstre undertreet til rotnoden krysses først, deretter rotnoden og deretter det høyre undertreet til rotnoden. Her antyder selve ordensnavnet at rotnoden kommer inn mellom venstre og høyre undertre.
Vi vil diskutere den inordnede traverseringen ved å bruke både rekursive og iterative teknikker. La oss først starte med inorder-traversering ved å bruke rekursjon.
Inorder traversering ved bruk av rekursjon
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Eksempel på inordergjennomgang
La oss nå se et eksempel på inorder-gjennomgang. Det vil være lettere å forstå prosedyren for inorder-gjennomgang ved å bruke et eksempel.
Nodene med gul farge er ikke besøkt ennå. Nå vil vi krysse nodene til treet ovenfor ved å bruke inorder-gjennomgang.
- Her er 40 rotnoden. Vi flytter til venstre undertre på 40, det vil si 30, og det har også undertre 25, så vi flytter igjen til venstre undertre på 25 som er 15. Her har 15 ikke noe undertre, så utskrift 15 og gå mot dens overordnede node, 25.
- Nå, utskrift 25 og flytt til høyre undertre av 25.
- Nå, utskrift 28 og gå til rotnoden på 25 som er 30.
- Så venstre undertre på 30 er besøkt. Nå, print 30 og flytte til rett barn på 30.
- Nå, trykk 35 og gå til rotnoden på 30.
- Nå, skriv ut rotnode 40 og flytt til høyre undertre.
- Gå nå rekursivt gjennom det høyre undertreet på 40 som er 50.
50 har undertre så kryss først det venstre undertreet på 50 som er 45. 45 har ingen barn, så utskrift 45 og gå til rotnoden.
- Nå trykk 50 og flytt til høyre undertre av 50 som er 60.
- Gå nå rekursivt gjennom det høyre undertreet på 50 som er 60. 60 har et undertre, så kryss først det venstre undertreet på 60 som er 55. 55 har ingen barn, så trykk 55 og gå til rotnoden.
- Nå trykk 60 og flytt til høyre undertre av 60 som er 70.
- Nå trykk 70.
Etter fullføringen av inordergjennomgang er den endelige utgangen -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Kompleksiteten til Inorder-traversering
Tidskompleksiteten til Inorder-traversering er På), hvor 'n' er størrelsen på binært tre.
Mens romkompleksiteten til inordnergjennomgang er O(1), hvis vi ikke vurderer stabelstørrelsen for funksjonskall. Ellers er romkompleksiteten til inorder-traversering Åh), hvor 'h' er høyden på treet.
Implementering av Inorder-traversering
La oss nå se implementeringen av inorder-gjennomgang i forskjellige programmeringsspråk.
Program: Skriv et program for å implementere inordretraversal 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; } Produksjon
Program: Skriv et program for å implementere inordre-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->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); cout<<' '<element<right); } int main() { struct node* root="createNode(39);" root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
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 + ' '); 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('The Inorder traversal of given binary tree is - '); 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 + ' '); 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('The Inorder traversal of given binary tree is - '); 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's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Produksjon
Program: Skriv et program for å implementere inordre-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 + ' '); 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('The Inorder traversal of given binary tree is - '); pt.traverseInorder(); System.out.println(); } } Produksjon
Så det handler om artikkelen. Håper artikkelen vil være nyttig og informativ for deg.