Przebieg przekazu pocztowego jest zdefiniowany jako rodzaj przechodzenie przez drzewo który jest zgodny z zasadą Left-Right-Root, tak że dla każdego węzła:
- Najpierw przemierzane jest lewe poddrzewo
- Następnie przechodzi się przez prawe poddrzewo
- Na koniec przechodzi się przez węzeł główny poddrzewa
Przebieg przekazu pocztowego
Algorytm postorderowego przechodzenia drzewa binarnego:
Algorytm przechodzenia postordera przedstawiono w następujący sposób:
Przekaz pocztowy (korzeń):
- Wykonaj kroki od 2 do 4, aż root != NULL
- Postorder (root -> lewy)
- Postorder (root -> prawy)
- Napisz root -> dane
- Zakończ pętlę
Jak działa postorderowe przechodzenie drzewa binarnego?
Rozważmy następujące drzewo:
Przykład drzewa binarnego
Jeśli wykonamy przechodzenie postorder w tym drzewie binarnym, wówczas przechodzenie będzie wyglądać następująco:
Krok 1: Przechodzenie będzie przebiegać od 1 do lewego poddrzewa, tj. 2, następnie od 2 do lewego korzenia poddrzewa, tj. 4. Teraz 4 nie ma poddrzewa, więc zostanie odwiedzone.
Węzeł 4 jest odwiedzany
Krok 2: Gdy lewe poddrzewo liczby 2 zostanie całkowicie odwiedzone, teraz przejdzie przez prawe poddrzewo liczby 2, tj. przejdzie do 5. Ponieważ nie ma poddrzewa liczby 5, zostanie odwiedzone.
Węzeł 5 jest odwiedzany
Krok 3: Teraz odwiedzane są lewe i prawe poddrzewo węzła 2. Więc teraz odwiedź sam węzeł 2.
Węzeł 2 jest odwiedzany
Krok 4: Po przejściu lewego poddrzewa węzła 1 przejdzie on teraz do prawego korzenia poddrzewa, tj. 3. Węzeł 3 nie ma żadnego lewego poddrzewa, więc przejdzie przez prawe poddrzewo, tj. 6. Węzeł 6 nie ma poddrzewa i więc jest odwiedzany.
Węzeł 6 jest odwiedzany
złożony klucz podstawowyKrok 5: Przemierzane są wszystkie poddrzewa węzła 3. Zatem teraz odwiedzany jest węzeł 3.
Węzeł 3 jest odwiedzany
Krok 6: Ponieważ wszystkie poddrzewa węzła 1 zostały przebyte, nadszedł czas na odwiedzenie węzła 1, a następnie przechodzenie kończy się wraz z przechodzeniem przez całe drzewo.
Odwiedzane jest całe drzewo
Zatem kolejność przechodzenia węzłów jest następująca 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Program do implementacji postorderowego przechodzenia drzewa binarnego
Poniżej znajduje się kodowa implementacja przechodzenia po zamówieniu:
C++
metody listy Java
// 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->lewo);> >// Then recur on right subtree> >printPostorder(node->prawda);> >// Now deal with the node> >cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->po lewej = nowy węzeł(2); root->right = nowy węzeł(3); root->lewy->lewy = nowy węzeł(4); root->lewy->prawy = nowy węzeł(5); root->right->right = nowy węzeł(6); // Wywołanie funkcji cout<< 'Postorder traversal of binary tree is:
'; printPostorder(root); return 0; }> |
>
>
Jawa
// 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
Przerzutnik typu T
# 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();> |
>
>Wyjście
Postorder traversal of binary tree is: 4 5 2 6 3 1>
Wyjaśnienie:
Jak działa przechodzenie wysyłkowe
Analiza złożoności:
Złożoność czasowa: O(N) gdzie N jest całkowitą liczbą węzłów. Ponieważ przechodzi przez wszystkie węzły przynajmniej raz.
Przestrzeń pomocnicza: O(1), jeśli nie jest brana pod uwagę przestrzeń stosu rekurencji. W przeciwnym razie O(h) gdzie h jest wysokością drzewa
zawiera w ciągu
- W najgorszym wypadku, H może być taki sam jak N (kiedy drzewo jest drzewem przekrzywionym)
- W najlepszym przypadku, H może być taki sam jak spokój (kiedy drzewo jest drzewem kompletnym)
Przypadki użycia Postorder Traversal:
Oto niektóre przypadki użycia przechodzenia po zamówieniu:
- Służy do usuwania drzewa.
- Przydatne jest również pobranie wyrażenia przyrostkowego z drzewa wyrażeń.
Powiązane artykuły:
- Rodzaje przechodzenia przez drzewa
- Iteracyjne przechodzenie po zamówieniu (przy użyciu dwóch stosów)
- Iteracyjne przechodzenie po zamówieniu (przy użyciu jednego stosu)
- Postorder drzewa binarnego bez rekurencji i bez stosu
- Znajdź przejście BST po zamówieniu w przedsprzedaży
- Przechodzenie Morrisa dla zamówień pocztowych
- Drukuj przechodzenie po zamówieniu z przedsprzedaży i przechodzenia po zamówieniu