Recorridos de árboles (en orden, en orden anticipado y en orden posterior) con ejemplos
¿Qué es el recorrido del árbol?
En la estructura de datos de árbol, atravesar significa visitar nodos de alguna manera específica. Hay nodos2 tipos de recorridos. Generalmente, este tipo de recorrido se basa en árboles binarios. Un árbol binario significa que cada nodo puede tener un máximo de 2 nodos.
Un árbol binario es una estructura de datos bien conocida. También hay un árbol de búsqueda binaria (BST). Este tipo de recorrido se utiliza para diversos fines. El recorrido de orden de nivel se utiliza para calcular la profundidad entre dos nodos. Existe otro tipo de árbol llamado “AVL”, donde es necesario calcular la altura de un nodo. Podemos representar un árbol binario en la matriz, pero para optimizar la memoria, usaremos estructura y puntero para hacer referencia al siguiente nodo.
Tipos de recorrido de árbol
Como discutimos árboles binarios, ahora analizamos los tipos individuales de recorridos. Según los tipos, existen dos tipos de recorrido. Anteriormente mencionamos la necesidad del orden de niveles o el recorrido primero en amplitud. Ahora Recorrido primero en profundidad Al igual que el orden posterior se utiliza para eliminar un nodo (lo analizaremos más adelante), el orden previo se utiliza para copiar un árbol binario y el "inorder" recorrerá el árbol de manera no decreciente.
- Travesía primero en anchura
- Recorrido primero en profundidad
- Recorrido de pre-pedido
- Recorrido posterior al pedido
- Recorrido en orden
Travesía primero en anchura
También se conoce como recorrido por orden de nivel. Consideremos el siguiente árbol para demostrar el recorrido por orden de nivel.
Entonces, comenzaremos desde el nodo raíz "1". Se marcará como nivel 1. Luego, el algoritmo irá a todos los hijos del nodo actual. Visitaremos los nodos 2 y 3 ahora. Serán marcados como nivel 2.
Después de eso, como tenemos 2 nodos en el nivel 2, también visitaremos a sus hijos. Entonces, visitaremos 5,6,8,7 y los marcaremos como nivel 3. Aquí hay una cosa que no se menciona:
Nivel de nodo = nivel del nodo padre + 1
Nivel 1: 1
Nivel 2: 2
Nivel 3: 5 6 8 7
Se utiliza un algoritmo similar para el BFS (Búsqueda primero en amplitud).
Aquí está el pseudocódigo para el recorrido del orden de niveles:
level_order(node) Q → Queue() Q.push(node) while !Q.empty(): current_node = Q.pop() print current_node.value # Checking if the current node have any child or not if current_node.left is not NULL: Q.push(current_node.left) if current_node.right is not NULL: Q.push(current_node.right)
Árbol Bianry transversal en orden
Pongamos el mismo ejemplo que antes. En este tipo de recorrido, primero visitamos el subárbol izquierdo, luego la raíz y luego el subárbol derecho. Para facilitar la memoria, podemos decir que el orden es izquierda-raíz-derecha.
Para todo el árbol, digamos que la raíz es 1. Ahora el algoritmo será el siguiente:
- Visite el subárbol izquierdo del nodo 1.
- El nodo actual es 2 (ya que es el subárbol izquierdo de 1)
- Visite el subárbol izquierdo de 2. El nodo actual será 5 esta vez.
- Pasando al 5, no tiene hijos, por lo que el nodo 5 se marcará como visitado. Volverá al nodo principal; que es 2.
- A medida que se visita el subárbol izquierdo de 2, ahora también se visitará 2.
- El algoritmo Moverá el nodo actual al subárbol derecho del nodo 2, que es el nodo 6. Después de visitar el nodo 6, se moverá a su nodo padre 2.
- A medida que se visita el nodo 2, ahora visitaremos el padre de 2; que es el nodo 1.
- Después de eso, visitaremos el subárbol derecho.
Entonces el recorrido final se verá así:
En orden: 5 → 2 → 6 → 1 → 8 → 3 → 7
Aquí está el pseudocódigo para el recorrido en orden:
InOrder(node): if node is not null: InOrder(node.left) print node.value InOrder(node.right)
Este es el algoritmo recursivo para el recorrido en orden. Para el Árbol de búsqueda binaria (BST), El recorrido en orden proporciona la matriz ordenada de valores.
Recorrido posterior al pedido
En este recorrido, atravesaremos primero el subárbol más a la izquierda y luego el subárbol más a la derecha después de la raíz. Todos los recorridos se realizarán en Post-Orden. Demostremos un ejemplo:
Aquí para raíz = 1,
- Primero iremos al subárbol izquierdo. Entonces la raíz se convertirá en 2.
- Entonces 2 ha abandonado el subárbol, por lo que iremos al nodo 5. Ahora la raíz es 5.
- No tiene subárbol izquierdo ni tampoco subárbol derecho. Entonces, ahora marcaremos el nodo 5 como visitado e iremos a su nodo padre.
- Ahora la raíz es 2 y su subárbol izquierdo está completamente visitado. Ahora pasaremos a su subárbol derecho. Entonces la raíz se convierte en 6.
- Como el nodo 6 no tiene subárbol izquierdo ni derecho, marcaremos el nodo 6 como visitado y lo trasladaremos a su nodo padre 2.
- Ahora, se están visitando los subárboles izquierdo y derecho para el nodo 2. También se marcará como visitado.
- Pasaremos al padre del nodo 2, que es el nodo 1.
- Se visita el subárbol izquierdo para la raíz 1. Ahora, de manera similar, visitaremos el subárbol derecho.
El círculo marcado es el subárbol derecho. Ahora visitaremos el subárbol derecho como visitamos el subárbol izquierdo. Después de eso, visitaremos el nodo. Entonces el recorrido final será:
Orden posterior: 5 → 6 → 2 → 8 → 7 → 3 → 1
Aquí está el pseudocódigo para el recorrido posterior al pedido:
PostOrder(node): if node is not null: PostOrder(node.left) PostOrder(node.right) print node.value
Recorrido de pedidos anticipados
Para el recorrido de preorden, el algoritmo visitará primero el nodo raíz y luego se moverá al subárbol izquierdo y derecho, respectivamente. Para facilitar la comprensión, podemos pensar en visitas transversales de pedidos anticipados como raíz → izquierda-derecha.
Entonces, seleccionemos el nodo 1 como raíz.
- Según el algoritmo, primero se descubrirá la raíz, luego el subárbol izquierdo y luego el derecho.
- Entonces, visitaremos la raíz 1. Luego nos moveremos a su subárbol izquierdo. La raíz se convierte en 2.
- Visitaremos el nodo 2 y nos trasladaremos a su subárbol izquierdo. Entonces, la raíz se convierte en 3.
- Visitamos el nodo 3, luego nos trasladamos a su nodo padre. Ahora se visita el nodo 2 y su subárbol izquierdo. Es hora de visitar el subárbol correcto.
- Nos moveremos al subárbol derecho, la raíz se convierte en 4. Visitaremos 4. Como 4 no tiene un nodo hijo, nos trasladaremos a su padre.
- Ahora la raíz es 2 y se visita junto con su subárbol izquierdo y derecho. Entonces, pasaremos a su nodo principal. Ahora la raíz se convierte en 1.
- De manera similar, visitaremos el subárbol derecho.
Reserva: 1 → 2 → 3 → 4 → 5 → 6 → 7
Aquí está el pseudocódigo para el recorrido posterior al pedido:
PreOrder(node): if node is not null: print node.value PreOrder(node.left) PreOrder(node.right)
Implementación en Python
class Node: def __init__(self, item): self.left = None self.right = None self.val = item # creating a tree data structure def inorder(root): #checking if the root is null or not if root: inorder(root.left) # recursively calling left subtree print(str(root.val) + " ", end = '') inorder(root.right) # recursively calling right subtree def postorder(root): if root: postorder(root.left) postorder(root.right) print(str(root.val) + " ", end = '') def preorder(root): if root: print(str(root.val) + " ", end = '') preorder(root.left) preorder(root.right) def levelOrder(root): queue = list() queue.append(root) while len(queue) & gt; 0: current = queue[0] queue = queue[1: ] print(str(current.val) + " ", end = "") if current.left: queue.append(current.left) if current.right: queue.append(current.right) root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.left = Node(6) root.right.right = Node(7) print("\nLevelOrder traversal:\t", end = " ") levelOrder(root) print("\nInorder traversal:\t", end = " ") inorder(root) print("\nPreorder traversal:\t", end = " ") preorder(root) print("\nPostorder traversal:\t", end = " ") postorder(root)
Salida:
LevelOrder traversal: 1 2 3 4 5 6 7 Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1
Implementación en C
#include <stdio.h> #include <stdlib.h> struct node { int value; struct node* left; struct node* right; }; // Inorder traversal void InOrder(struct node* root) { if (root == NULL) return; InOrder(root->left); printf("%d ", root->value); InOrder(root->right); } // PreOrder traversal void PreOrder(struct node* root) { if (root == NULL) return; printf("%d ", root->value); PreOrder(root->left); PreOrder(root->right); } // PostOrder traversal void PostOrder(struct node* root) { if (root == NULL) return; PostOrder(root->left); PostOrder(root->right); printf("%d ", root->value); } // Create a new Node struct node* createNode(int value) { struct node* newNode = malloc(sizeof(struct node)); newNode->value = value; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { struct node* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7); printf("Inorder traversal:\t"); InOrder(root); printf("\PreOrder traversal:\t"); PreOrder(root); printf("\nPostOrder traversal:\t"); PostOrder(root); }
Producción:
Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1
Implementación de C++ (Usando std:queue para orden de nivel)
#include <stdio.h> #include <stdlib.h> #include<queue> typedef struct node { int value; struct node* left; struct node* right; }node; // Inorder traversal void InOrder(struct node* root) { if (root == NULL) return; InOrder(root->left); printf("%d ", root->value); InOrder(root->right); } // PreOrder traversal void PreOrder(struct node* root) { if (root == NULL) return; printf("%d ", root->value); PreOrder(root->left); PreOrder(root->right); } // PostOrder traversal void PostOrder(struct node* root) { if (root == NULL) return; PostOrder(root->left); PostOrder(root->right); printf("%d ", root->value); } void LevelOrder(struct node* root){ std::queue<struct node*> Q; Q.push(root); while(!Q.empty()){ struct node* current = Q.front(); Q.pop(); printf("%d ",current->value); if(current->left) Q.push(current->left); if(current->right) Q.push(current->right); } } // Create a new Node struct node* createNode(int value) { struct node* newNode = new node(); newNode->value = value; newNode->left = NULL; newNode->right = NULL; return newNode; } int main() { struct node* root = createNode(1); root->left = createNode(2); root->right = createNode(3); root->left->left = createNode(4); root->left->right = createNode(5); root->right->left = createNode(6); root->right->right = createNode(7); printf("Level Order traversal:\t"); LevelOrder(root); printf("\nInorder traversal:\t"); InOrder(root); printf("\nPreOrder traversal:\t"); PreOrder(root); printf("\nPostOrder traversal:\t"); PostOrder(root); }
LevelOrder traversal: 1 2 3 4 5 6 7 Inorder traversal: 4 2 5 1 6 3 7 Preorder traversal: 1 2 4 5 3 6 7 Postorder traversal: 4 5 2 6 7 3 1