En este artículo, analizaremos el recorrido posterior al orden en la estructura de datos.
Las estructuras de datos lineales, como pila, matriz, cola, etc., solo tienen una forma de atravesar los datos. Pero en una estructura de datos jerárquica como árbol , hay varias formas de recorrer los datos. Entonces, aquí discutiremos otra forma de recorrer la estructura de datos del árbol, es decir, recorrido de pedido por correo . El recorrido posterior al orden es una de las técnicas de recorrido utilizadas para visitar el nodo en el árbol. Sigue el principio LRN (nodo izquierdo-derecho) . El recorrido de postorden se utiliza para obtener la expresión de postfijo de un árbol.
teclas modificadoras
Los siguientes pasos se utilizan para realizar el recorrido posterior al pedido:
- Recorra el subárbol izquierdo llamando recursivamente a la función de postorden.
- Atraviese el subárbol derecho llamando a la función de postorden de forma recursiva.
- Acceda a la parte de datos del nodo actual.
La técnica transversal de orden posterior sigue el Raíz izquierda derecha política. Aquí, Raíz izquierda derecha significa que primero se atraviesa el subárbol izquierdo del nodo raíz, luego el subárbol derecho y, finalmente, se atraviesa el nodo raíz. Aquí, el propio nombre Postorder sugiere que por fin se atravesaría el nodo raíz del árbol.
Algoritmo
Ahora, veamos el algoritmo de recorrido posterior al orden.
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
Ejemplo de recorrido de pedido por correo
Ahora, veamos un ejemplo de recorrido posterior al orden. Será más fácil comprender el proceso de recorrido posterior al pedido con un ejemplo.
Los nodos de color amarillo aún no han sido visitados. Ahora, atravesaremos los nodos del árbol anterior utilizando el recorrido de postorden.
- Aquí, 40 es el nodo raíz. Primero visitamos el subárbol izquierdo de 40, es decir, 30. El nodo 30 también lo atravesará en orden posterior. 25 es el subárbol izquierdo de 30, por lo que también se recorre en orden posterior. Entonces 15 es el subárbol izquierdo de 25. Pero 15 no tiene subárbol, entonces imprimir 15 y avanzar hacia el subárbol derecho de 25.
- 28 es el subárbol derecho de 25 y no tiene hijos. Entonces, imprimir 28 .
- Ahora, imprimir 25 , y el recorrido posterior al orden para 25 Está terminado.
- A continuación, avance hacia el subárbol derecho de 30. 35 es el subárbol derecho de 30 y no tiene hijos. Entonces, imprimir 35 .
- Después, imprimir 30 , y el recorrido posterior al orden para 30 Está terminado. Entonces, se atraviesa el subárbol izquierdo del árbol binario dado.
- Ahora, avance hacia el subárbol derecho de 40, que es 50, y también lo atravesará en orden posterior. 45 es el subárbol izquierdo de 50 y no tiene hijos. Entonces, imprimir 45 y avanzar hacia el subárbol derecho de 50.
- 60 es el subárbol derecho de 50, que también se atravesará en orden posterior. 55 es el subárbol izquierdo de 60 que no tiene hijos. Entonces, imprimir 55 .
- Ahora, imprimir 70, que es el subárbol derecho de 60.
- Ahora, imprimir 60, y se completa el recorrido posterior a la orden de 60.
- Ahora, imprimir 50, y se completa el recorrido posterior a la orden de 50.
- Por fin, imprimir 40, que es el nodo raíz del árbol binario dado, y se completa el recorrido posterior al orden para el nodo 40.
El resultado final que obtendremos después del recorrido posterior al pedido es:
{15, 28, 25, 35, 30, 45, 55, 70, 60, 50, 40}
Complejidad del recorrido de pedidos por correo
La complejidad temporal del recorrido posterior al orden es En) , donde 'n' es el tamaño del árbol binario.
Considerando que la complejidad espacial del recorrido posterior al orden es O(1) , si no consideramos el tamaño de la pila para las llamadas a funciones. De lo contrario, la complejidad espacial del recorrido posterior al orden es Oh) , donde 'h' es la altura del árbol.
Implementación del recorrido de pedidos por correo
Ahora, veamos la implementación del recorrido de postorden en diferentes lenguajes de programación.
Programa: Escriba un programa para implementar el recorrido posterior al orden en lenguaje C.
#include #include struct node { s struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Postorder traversal of given binary tree is -
'); traversePostorder(root); return 0; } Producción
archivo abierto en java
Programa: Escriba un programa para implementar el recorrido de postorden en C++.
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-16.webp" alt="Postorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> Producción
Después de la ejecución del código anterior, el resultado será:
Programa: Escriba un programa para implementar el recorrido de postorden en Java.
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } Producción
Después de la ejecución del código anterior, el resultado será:
Entonces, eso es todo sobre el artículo. Espero que el artículo le resulte útil e informativo.