Gennemgang af uorden er defineret som en type trægennemløbsteknik som følger venstre-rod-højre-mønsteret, således at:
- Det venstre undertræ krydses først
- Derefter krydses rodknuden for det undertræ
- Til sidst krydses det højre undertræ
Gennemgang af uorden
Algoritme for Inorder Traversal af binært træ
Algoritmen for gennemløb af uorden er vist som følger:
Inorder (rod):
- Følg trin 2 til 4 indtil root != NULL
- I rækkefølge (rod -> venstre)
- Skriv root -> data
- I rækkefølge (rod -> højre)
- Slut sløjfe
Hvordan virker Inorder Traversal of Binary Tree?
Overvej følgende træ:
Eksempel på binært træ
Hvis vi udfører en uordensgennemgang i dette binære træ, vil gennemgangen være som følger:
Trin 1: Gennemgangen vil gå fra 1 til dets venstre undertræ, dvs. 2, derefter fra 2 til dets venstre undertrærod, dvs. 4. Nu har 4 ikke noget venstre undertræ, så det vil blive besøgt. Den har heller ikke noget ret undertræ. Så ikke mere traversering fra 4
Node 4 er besøgt
Trin 2: Da det venstre undertræ af 2 besøges fuldstændigt, læser det nu data fra node 2, før det flytter til dets højre undertræ.
Node 2 er besøgt
Trin 3: Nu vil det højre undertræ af 2 blive krydset, dvs. flytte til node 5. For node 5 er der ikke noget venstre undertræ, så det bliver besøgt, og derefter kommer gennemgangen tilbage, fordi der ikke er noget højre undertræ af node 5.
Node 5 er besøgt
Trin 4: Som det venstre undertræ af node 1 er, vil selve roden, dvs. node 1 blive besøgt.
Node 1 er besøgt
Trin 5: Venstre undertræ af node 1 og selve noden besøges. Så nu vil det højre undertræ af 1 blive krydset, dvs. flytte til node 3. Da node 3 ikke har noget venstre undertræ, så bliver det besøgt.
Node 3 er besøgt
Trin 6: Det venstre undertræ af node 3 og selve noden besøges. Så gå til det højre undertræ og besøg knudepunkt 6. Nu slutter gennemkørslen, når alle knuderne krydses.
Hele træet krydses
Så rækkefølgen af krydsning af noder er 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Program til at implementere Inorder Traversal of Binary Tree:
Nedenfor er kodeimplementeringen af inorder-gennemgangen:
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->venstre);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->højre); } // Driverkode int main() { struct Node* root = new Node(1); root->venstre = ny node(2); root->right = ny node(3); root->venstre->venstre = ny node(4); root->venstre->højre = ny node(5); root->right->right = new Node(6); // Funktionskald cout<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
konverter char til streng
// 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)> |
>
>
java er tom
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);> |
>
>Produktion
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Forklaring:
Hvordan inorder traversal virker
Kompleksitetsanalyse:
Tidskompleksitet: O(N) hvor N er det samlede antal knudepunkter. Fordi den krydser alle noderne mindst én gang.
Hjælpeplads: O(1), hvis der ikke tages hensyn til et rekursionsstabelrum. Ellers O(h), hvor h er højden af træet
- I værste fald, h kan være det samme som N (når træet er et skævt træ)
- I bedste tilfælde, h kan være det samme som berolige (når træet er et komplet træ)
Brugstilfælde af Inorder Traversal:
I tilfælde af BST (Binary Search Tree), hvis der på noget tidspunkt er behov for at få noderne i ikke-faldende rækkefølge, er den bedste måde at implementere en inorder-gennemgang.
Relaterede artikler:
- Typer af trægennemgange
- Iterativ krydsning af uorden
- Konstruer binært træ ud fra preorder og inorder traversal
- Morris-traversal for uordensgennemgang af træ
- Uordensgennemgang uden rekursion