Parcursul prin comanda postala este definit ca un tip de traversarea copacilor care urmează politica Stânga-Dreapta-Rădăcină astfel încât pentru fiecare nod:
- Subarborele din stânga este parcurs mai întâi
- Apoi se parcurge subarborele din dreapta
- În cele din urmă, nodul rădăcină al subarborelui este parcurs
Parcursul prin comanda postala
Algoritm pentru traversarea după ordinea arborelui binar:
Algoritmul pentru traversarea postcomandă este prezentat după cum urmează:
Comanda poștală (rădăcină):
- Urmați pașii de la 2 la 4 până la root != NULL
- Postorder (rădăcină -> stânga)
- Postorder (rădăcină -> dreapta)
- Scrie root -> date
- Sfârșit bucla
Cum funcționează traversarea după ordinea arborelui binar?
Luați în considerare următorul arbore:
Exemplu de arbore binar
Dacă efectuăm o traversare post-comandă în acest arbore binar, atunci traversarea va fi după cum urmează:
Pasul 1: Parcursul va merge de la 1 la subarborele din stânga, adică 2, apoi de la 2 la rădăcina din stânga, adică 4. Acum 4 nu are subarborele, așa că va fi vizitat.
Nodul 4 este vizitat
Pasul 2: Deoarece subarborele din stânga al lui 2 este vizitat complet, acum va traversa subarborele din dreapta al lui 2, adică se va muta la 5. Deoarece nu există subarborele lui 5, acesta va fi vizitat.
Nodul 5 este vizitat
Pasul 3: Acum sunt vizitate atât subarborele din stânga, cât și din dreapta ale nodului 2. Așa că acum vizitați nodul 2 în sine.
Nodul 2 este vizitat
Pasul 4: Pe măsură ce subarborele din stânga al nodului 1 este traversat, acesta se va muta acum la rădăcina subarborelui din dreapta, adică 3. Nodul 3 nu are niciun subarborele din stânga, deci va traversa subarborele din dreapta, adică 6. Nodul 6 nu are subarborele și deci este vizitat.
Nodul 6 este vizitat
Pasul 5: Toți subarborele nodului 3 sunt parcurși. Deci acum nodul 3 este vizitat.
Nodul 3 este vizitat
string.format javaPasul 6: Deoarece toți subarborele nodului 1 sunt parcurși, acum este timpul ca nodul 1 să fie vizitat și traversarea se termină după aceea, pe măsură ce întregul arbore este traversat.
Se vizitează arborele complet
Deci ordinea de parcurgere a nodurilor este 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Program pentru implementarea Postorder Traversal of Binary Tree
Mai jos este implementarea codului a traversării post-comandă:
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->stânga);> >// Then recur on right subtree> >printPostorder(node->dreapta);> >// Now deal with the node> >cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->stânga = nou Nod(2); root->right = nou Nod(3); rădăcină->stânga->stânga = nou Nod(4); rădăcină->stânga->dreapta = nou Nod(5); root->right->right = nou Nod(6); // Apelul funcției cout<< 'Postorder traversal of binary tree is:
'; printPostorder(root); return 0; }> |
Android poate juca gamepigeon
>
>
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)> |
>
scaner java
>
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();> |
>
>Ieșire
Postorder traversal of binary tree is: 4 5 2 6 3 1>
Explicaţie:
Cum funcționează traversarea comenzilor prin corespondență
Analiza complexității:
Complexitatea timpului: O(N) unde N este numărul total de noduri. Pentru că străbate toate nodurile cel puțin o dată.
Spațiu auxiliar: O(1) dacă nu se ia în considerare spațiul stivei recursive. În caz contrar, O(h) unde h este înălțimea copacului
contacte blocate
- În cel mai rău caz, h poate fi la fel ca N (când copacul este un copac înclinat)
- În cel mai bun caz, h poate fi la fel ca calm (când copacul este un copac complet)
Cazuri de utilizare ale traversării post-comandă:
Unele cazuri de utilizare ale traversării post-comandă sunt:
- Acesta este folosit pentru ștergerea arborilor.
- De asemenea, este util să obțineți expresia postfix dintr-un arbore de expresii.
Articole similare:
- Tipuri de traversări ale arborilor
- Parcurs iterativ post-comanda (folosind două stive)
- Parcurs iterativ post-comanda (folosind o stivă)
- Postorder a arborelui binar fără recursivitate și fără stivă
- Găsiți traversarea postcomandă a BST din traversarea precomandă
- Morris traversare pentru Comandă prin corespondență
- Imprimați parcurgerea postcomandă din precomandă și traversarea în ordine