Recorrido del giro postal se define como un tipo de recorrido del árbol que sigue la política Izquierda-Derecha-Raíz de modo que para cada nodo:
- El subárbol izquierdo se recorre primero.
- Luego se atraviesa el subárbol derecho.
- Finalmente, se atraviesa el nodo raíz del subárbol.
Recorrido del giro postal
Algoritmo para el recorrido posterior al orden del árbol binario:
El algoritmo para el recorrido posterior al orden se muestra a continuación:
Giro postal (raíz):
- Siga los pasos 2 a 4 hasta root! = NULL
- Orden posterior (raíz -> izquierda)
- Orden posterior (raíz -> derecha)
- Escribir raíz -> datos
- Finalizar bucle
¿Cómo funciona el recorrido posterior al pedido del árbol binario?
Considere el siguiente árbol:
Ejemplo de árbol binario
Si realizamos un recorrido de postorden en este árbol binario, entonces el recorrido será el siguiente:
Paso 1: El recorrido irá de 1 a su subárbol izquierdo, es decir, 2, luego de 2 a la raíz de su subárbol izquierdo, es decir, 4. Ahora 4 no tiene subárbol, por lo que será visitado.
Se visita el nodo 4
Paso 2: Como el subárbol izquierdo de 2 se visita por completo, ahora atravesará el subárbol derecho de 2, es decir, se moverá a 5. Como no hay ningún subárbol de 5, se visitará.
Se visita el nodo 5
Paso 3: Ahora se visitan los subárboles izquierdo y derecho del nodo 2. Así que ahora visite el nodo 2.
Se visita el nodo 2
java convierte int a cadenaEtapa 4: A medida que se atraviesa el subárbol izquierdo del nodo 1, ahora se moverá a la raíz del subárbol derecho, es decir, 3. El nodo 3 no tiene ningún subárbol izquierdo, por lo que atravesará el subárbol derecho, es decir, 6. El nodo 6 no tiene ningún subárbol y así es visitado.
Se visita el nodo 6
Paso 5: Se atraviesan todos los subárboles del nodo 3. Entonces ahora se visita el nodo 3.
Se visita el nodo 3
Paso 6: Como se atraviesan todos los subárboles del nodo 1, ahora es el momento de visitar el nodo 1 y el recorrido finaliza después de atravesar todo el árbol.
Se visita el árbol completo
Entonces el orden de recorrido de los nodos es 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
Programa para implementar el recorrido posterior al pedido del árbol binario
A continuación se muestra la implementación del código del recorrido posterior al pedido:
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->izquierda);> >// Then recur on right subtree> >printPostorder(node->derecha);> >// Now deal with the node> >cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->izquierda = nuevo Nodo(2); raíz->derecha = nuevo Nodo(3); raíz->izquierda->izquierda = nuevo Nodo(4); raíz->izquierda->derecha = nuevo Nodo(5); raíz->derecha->derecha = nuevo Nodo(6); // Llamada a función 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> |
>
inttostr java
>
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
java compareto
// 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();> |
>
>Producción
Postorder traversal of binary tree is: 4 5 2 6 3 1>
Explicación:
Cómo funciona el recorrido de pedidos por correo
Análisis de complejidad:
Complejidad del tiempo: O(N) donde N es el número total de nodos. Porque atraviesa todos los nodos al menos una vez.
Espacio Auxiliar: O(1) si no se considera ningún espacio de pila de recursividad. De lo contrario, O(h) donde h es la altura del árbol
- En el peor de los casos, h puede ser lo mismo que norte (cuando el árbol es un árbol torcido)
- En el mejor de los casos, h puede ser lo mismo que calma (cuando el árbol es un árbol completo)
Casos de uso de Postorder Traversal:
Algunos casos de uso del recorrido posterior al pedido son:
- Esto se utiliza para eliminar árboles.
- También resulta útil obtener la expresión sufijo de un árbol de expresiones.
Artículos relacionados:
- Tipos de recorridos de árboles
- Recorrido iterativo de postorden (usando dos pilas)
- Recorrido iterativo de postorden (usando una pila)
- Postorder de Árbol Binario sin recursividad y sin pila
- Encuentre el recorrido posterior al pedido de BST desde el recorrido previo al pedido
- Recorrido de Morris para pedidos por correo
- Imprimir recorrido en orden posterior desde orden previo y recorrido en orden