Inorder-Durchquerung ist als eine Art von definiert Baumdurchquerungstechnik das dem Links-Wurzel-Rechts-Muster folgt, so dass:
- Der linke Teilbaum wird zuerst durchlaufen
- Dann wird der Wurzelknoten für diesen Teilbaum durchlaufen
- Abschließend wird der rechte Teilbaum durchlaufen
Inorder-Durchquerung
Algorithmus für die Inorder-Traversierung des Binärbaums
Der Algorithmus für die Inorder-Traversierung wird wie folgt dargestellt:
Inorder(root):
- Befolgen Sie die Schritte 2 bis 4, bis root != NULL ist
- Inorder (Wurzel -> links)
- Root -> Daten schreiben
- Inorder (root -> rechts)
- Schleife beenden
Wie funktioniert die Inorder-Traversierung des Binärbaums?
Betrachten Sie den folgenden Baum:
Beispiel eines Binärbaums
Wenn wir in diesem Binärbaum eine Inorder-Traversierung durchführen, sieht die Traversierung wie folgt aus:
Schritt 1: Die Durchquerung erfolgt von 1 zu seinem linken Teilbaum, d. h. 2, dann von 2 zu seiner linken Teilbaumwurzel, d. h. 4. Jetzt hat 4 keinen linken Teilbaum, also wird er besucht. Es gibt auch keinen rechten Teilbaum. Also keine Durchquerung mehr von 4
Knoten 4 wird besucht
Schritt 2: Da der linke Teilbaum von Knoten 2 vollständig besucht ist, liest er nun die Daten von Knoten 2, bevor er zu seinem rechten Teilbaum wechselt.
Knoten 2 wird besucht
Schritt 3: Jetzt wird der rechte Teilbaum von 2 durchlaufen, d. h. zu Knoten 5 verschoben. Für Knoten 5 gibt es keinen linken Teilbaum, daher wird er besucht und danach kommt die Durchquerung zurück, da es keinen rechten Teilbaum von Knoten 5 gibt.
Knoten 5 wird besucht
Schritt 4: Da es sich um den linken Teilbaum von Knoten 1 handelt, wird die Wurzel selbst, also Knoten 1, besucht.
Knoten 1 wird besucht
Schritt 5: Linker Teilbaum von Knoten 1 und der Knoten selbst wird besucht. Jetzt wird also der rechte Teilbaum von 1 durchlaufen, d. h. zu Knoten 3 verschoben. Da Knoten 3 keinen linken Teilbaum hat, wird er besucht.
Knoten 3 wird besucht
Schritt 6: Der linke Teilbaum von Knoten 3 und der Knoten selbst werden besucht. Gehen Sie also zum rechten Teilbaum und besuchen Sie Knoten 6. Nun endet die Durchquerung, da alle Knoten durchlaufen wurden.
Der komplette Baum wird durchlaufen
Die Reihenfolge der Knotendurchquerung ist also 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Programm zur Implementierung von Inorder Traversal of Binary Tree:
Nachfolgend finden Sie die Code-Implementierung der Inorder-Traversierung:
C++
römische Ziffern 1 100
// 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->links);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->Rechts); } // Treibercode 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->left->right = new Node(5); root->right->right = new Node(6); // Funktionsaufruf cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
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
Eingabe einer Zeichenfolge in Java
# 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#
// 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);> |
>
>Ausgabe
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Erläuterung:
string.substring Java
Wie Inorder-Traversal funktioniert
Komplexitätsanalyse:
Zeitkomplexität: O(N) wobei N die Gesamtzahl der Knoten ist. Weil es alle Knoten mindestens einmal durchläuft.
Hilfsraum: O(1), wenn kein Rekursionsstapelplatz berücksichtigt wird. Ansonsten O(h), wobei h die Höhe des Baums ist
- Im schlimmsten Fall, H kann dasselbe sein wie N (wenn der Baum ein schiefer Baum ist)
- Im besten Fall, H kann dasselbe sein wie ruhig (wenn der Baum ein vollständiger Baum ist)
Anwendungsfälle von Inorder Traversal:
Wenn im Fall von BST (Binary Search Tree) zu irgendeinem Zeitpunkt die Notwendigkeit besteht, die Knoten in nicht absteigender Reihenfolge abzurufen, ist es am besten, eine Durchquerung in der Reihenfolge zu implementieren.
In Verbindung stehende Artikel:
- Arten von Baumdurchquerungen
- Iterative Inorder-Traversierung
- Konstruieren Sie einen Binärbaum aus der Vorbestellungs- und Inorder-Traversierung
- Morris-Durchquerung für die Durchquerung eines Baumes in geordneter Reihenfolge
- Inorder-Traversal ohne Rekursion