Tilauksen läpikulku määritellään tyypiksi puun läpikulkutekniikka joka noudattaa vasen-juuri-oikea -mallia siten, että:
- Vasen alipuu ajetaan ensin
- Sitten alipuun juurisolmu ajetaan
- Lopuksi ajetaan oikea alipuu
Tilauksen läpikulku
Algoritmi binaaripuun inorder traversalille
Inorder traversal -algoritmi esitetään seuraavasti:
Järjestys(juuri):
- Noudata vaiheita 2–4, kunnes root != NULL
- Järjestä (juuri -> vasen)
- Kirjoita root -> data
- Järjestä (juuri -> oikealle)
- Lopeta silmukka
Kuinka binaaripuun Inorder Traversal toimii?
Harkitse seuraavaa puuta:
keskiarvo vs keskiarvo
Esimerkki binaaripuusta
Jos suoritamme tässä binääripuussa järjestyskierroksen, läpikulku on seuraava:
Vaihe 1: Läpikulku siirtyy luvusta 1 sen vasempaan alipuuhun eli 2:een, sitten 2:sta sen vasempaan alipuun juureen, eli 4. Nyt 4:ssä ei ole vasenta alipuuta, joten siinä käydään. Siinä ei myöskään ole oikeaa alipuuta. Joten ei enää läpikulkua 4
Solmussa 4 käydään
Vaihe 2: Koska 2:n vasemmassa alipuussa käydään kokonaan, se luki nyt solmun 2 tiedot ennen siirtymistä oikeaan alipuuhun.
Node 2 on vierailtu
Vaihe 3: Nyt ajetaan 2:n oikea alipuu, eli siirrytään solmuun 5. Solmulle 5 ei ole vasenta alipuuta, joten siinä käydään ja sen jälkeen läpikulku tulee takaisin, koska solmun 5 oikeaa alipuuta ei ole.
Node 5 on vierailtu
Vaihe 4: Kuten solmun 1 vasen alipuu on, käydään itse juurissa, eli solmussa 1.
Solmussa 1 käydään
Vaihe 5: Solmun 1 vasemmassa alipuussa ja itse solmussa käydään. Joten nyt ajetaan 1:n oikea alipuu, eli siirrytään solmuun 3. Koska solmussa 3 ei ole vasenta alipuuta, siinä käydään.
Solmussa 3 käydään
Vaihe 6: Solmun 3 vasemmassa alipuussa ja itse solmussa käydään. Siirrä siis oikeaan alipuuhun ja käy solmussa 6. Nyt läpikulku päättyy, kun kaikki solmut on ajettu.
Koko puu ajetaan läpi
Joten solmujen läpikulkujärjestys on 4 -> 2 -> 5 -> 1 -> 3 -> 6 .
Ohjelma toteuttaa Inorder Traversal of Binary Tree:
Alla on järjestyksen läpikäymisen kooditoteutus:
C++
strint to int
// 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->vasemmalle);> >// Now deal with the node> >cout ' '; // Then recur on right subtree printInorder(node->oikea); } // Ohjainkoodi int main() { struct Solmu* root = new Node(1); juuri->vasen = uusi solmu(2); juuri->oikea = uusi solmu(3); juuri->vasen->vasen = uusi solmu(4); juuri->vasen->oikea = uusi solmu(5); juuri->oikea->oikea = uusi solmu(6); // Funktion kutsu<< '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> |
>
>
Python 3
string.compare c#
# 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#
piilotetut sovellukset
// 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);> >}> }> |
>
>
numpy dot tuote
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);> |
>
>Lähtö
Inorder traversal of binary tree is: 4 2 5 1 3 6>
Selitys:
Kuinka tilauksen läpikulku toimii
Monimutkaisuusanalyysi:
Aika monimutkaisuus: O(N) missä N on solmujen kokonaismäärä. Koska se kulkee kaikkien solmujen läpi vähintään kerran.
Aputila: O(1), jos rekursiopinotilaa ei oteta huomioon. Muussa tapauksessa O(h), missä h on puun korkeus
- Pahimmassa tapauksessa h voi olla sama kuin N (kun puu on vinossa puu)
- Parhaassa tapauksessa h voi olla sama kuin rauhoittaa (kun puu on täydellinen puu)
Inorder Traversalin käyttötapaukset:
BST:n (Binary Search Tree) tapauksessa, jos milloin tahansa on tarve saada solmut ei-laskevassa järjestyksessä, paras tapa on toteuttaa inorder traversal.
Aiheeseen liittyvät artikkelit:
- Puun läpikulkutyypit
- Iteratiivinen järjestyksen läpikulku
- Muodosta binääripuu ennakkotilauksesta ja inorder traversalista
- Morris-läpikulku puun inorder-läpikulkua varten
- Tilaa läpikulku ilman rekursiota