In dit artikel bespreken we de inorder-traversal in de datastructuur.
Als we de knooppunten in oplopende volgorde willen doorlopen, gebruiken we de in-order-doorgang. Hieronder volgen de stappen die nodig zijn voor het doorlopen van de volgorde:
- Bezoek alle knooppunten in de linker subboom
- Bezoek het hoofdknooppunt
- Bezoek alle knooppunten in de rechter subboom
Lineaire datastructuren zoals stack, array, wachtrij, etc. hebben maar één manier om de data te doorkruisen. Maar in hiërarchische datastructuren zoals boom, er zijn meerdere manieren om de gegevens te doorkruisen. Hier zullen we een andere manier bespreken om de boomgegevensstructuur te doorkruisen, dat wil zeggen: in volgorde.
Er worden twee benaderingen gebruikt voor de inorder-traversal:
- Inorder-traversal met behulp van recursie
- Inorder-traversal met behulp van een iteratieve methode
Een inorder-traversal-techniek volgt de Links Wortel Rechts beleid. Hier betekent Left Root Right dat eerst de linker deelboom van het hoofdknooppunt wordt doorlopen, daarna de hoofdknoop en vervolgens de rechter deelboom van het hoofdknooppunt. Hier suggereert de naam zelf dat het hoofdknooppunt tussen de linker en de rechter subboom komt.
We zullen de inorder-traversal bespreken met behulp van zowel recursieve als iteratieve technieken. Laten we eerst beginnen met het doorlopen van de volgorde met behulp van recursie.
Inorder-traversal met behulp van recursie
Step 1: Recursively traverse the left subtree Step 2: Now, visit the root Step 3: Traverse the right subtree recursively
Voorbeeld van inorder-traversal
Laten we nu een voorbeeld bekijken van inorder-traversal. Het zal gemakkelijker zijn om de procedure van inorder-traversal te begrijpen aan de hand van een voorbeeld.
De knooppunten met gele kleur zijn nog niet bezocht. Nu zullen we de knooppunten van de bovenstaande boom doorkruisen met behulp van inorder-traversal.
- Hier is 40 het hoofdknooppunt. We gaan naar de linker subboom van 40, dat is 30, en die heeft ook subboom 25, dus we gaan weer naar de linker subboom van 25, dat is 15. Hier heeft 15 geen subboom, dus afdrukken 15 en ga naar het ouderknooppunt, 25.
- Nu, afdrukken 25 en ga naar de rechter subboom van 25.
- Nu, afdrukken 28 en ga naar het hoofdknooppunt van 25, dat is 30.
- Dus de linker subboom van 30 wordt bezocht. Nu, afdrukken 30 en verhuizen naar het juiste kind van 30.
- Nu, afdrukken 35 en ga naar het hoofdknooppunt van 30.
- Nu, print rootknooppunt 40 en ga naar de rechter subboom.
- Doorloop nu recursief de rechter deelboom van 40, dat is 50.
50 hebben een subboom, dus doorloop eerst de linker subboom van 50, dat is 45. 45 heeft geen kinderen, dus afdrukken 45 en ga naar het hoofdknooppunt.
- Nu afdrukken 50 en ga naar de rechter subboom van 50, dat is 60.
- Doorloop nu recursief de rechter deelboom van 50, dat is 60. 60 hebben een subboom, dus doorkruis eerst de linker deelboom van 60, dat is 55. 55 heeft geen kinderen, dus afdrukken 55 en ga naar het hoofdknooppunt.
- Nu afdrukken 60 en ga naar de rechter subboom van 60, dat is 70.
- Nu afdrukken 70.
Na voltooiing van de inorder-doorgang is de uiteindelijke uitvoer -
{15, 25, 28, 30, 35, 40, 45, 50, 55, 60, 70}
Complexiteit van het doorkruisen van onorden
De tijdscomplexiteit van Inorder-traversal is Op), waarbij 'n' de grootte van de binaire boom is.
Terwijl de ruimtecomplexiteit van inorder-traversal dat wel is O(1), als we geen rekening houden met de stapelgrootte voor functieaanroepen. Anders is de ruimtecomplexiteit van inorder-traversal dat wel Oh), waarbij 'h' de hoogte van de boom is.
Implementatie van Inorder-traversal
Laten we nu eens kijken naar de implementatie van inorder traversal in verschillende programmeertalen.
Programma: Schrijf een programma om inorder traversal in C-taal te implementeren.
#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; } Uitvoer
Programma: Schrijf een programma om inorder traversal in C++ te implementeren.
#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></'
></'> Uitvoer
Programma: Schrijf een programma om inorder traversal in Java te implementeren.
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(); } } Uitvoer
Dus dat is alles over het artikel. Ik hoop dat het artikel nuttig en informatief voor u zal zijn.