Užsakymo perėjimas apibrėžiamas kaip tipas medžių perėjimo technika kuri seka kairę-šaknį-dešinę modelį, kad:
- Pirmiausia kertamas kairysis pomedis
- Tada perkeliamas to pomedžio šakninis mazgas
- Galiausiai pervažiuojamas dešinysis pomedis
Užsakymo perėjimas
Dvejetainio medžio netvarkingo judėjimo algoritmas
Inorder perėjimo algoritmas parodytas taip:
Eilė (šaknis):
- Atlikite 2–4 veiksmus, kol šaknis != NULL
- Eilės tvarka (šaknis -> kairėn)
- Rašyti root -> data
- Eilės tvarka (šaknis -> dešinėn)
- Pabaigos kilpa
Kaip veikia Inorder Traversal of Binary Tree?
Apsvarstykite šį medį:
Vlc media player atsisiųsti youtube
Dvejetainio medžio pavyzdys
Jei šiame dvejetainiame medyje atliksime eilės eiliškumą, tada perėjimas bus toks:
1 žingsnis: Perėjimas nuo 1 pereis į kairįjį pomedį, ty 2, tada nuo 2 iki kairiojo pomedžio šaknies, ty 4. Dabar 4 neturi kairiojo pomedžio, todėl jis bus aplankytas. Jis taip pat neturi tinkamo pomedžio. Taigi daugiau nereikia pereiti nuo 4
Aplankytas 4 mazgas
2 žingsnis: Kadangi kairysis 2 pomedis yra visiškai aplankytas, dabar jis nuskaito 2 mazgo duomenis prieš pereidamas prie dešiniojo pomedžio.
Aplankytas 2 mazgas
3 veiksmas: Dabar bus perkeltas dešinysis 2 pomedis, t. y. pereikite į 5 mazgą. 5 mazgo kairiojo pomedžio nėra, todėl jis aplankomas, o po to grįžtama, nes 5 mazgo dešiniojo pomedžio nėra.
Aplankytas 5 mazgas
4 veiksmas: Kadangi yra kairysis mazgo 1 pomedis, bus aplankyta pati šaknis, ty mazgas 1.
Aplankytas 1 mazgas
5 veiksmas: Lankomas kairysis 1 mazgo pomedis ir pats mazgas. Taigi dabar bus perkeltas dešinysis 1 pomedis, t. y. pereikite į 3 mazgą. Kadangi 3 mazgas neturi kairiojo pomedžio, jis bus lankomas.
Aplankytas 3 mazgas
6 veiksmas: Lankomas kairysis 3 mazgo pomedis ir pats mazgas. Taigi pereikite prie dešiniojo pomedžio ir aplankykite 6 mazgą. Dabar perėjimas baigiasi, nes visi mazgai yra pereiti.
Pervažiuojamas visas medis
Taigi mazgų perėjimo tvarka yra 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Programa, skirta įgyvendinti „Inorder Traversal of Binary Tree“:
Žemiau pateikiamas eilės perėjimo kodo įgyvendinimas:
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->kairėje);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->teisė); } // Tvarkyklės kodas int main() { struct Node* root = new Node(1); root->left = naujas mazgas (2); root->right = naujas mazgas (3); šaknis->kairė->kairė = naujas mazgas(4); šaknis->kairė->dešinė = naujas mazgas(5); root->right->right = naujas mazgas (6); // Funkcijos iškvietimas<< 'Inorder traversal of binary tree is:
'; printInorder(root); return 0; }> |
>
>
Java
git pridėti viską
// 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)> |
>
>
C#
pakeičiant eilutę Java
// 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);> |
>
>Išvestis
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Paaiškinimas:
Kaip veikia įsakymo perėjimas
Python programa dvejetainei paieškai
Sudėtingumo analizė:
Laiko sudėtingumas: O(N) čia N yra bendras mazgų skaičius. Nes jis bent kartą kerta visus mazgus.
Pagalbinė erdvė: O(1), jei neatsižvelgiama į rekursijos kamino erdvę. Kitu atveju O(h), kur h yra medžio aukštis
- Blogiausiu atveju, h gali būti toks pat kaip N (kai medis yra pasviręs)
- Geriausiu atveju, h gali būti toks pat kaip Ramus (kai medis yra pilnas medis)
Inorder Traversal naudojimo atvejai:
BST (dvejetainės paieškos medžio) atveju, jei bet kuriuo metu reikia gauti mazgus nemažėjančia tvarka, geriausias būdas yra įgyvendinti inorder traversal.
Susiję straipsniai:
- Medžių apvažiavimų rūšys
- Iteratyvus eiliškumo perėjimas
- Sukurkite dvejetainį medį iš išankstinio užsakymo ir eilės eilės
- Morris traversal už inorder traversal per medį
- Inorder perėjimas be rekursijos