Postorderowe przechodzenie drzewa binarnego
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
Krok 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++
// 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
# 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
- 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
