Prehod po naročilu binarnega drevesa
Prehod poštnega naloga je opredeljena kot vrsta prečenje drevesa ki sledi politiki Left-Right-Root, tako da za vsako vozlišče:
- Najprej se prečka levo poddrevo
- Nato se prečka desno poddrevo
- Na koncu se prečka korensko vozlišče poddrevesa
Prehod poštnega naloga
Algoritem za prehod po naročilu binarnega drevesa:
Algoritem za prehod po naročilu je prikazan takole:
Poštna nakaznica (koren):
- Sledite korakom od 2 do 4, dokler ni root != NULL
- Postorder (koren -> levo)
- Postorder (koren -> desno)
- Zapiši root -> data
- Končna zanka
Kako deluje postorder traversal binarnega drevesa?
Razmislite o naslednjem drevesu:
Primer binarnega drevesa
Če izvedemo prehod po naročilu v tem binarnem drevesu, bo prehod naslednji:
Korak 1: Prehod bo šel od 1 do njegovega levega poddrevesa, tj. 2, nato od 2 do njegovega levega korena poddrevesa, tj. 4. Zdaj 4 nima poddrevesa, zato bo obiskano.
Vozlišče 4 je obiskano
2. korak: Ker je levo poddrevo 2 obiskano v celoti, bo zdaj prečkalo desno poddrevo 2, tj. premaknilo se bo na 5. Ker ni nobenega poddrevesa 5, bo obiskano.
Vozlišče 5 je obiskano
3. korak: Zdaj sta obiskana tako levo kot desno poddrevo vozlišča 2. Zdaj obiščite samo vozlišče 2.
Vozlišče 2 je obiskano
4. korak: Ko se prečka levo poddrevo vozlišča 1, se bo zdaj premaknilo v desni koren poddrevesa, tj. 3. Vozlišče 3 nima levega poddrevesa, zato bo prečkalo desno poddrevo, tj. 6. Vozlišče 6 nima poddrevesa in zato je obiskano.
Vozlišče 6 je obiskano
5. korak: Prehodna so vsa poddrevesa vozlišča 3. Torej je zdaj vozlišče 3 obiskano.
Vozlišče 3 je obiskano
6. korak: Ker so prečkana vsa poddrevesa vozlišča 1, je zdaj čas, da se obišče vozlišče 1, nato pa se prečkanje konča, saj je prečkano celotno drevo.
Obišče se celotno drevo
Vrstni red prečkanja vozlišč je torej 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Program za izvajanje Postorder Traversal binarnega drevesa
Spodaj je implementacija kode prehoda po naročilu:
C++
// C++ program for postorder 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 postorder traversal> void> printPostorder(> struct> Node* node)> {> > if> (node == NULL)> > return> ;> > // First recur on left subtree> > printPostorder(node->levo);> > // Then recur on right subtree> > printPostorder(node->desno);> > // Now deal with the node> > cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->levo = novo vozlišče (2); root->desno = novo vozlišče(3); root->left->left = novo vozlišče(4); koren->levo->desno = novo vozlišče(5); root->desno->desno = novo vozlišče(6); // Klic funkcije cout < < 'Postorder traversal of binary tree is:
'; printPostorder(root); return 0; }> |
Java
// Java program for postorder 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> ;> > }> }> class> GFG {> > > // Function to print postorder traversal> > static> void> printPostorder(Node node)> > {> > if> (node ==> null> )> > return> ;> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > System.out.print(node.data +> ' '> );> > }> > // 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(> 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by prasad264> |
Python3
# Python program for postorder traversals> # Structure of a Binary Tree Node> class> Node:> > def> __init__(> self> , v):> > self> .data> => v> > self> .left> => None> > self> .right> => None> # Function to print postorder traversal> def> printPostorder(node):> > if> node> => => None> :> > return> > # First recur on left subtree> > printPostorder(node.left)> > # Then recur on right subtree> > printPostorder(node.right)> > # Now deal with the node> > print> (node.data, end> => ' '> )> # 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> (> 'Postorder traversal of binary tree is:'> )> > printPostorder(root)> |
C#
// C# program for postorder 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> ;> > }> }> public> class> GFG {> > // Function to print postorder traversal> > static> void> printPostorder(Node node)> > {> > if> (node ==> null> )> > return> ;> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > Console.Write(node.data +> ' '> );> > }> > static> public> void> Main()> > {> > // Code> > 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(> > 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by karthik.> |
Javascript
// Structure of a Binary Tree Node> class Node {> > constructor(v) {> > this> .data = v;> > this> .left => null> ;> > this> .right => null> ;> > }> }> // Function to print postorder traversal> function> printPostorder(node) {> > if> (node ==> null> ) {> > return> ;> > }> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > console.log(node.data +> ' '> );> }> // Driver code> function> main() {> > let 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(> 'Postorder traversal of binary tree is:
'> );> > printPostorder(root);> }> main();> |
Izhod
Postorder traversal of binary tree is: 4 5 2 6 3 1
Pojasnilo:
Kako deluje prečkanje naročil po pošti
Analiza kompleksnosti:
Časovna zapletenost: O(N), kjer je N skupno število vozlišč. Ker vsaj enkrat prečka vsa vozlišča.
Pomožni prostor: O(1), če ni upoštevan noben prostor rekurzijskega sklada. V nasprotnem primeru O(h), kjer je h višina drevesa
- V najslabšem primeru h lahko enako kot n (ko je drevo poševno drevo)
- V najboljšem primeru h lahko enako kot miren (ko je drevo popolno drevo)
Primeri uporabe Postorder Traversal:
Nekateri primeri uporabe prečkanja po naročilu so:
- To se uporablja za brisanje drevesa.
- Koristno je tudi pridobiti postfiksni izraz iz izraznega drevesa.
Povezani članki:
- Vrste prečkanja dreves
- Iterativno prečkanje po naročilu (z uporabo dveh skladov)
- Iterativno prečkanje po naročilu (z uporabo enega sklada)
- Postorder binarnega drevesa brez rekurzije in brez sklada
- Poiščite prehod po naročilu BST iz prehoda pred naročilom
- Morrisov prehod za naročilo po pošti
- Natisnite prehod po naročilu iz prednaročila in prehod po vrstnem redu
