Durchquerung von Postanweisungen ist als eine Art von definiert Baumdurchquerung Dies folgt der Left-Right-Root-Richtlinie, sodass für jeden Knoten Folgendes gilt:
- Der linke Teilbaum wird zuerst durchlaufen
- Anschließend wird der rechte Teilbaum durchlaufen
- Abschließend wird der Wurzelknoten des Teilbaums durchlaufen
Durchquerung von Postanweisungen
Algorithmus für die Postorder-Traversierung des Binärbaums:
Der Algorithmus für die Postorder-Traversierung wird wie folgt dargestellt:
Postanweisung (Wurzel):
- Befolgen Sie die Schritte 2 bis 4, bis root != NULL ist
- Postorder (root -> links)
- Postorder (root -> rechts)
- Root -> Daten schreiben
- Schleife beenden
Wie funktioniert die Postorder-Traversierung des Binärbaums?
Betrachten Sie den folgenden Baum:
Beispiel eines Binärbaums
Wenn wir in diesem Binärbaum eine Postorder-Traversierung durchführen, sieht die Traversierung wie folgt aus:
Schritt 1: Die Durchquerung erfolgt von 1 zu seinem linken Teilbaum, also 2, dann von 2 zu seiner linken Teilbaumwurzel, also 4. Jetzt hat 4 keinen Teilbaum, also wird er besucht.
Knoten 4 wird besucht
Schritt 2: Da der linke Teilbaum von 2 vollständig besucht ist, durchläuft er nun den rechten Teilbaum von 2, d. h. er bewegt sich zu 5. Da es keinen Teilbaum von 5 gibt, wird er besucht.
Knoten 5 wird besucht
Schritt 3: Nun werden sowohl der linke als auch der rechte Teilbaum von Knoten 2 besucht. Besuchen Sie nun Knoten 2 selbst.
Knoten 2 wird besucht
Schritt 4: Wenn der linke Teilbaum von Knoten 1 durchquert wird, bewegt er sich nun zur rechten Teilbaumwurzel, d. h. 3. Knoten 3 hat keinen linken Teilbaum, also wird er den rechten Teilbaum durchqueren, d. h. 6. Knoten 6 hat keinen Teilbaum und also wird es besucht.
Knoten 6 wird besucht
Schritt 5: Alle Teilbäume von Knoten 3 werden durchlaufen. Jetzt wird Knoten 3 besucht.
Knoten 3 wird besucht
Schritt 6: Da alle Teilbäume von Knoten 1 durchquert werden, ist es nun an der Zeit, Knoten 1 zu besuchen, und die Durchquerung endet danach, wenn der gesamte Baum durchquert wird.
Der komplette Baum wird besichtigt
Die Reihenfolge der Knotendurchquerung ist also 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Programm zur Implementierung von Postorder Traversal of Binary Tree
Nachfolgend finden Sie die Code-Implementierung des Postorder-Traversals:
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->links);> >// Then recur on right subtree> >printPostorder(node->rechts);> >// Now deal with the node> >cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->links = neuer Knoten(2); root->right = new Node(3); root->left->left = new Node(4); root->left->right = new Node(5); root->right->right = new Node(6); // Funktionsaufruf 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#
str.substring in Java
// 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();> |
>
>Ausgabe
Postorder traversal of binary tree is: 4 5 2 6 3 1>
Erläuterung:
So funktioniert die Durchquerung des Versandhandels
Komplexitätsanalyse:
Zeitkomplexität: O(N) wobei N die Gesamtzahl der Knoten ist. Weil es alle Knoten mindestens einmal durchläuft.
Hilfsraum: O(1), wenn kein Rekursionsstapelplatz berücksichtigt wird. Ansonsten O(h), wobei h die Höhe des Baums ist
- Im schlimmsten Fall, H kann dasselbe sein wie N (wenn der Baum ein schiefer Baum ist)
- Im besten Fall, H kann dasselbe sein wie ruhig (wenn der Baum ein vollständiger Baum ist)
Anwendungsfälle von Postorder Traversal:
Einige Anwendungsfälle der Postorder-Traversierung sind:
- Dies wird zum Löschen des Baums verwendet.
- Es ist auch nützlich, den Postfix-Ausdruck aus einem Ausdrucksbaum abzurufen.
In Verbindung stehende Artikel:
- Arten von Baumdurchquerungen
- Iterative Postorder-Traversierung (mit zwei Stapeln)
- Iterative Postorder-Durchquerung (mit einem Stapel)
- Nachbestellung des Binärbaums ohne Rekursion und ohne Stapel
- Finden Sie Postorder-Traversal von BST aus Preorder-Traversal
- Morris-Durchquerung für den Versandhandel
- Postorder-Traversal aus Preorder und Inorder-Traversal drucken