Postorder traversal definieras som en typ av trädpassering som följer Vänster-Höger-Root-policyn så att för varje nod:
- Det vänstra underträdet korsas först
- Sedan korsas det högra underträdet
- Slutligen korsas underträdets rotnod
Postorder traversal
Algoritm för postorderpassering av binärt träd:
Algoritmen för postorder-traversering visas enligt följande:
Postorder(root):
- Följ steg 2 till 4 tills root != NULL
- Postorder (root -> vänster)
- Postorder (root -> höger)
- Skriv root -> data
- Slutslinga
Hur fungerar Postorder Traversal of Binary Tree?
Tänk på följande träd:
Exempel på binärt träd
Om vi utför en postorder-genomgång i det här binära trädet, så kommer övergången att vara som följer:
Steg 1: Traverseringen kommer att gå från 1 till dess vänstra underträd, dvs. 2, sedan från 2 till dess vänstra underträdsrot, d.v.s. 4. Nu har 4 inget underträd, så det kommer att besökas.
Nod 4 besöks
Steg 2: Eftersom det vänstra underträdet av 2 besöks fullständigt, kommer det nu att korsa det högra underträdet av 2, dvs. det kommer att flyttas till 5. Eftersom det inte finns något underträd av 5, kommer det att besökas.
Nod 5 besöks
Steg 3: Nu besöks både vänster och höger underträd av nod 2. Så besök nu själva nod 2.
Nod 2 besöks
Steg 4: När det vänstra underträdet av nod 1 korsas, kommer det nu att flyttas till höger underträdsrot, dvs. 3. Nod 3 har inget vänster underträd, så det kommer att korsa det högra underträdet, dvs. 6. Nod 6 har inget underträd och så det är besökt.
Nod 6 besöks
Steg 5: Alla underträden i nod 3 korsas. Så nu är nod 3 besökt.
Nod 3 besöks
Steg 6: Eftersom alla underträd i nod 1 korsas, är det nu dags för nod 1 att besökas och genomgången avslutas efter det när hela trädet korsas.
Hela trädet besöks
Så ordningen för korsning av noder är 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Program för att implementera Postorder Traversal of Binary Tree
Nedan är kodimplementeringen av postorderövergången:
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->vänster);> >// Then recur on right subtree> >printPostorder(node->höger);> >// Now deal with the node> >cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->vänster = ny Node(2); root->right = new Node(3); root->left->left = new Node(4); root->vänster->höger = ny Node(5); root->right->right = new Node(6); // Funktionsanrop 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> |
nick pulos svart blixt
>
>
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
omvandla sträng till int
// 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();> |
>
>Produktion
Postorder traversal of binary tree is: 4 5 2 6 3 1>
Förklaring:
How postorder traversal works
Komplexitetsanalys:
Tidskomplexitet: O(N) där N är det totala antalet noder. Eftersom den korsar alla noder minst en gång.
Hjälputrymme: O(1) om inget rekursionsstackutrymme beaktas. Annars O(h) där h är trädets höjd
- I värsta fall, h kan vara samma som N (när trädet är ett skevt träd)
- I bästa fall, h kan vara samma som lugna (när trädet är ett komplett träd)
Användningsfall av Postorder Traversal:
Några användningsfall av postorderpassering är:
- Detta används för att radera träd.
- Det är också användbart att hämta postfix-uttrycket från ett uttrycksträd.
Relaterade artiklar:
- Typer av trädövergångar
- Iterativ postorderövergång (med två stackar)
- Iterativ postorderövergång (med en stack)
- Postorder av binärt träd utan rekursion och utan stack
- Hitta Postorder-traversal av BST från preorder-traversal
- Morris traversal for Postorder
- Skriv ut postorder-traversal från förbeställd och inorder-traversal