Recorrido de árbol (en orden, en orden anticipado, en orden posterior)

¿Qué es el recorrido del árbol?

En la estructura de datos de árbol, el recorrido consiste en visitar los nodos de una manera específica. Existen dos tipos de recorrido. Generalmente, este tipo de recorrido se basa en un árbol binario. Un árbol binario implica que cada nodo puede tener un máximo de dos 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 binario de recorrido 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 moveremos a su subárbol izquierdo. Por lo tanto, la raíz pasa a ser 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 en preorden:

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) >
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 el orden por niveles)

#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

Preguntas Frecuentes