logo

TechCodeview

Técnicas de recorrido de árbol: tutoriales de algoritmos y estructura de datos

Técnicas de recorrido de árboles Incluye varias formas de visitar todos los nodos del árbol. A diferencia de las estructuras de datos lineales (matriz, lista vinculada, colas, pilas, etc.) que solo tienen una forma lógica de atravesarlas, los árboles se pueden atravesar de diferentes maneras. En este artículo, analizaremos todas las técnicas de recorrido de árboles junto con sus usos.

Tabla de contenidos



Significado del recorrido del árbol:

Recorrido del árbol se refiere al proceso de visitar o acceder a cada nodo del árbol exactamente una vez en un orden determinado. Los algoritmos de recorrido de árbol nos ayudan a visitar y procesar todos los nodos del árbol. Dado que el árbol no es una estructura de datos lineal, hay varios nodos que podemos visitar después de visitar un determinado nodo. Existen múltiples técnicas de recorrido de árboles que deciden el orden en el que se visitarán los nodos del árbol.

Técnicas de recorrido de árboles:

Una estructura de datos de árbol se puede recorrer de las siguientes maneras:

  • Primera búsqueda en profundidad o DFS
    • Recorrido en orden
    • Recorrido de pedidos anticipados
    • Recorrido de giro postal
  • Recorrido de orden de nivel o búsqueda de amplitud primero o BFS

Recorrido en orden :

El recorrido en orden visita el nodo en el orden: Izquierda -> Raíz -> Derecha


Algoritmo para recorrido en orden:

En orden (árbol)

  • Atraviese el subárbol izquierdo, es decir, llame a Inorder(left->subtree)
  • Visita la raíz.
  • Atraviese el subárbol derecho, es decir, llame a Inorder(right->subtree)

Usos del recorrido en orden:

  • En el caso de los árboles de búsqueda binaria (BST), el recorrido en orden proporciona nodos en orden no decreciente.
  • Para obtener los nodos de BST en orden no creciente, se puede utilizar una variación del recorrido en orden en el que se invierte el recorrido en orden.
  • El recorrido en orden se puede utilizar para evaluar expresiones aritméticas almacenadas en árboles de expresión.

Fragmento de código para recorrido en orden:

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->izquierda);  // Luego imprimimos los datos del nodo cout<< node->datos<< ' ';  // Now recur on right child  printInorder(node->bien); }>
C 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->izquierda);  // Luego imprime los datos del nodo printf('%d ', node->data);  // Ahora recurre en el hijo derecho printInorder(node->right); }>
Java 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Python3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
C# 
// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
JavaScript 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
Producción 
Inorder traversal of binary tree is 4 2 5 1 3>

Complejidad del tiempo: EN)
Espacio Auxiliar: Si no consideramos el tamaño de la pila para llamadas a funciones, entonces O(1) de lo contrario O(h) donde h es la altura del árbol.

Recorrido de pedidos anticipados :

El recorrido del pedido anticipado visita el nodo en el orden: Raíz -> Izquierda -> Derecha

Algoritmo para recorrido de pedidos anticipados:

Reserva (árbol)

  • Visita la raíz.
  • Atraviese el subárbol izquierdo, es decir, llame a Preorder(left->subtree)
  • Recorra el subárbol derecho, es decir, llame a Preorder(right->subtree)

Usos del recorrido de pedidos anticipados:

  • El recorrido de pedido anticipado se utiliza para crear una copia del árbol.
  • El recorrido de preorden también se utiliza para obtener expresiones de prefijo en un árbol de expresiones.

Fragmento de código para recorrido de pedidos anticipados:

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->datos<< ' ';  // Then recur on left subtree  printPreorder(node->izquierda);  // Ahora recurre en el subárbol derecho printPreorder(node->right); }>
C 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->datos);  // Luego recurre en el subárbol izquierdo printPreorder(node->left);  // Ahora recurre en el subárbol derecho printPreorder(node->right); }>
Java 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Python3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
C# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
JavaScript 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
Producción 
Preorder traversal of binary tree is 1 2 4 5 3>

Complejidad del tiempo: EN)
Espacio Auxiliar: Si no consideramos el tamaño de la pila para llamadas a funciones, entonces O(1) de lo contrario O(h) donde h es la altura del árbol.

Recorrido de giro postal :

El recorrido posterior al pedido visita el nodo en el orden: Izquierda -> Derecha -> Raíz

Algoritmo para recorrido posterior al pedido:

Algoritmo Giro postal(árbol)

  • Recorra el subárbol izquierdo, es decir, llame a Postorder(izquierda->subárbol)
  • Recorra el subárbol derecho, es decir, llame a Postorder(derecha->subárbol)
  • Visita la raíz

Usos del recorrido de pedido por correo:

  • El recorrido posterior al pedido se utiliza para eliminar el árbol. Ver la pregunta por la eliminación de un árbol para detalles.
  • El recorrido posterior al orden también es útil para obtener la expresión postfija de un árbol de expresión.
  • El recorrido posterior al pedido puede ayudar en los algoritmos de recolección de basura, particularmente en sistemas donde se utiliza la administración de memoria manual.

Fragmento de código para recorrido de pedidos por correo:

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->izquierda);  // Luego recurre en el subárbol derecho printPostorder(node->right);  // Ahora trata con el nodo cout<< node->datos<< ' '; }>
C 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->izquierda);  // Luego recurre en el subárbol derecho printPostorder(node->right);  // Ahora tratamos con el nodo printf('%d ', node->data); }>
Java 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. 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.key + ' '); }>
Python3 
# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>
C# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. 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.key + ' '); }>
JavaScript 
// Given a binary tree, print its nodes according  // to the 'bottom-up' 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.key + ' '); }>
Producción 
Postorder traversal of binary tree is 4 5 2 3 1>

Recorrido de orden de nivel :

Recorrido de orden de nivel visita todos los nodos presentes en el mismo nivel por completo antes de visitar el siguiente nivel.

Algoritmo para recorrido de orden de nivel:

Orden de nivel (árbol)

  • Crear una cola vacía Q
  • Ponga en cola el nodo raíz del árbol en Q
  • Bucle mientras Q no esté vacío
    • Retire un nodo de la cola de Q y visítelo
    • Poner en cola el hijo izquierdo del nodo fuera de cola si existe
    • Poner en cola al hijo derecho del nodo fuera de cola si existe

Usos del orden de niveles:

  • El recorrido de orden de nivel se utiliza principalmente como búsqueda primero en amplitud para buscar o procesar nodos nivel por nivel.
  • El recorrido de orden de nivel también se utiliza para Serialización y deserialización de árboles .

Fragmento de código para recorrido de orden de nivel:

pruebas de compatibilidad
C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queueq;  // Poner en cola Root e inicializar altura q.push(root);  while (q.empty() == false) { // Imprime el frente de la cola y elimínalo de la cola Nodo* nodo = q.front();  corte<< node->datos<< ' ';  q.pop();  // Enqueue left child  if (node->izquierda != NULL) q.push(nodo->izquierda);  // Poner en cola al hijo derecho if (nodo->derecho! = NULL) q.push(nodo->derecho);  } }>
C 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->datos);  // Poner en cola al hijo izquierdo if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // Poner en cola al hijo derecho if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // Quitar el nodo de la cola y convertirlo en temp_node temp_node = deQueue(queue, &front);  } }>
Java 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queuecola = nueva lista enlazada();  cola.add(raíz);  while (!queue.isEmpty()) { // poll() elimina el encabezado actual.  Nodo tempNode = cola.poll();  System.out.print(tempNode.data + ' ');  // Poner en cola al hijo izquierdo if (tempNode.left! = null) { queue.add(tempNode.left);  } // Poner en cola el hijo derecho if (tempNode.right! = null) { queue.add(tempNode.right);  } } }>
Python3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # Imprimir el frente de la cola y # eliminarlo de la cola print(queue[0].data, end=' ') node = queue.pop(0) # Poner en cola el hijo izquierdo si node.left no es Ninguno: queue.append(node.left) # Poner en cola al hijo derecho si node.right no es Ninguno: queue.append(node.right)>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queuecola = nueva cola();  cola.En cola (raíz);  while (queue.Count != 0) { Nodo tempNode = cola.Dequeue();  Console.Write(tempNode.data + ' ');  // Poner en cola al hijo izquierdo if (tempNode.left! = null) { queue.Enqueue(tempNode.left);  } // Poner en cola el hijo derecho if (tempNode.right! = null) { queue.Enqueue(tempNode.right);  } } }>
javascript 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

Otros recorridos de árboles:

  1. Recorrido de límites
  2. Recorrido diagonal

1. Recorrido de límites :

Recorrido de límites de un árbol incluye:

  • Límite izquierdo (nodos a la izquierda excluyendo nodos hoja)
  • hojas (constan únicamente de los nodos de las hojas)
  • Límite derecho (nodos a la derecha excluyendo nodos hoja)

Algoritmo para atravesar límites:

Recorrido de límites (árbol)

  • Si la raíz no es nula:
    • Imprimir los datos de la raíz
    • PrintLeftBoundary(root->left) // Imprime los nodos del límite izquierdo
    • PrintLeafNodes(root->left) // Imprime los nodos de hoja del subárbol izquierdo
    • PrintLeafNodes(root->right) // Imprime los nodos de hoja del subárbol derecho
    • PrintRightBoundary(root->right) // Imprime los nodos del límite derecho

Usos del cruce de límites:

  • El recorrido de límites ayuda a visualizar la estructura exterior de un árbol binario, proporcionando información sobre su forma y límites.
  • El recorrido de límites proporciona una forma de acceder y modificar estos nodos, lo que permite operaciones como la poda o el reposicionamiento de nodos de límites.

2. Recorrido diagonal

En el Recorrido Diagonal de un Árbol, todos los nodos en una sola diagonal se imprimirán uno por uno.

Algoritmo de recorrido diagonal:

DiagonalTraversal(árbol):

  • Si la raíz no es nula:
    • Crear un mapa vacío
    • DiagonalTraversalUtil(root, 0, M) // Llamada a la función auxiliar con nivel diagonal inicial 0
    • Para cada par clave-valor (nivel diagonal, nodos) en M:
      • Para cada nodo en nodos:
      • Imprimir los datos del nodo

DiagonalTraversalUtil(nodo, diagonalLevel, M):

  • Si el nodo es nulo:
  • Devolver
  • Si diagonalLevel no está presente en M:
    • Crea una nueva lista en M para diagonalLevel
  • Agregue los datos del nodo a la lista en M[diagonalLevel]
  • DiagonalTraversalUtil(node->left, diagonalLevel + 1, M) // Recorre el elemento secundario izquierdo con mayor nivel diagonal
  • DiagonalTraversalUtil(node->right, diagonalLevel, M) // Atraviesa al niño derecho con el mismo nivel diagonal

Usos del recorrido diagonal:

  • El recorrido diagonal ayuda a visualizar la estructura jerárquica de los árboles binarios, particularmente en estructuras de datos basadas en árboles como los árboles de búsqueda binaria (BST) y los árboles de montón.
  • El recorrido diagonal se puede utilizar para calcular sumas de caminos a lo largo de diagonales en un árbol binario.

Preguntas frecuentes (FAQ) sobre técnicas de recorrido de árboles:

1. ¿Qué son las técnicas de recorrido de árboles?

Las técnicas de recorrido de árbol son métodos utilizados para visitar y procesar todos los nodos en una estructura de datos de árbol. Le permiten acceder a cada nodo exactamente una vez de forma sistemática.

2. ¿Cuáles son los tipos comunes de recorrido de árboles?

Los tipos comunes de recorrido de árbol son: recorrido en orden, recorrido en orden previo, recorrido en orden posterior, recorrido en orden de nivel (búsqueda primero en amplitud)

3. ¿Qué es el recorrido en orden?

El recorrido en orden es un método de recorrido en profundidad en el que los nodos se visitan en el orden: subárbol izquierdo, nodo actual, subárbol derecho.

4. ¿Qué es el recorrido de preorden?

El recorrido de preorden es un método de recorrido en profundidad en el que los nodos se visitan en el orden: nodo actual, subárbol izquierdo, subárbol derecho.

5. ¿Qué es el recorrido del giro postal?

El recorrido posterior al orden es un método de recorrido en profundidad en el que los nodos se visitan en el orden: subárbol izquierdo, subárbol derecho, nodo actual.

6. ¿Qué es el recorrido de orden de niveles?

El recorrido de orden de nivel, también conocido como búsqueda en amplitud (BFS), visita los nodos nivel por nivel, comenzando desde la raíz y pasando al siguiente nivel antes de atravesar más profundamente.

7. ¿Cuándo debo utilizar cada técnica transversal?

El recorrido en orden se utiliza a menudo en árboles de búsqueda binarios para obtener nodos en orden.

El recorrido de pedido anticipado es útil para crear una copia del árbol.

El recorrido de postorden se usa comúnmente en árboles de expresión para evaluar expresiones.

El recorrido del orden de niveles es útil para encontrar el camino más corto entre nodos.

8. ¿Cómo implemento algoritmos de recorrido de árboles?

Los algoritmos de recorrido de árbol se pueden implementar de forma recursiva o iterativa, según los requisitos específicos y el lenguaje de programación que se utilice.

9. ¿Se pueden aplicar los algoritmos de recorrido de árboles a otras estructuras similares a árboles?

Sí, los algoritmos de recorrido de árboles se pueden adaptar para atravesar otras estructuras similares a árboles, como montones binarios, árboles n-arios y gráficos representados como árboles.

10. ¿Existen consideraciones de rendimiento al elegir una técnica transversal?

Las consideraciones de rendimiento dependen de factores como el tamaño y la forma del árbol, la memoria disponible y las operaciones específicas que se realizan durante el recorrido. En general, la elección de la técnica transversal puede afectar la eficiencia de ciertas operaciones, por lo que es importante elegir el método más adecuado para su caso de uso específico.

Algunos otros tutoriales importantes:

  • Tutorial de DSA
  • Tutorial de diseño de sistemas
  • Hoja de ruta de desarrollo de software
  • Hoja de ruta para convertirse en Product Manager
  • Aprenda SAP
  • Aprende SEO