POSTORDER GENNEMKØRSEL AF BINÆRT TRÆ - TECHCODEVIEW.COM

Postordregennemgang er defineret som en type trægennemgang som følger venstre-højre-rod-politikken, således at for hver node:

Det venstre undertræ krydses først

Derefter krydses det højre undertræ

Til sidst krydses undertræets rodknude

Postordregennemgang

Algoritme for postorder-gennemgang af binært træ:

Algoritmen for postorder-gennemgang er vist som følger:

Postordre (rod):

Følg trin 2 til 4 indtil root != NULL

Postordre (rod -> venstre)

Postordre (rod -> højre)

Skriv root -> data

Slut sløjfe

Hvordan fungerer Postorder Traversal of Binary Tree?

Overvej følgende træ:

Eksempel på binært træ

Hvis vi udfører en postorder traversal i dette binære træ, så vil gennemgangen være som følger:

Trin 1: Gennemgangen vil gå fra 1 til dets venstre undertræ, dvs. 2, derefter fra 2 til dets venstre undertrærod, dvs. 4. Nu har 4 ikke noget undertræ, så det vil blive besøgt.

Node 4 er besøgt

Trin 2: Da det venstre undertræ af 2 besøges fuldstændigt, vil det nu krydse det højre undertræ af 2, dvs. det vil flytte til 5. Da der ikke er noget undertræ på 5, vil det blive besøgt.

Node 5 er besøgt

Trin 3: Nu er både venstre og højre undertræ af node 2 besøgt. Så besøg nu selve node 2.

Node 2 er besøgt

Trin 4: Når det venstre undertræ af node 1 krydses, vil det nu flytte til højre undertrærod, dvs. 3. Node 3 har ikke noget venstre undertræ, så det vil krydse det højre undertræ, dvs. 6. Node 6 har intet undertræ og så den bliver besøgt.

Node 6 er besøgt

Trin 5: Alle undertræerne i node 3 gennemløbes. Så nu er node 3 besøgt.

Node 3 er besøgt

Trin 6: Da alle undertræerne i node 1 gennemløbes, er det nu tid til, at node 1 skal besøges, og gennemkørslen slutter derefter, da hele træet krydses.

Hele træet er besøgt

Så rækkefølgen af krydsning af noder er 4 -> 5 -> 2 -> 6 -> 3 -> 1 .

Program til at implementere Postorder Traversal of Binary Tree

Nedenfor er kodeimplementeringen af postordre-gennemgangen:

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->venstre);> > // Then recur on right subtree> > printPostorder(node->højre);> > // Now deal with the node> >

cout ' '; } // Driver code int main() {  struct Node* root = new Node(1);  root->venstre = ny node(2);  root->right = ny node(3);  root->venstre->venstre = ny node(4);  root->venstre->højre = ny node(5);  root->right->right = new Node(6);  // Funktionskald 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();>

Produktion

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

Forklaring:

Sådan fungerer postordregennemgang

Kompleksitetsanalyse:

Tidskompleksitet: O(N) hvor N er det samlede antal knudepunkter. Fordi den krydser alle noderne mindst én gang.
Hjælpeplads: O(1), hvis der ikke tages hensyn til et rekursionsstabelrum. Ellers O(h), hvor h er højden af træet

I værste fald, h kan være det samme som N (når træet er et skævt træ)
I bedste tilfælde, h kan være det samme som berolige (når træet er et komplet træ)