logo

TechCodeview

Postorder Traversal binárneho stromu

Prenos poštovej poukážky je definovaný ako typ prechod cez strom ktorý sa riadi zásadou Left-Right-Root tak, že pre každý uzol:

  • Najprv sa prejde ľavý podstrom
  • Potom sa prejde pravý podstrom
  • Nakoniec sa prejde koreňový uzol podstromu
Prenos poštovej poukážky

Prenos poštovej poukážky



Algoritmus pre prechod binárneho stromu postorderom:

Algoritmus pre prechod postorderom je znázornený takto:

Poštová objednávka (koreň):

  1. Postupujte podľa krokov 2 až 4, kým root != NULL
  2. Postorder (koreň -> vľavo)
  3. Postorder (koreň -> vpravo)
  4. Napíšte root -> údaje
  5. Koniec slučky

Ako funguje Postorder Traversal binárneho stromu?

Zvážte nasledujúci strom:



Príklad binárneho stromu

Príklad binárneho stromu

Ak vykonáme prechod postorderom v tomto binárnom strome, prechod bude nasledujúci:

Krok 1: Prechod prejde z 1 do svojho ľavého podstromu, t. j. 2, potom z 2 do svojho ľavého koreňa podstromu, t. j. 4. Teraz 4 nemá žiadny podstrom, takže bude navštívený.



Uzol 4 je navštívený

Uzol 4 je navštívený

Krok 2: Keďže ľavý podstrom 2 je úplne navštívený, teraz bude prechádzať pravým podstromom 2, t. j. presunie sa na 5. Keďže neexistuje žiadny podstrom 5, bude navštívený.

Uzol 5 je navštívený

Uzol 5 je navštívený

Krok 3: Teraz sú navštívené ľavý aj pravý podstrom uzla 2. Takže teraz navštívte samotný uzol 2.

Uzol 2 je navštívený

Uzol 2 je navštívený

triedenie vloženia

Krok 4: Pri prechode ľavým podstromom uzla 1 sa teraz presunie do pravého koreňa podstromu, t.j. 3. Uzol 3 nemá žiadny ľavý podstrom, takže bude prechádzať pravým podstromom, t. j. 6. Uzol 6 nemá žiadny podstrom a tak je navštevovaný.

Uzol 6 je navštívený

Uzol 6 je navštívený

Krok 5: Všetky podstromy uzla 3 sú prekročené. Takže teraz je navštívený uzol 3.

Uzol 3 je navštívený

Uzol 3 je navštívený

Krok 6: Keďže sa prešli všetky podstromy uzla 1, teraz je čas navštíviť uzol 1 a potom sa prechod skončí, keď sa prejde celý strom.

Navštívený je kompletný strom

Navštívený je kompletný strom

Takže poradie prechodu uzlov je 4 -> 5 -> 2 -> 6 -> 3 -> 1 .

Program na implementáciu Postorder Traversal binárneho stromu

Nižšie je uvedená implementácia kódu postorder traversal:

C++


java previesť reťazec na celé číslo



// 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->vľavo);> >// Then recur on right subtree> >printPostorder(node->vpravo);> >// Now deal with the node> >cout ' '; } // Driver code 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); // Volanie funkcie 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

zadarmo vs zadarmo




# 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();> 

>

>

Výkon 

Postorder traversal of binary tree is: 4 5 2 6 3 1>

Vysvetlenie:

Ako funguje prechod zásielky

Ako funguje prechod zásielky

Analýza zložitosti:

Časová zložitosť: O(N), kde N je celkový počet uzlov. Pretože aspoň raz prejde cez všetky uzly.
Pomocný priestor: O(1), ak sa neberie do úvahy priestor zásobníka rekurzie. V opačnom prípade O(h), kde h je výška stromu

najlepšie hentai
  • V najhoršom prípade h môže byť rovnaký ako N (keď je strom skosený strom)
  • V najlepšom prípade h môže byť rovnaký ako pokojne (keď je strom úplný strom)

Prípady použitia Postorder Traversal:

Niektoré prípady použitia prechodu postorderom sú:

  • Používa sa na vymazanie stromu.
  • Je tiež užitočné získať výraz postfix zo stromu výrazov.

Súvisiace články:

  • Typy prechodov cez stromy
  • Iteratívne prechádzanie postorderom (pomocou dvoch zásobníkov)
  • Iteratívne prechádzanie postorderom (pomocou jedného zásobníka)
  • Postorder Binary Tree bez rekurzie a bez zásobníka
  • Nájsť Postorder traversal BST z preorder traversal
  • Morris traversal pre zásielkový obchod
  • Vytlačte prechod postordera z prechodu predobjednávky a prechodu po poradí