Recorrido de árbol binario

1. Recorrido de árbol binario
2. Ilustración de recorrido de árbol binario
3. Algoritmo de recorrido de árbol binario
4. Implementación de recorridos de árboles binarios
5. Complejidad del algoritmo de recorrido de árbol binario

Un árbol binario es una estructura de datos no lineal. Se llama árbol binario porque cada nodo tiene un máximo de dos hijos. Estos niños se llaman niños izquierdos y niños derechos. También se puede interpretar como un gráfico no dirigido en el que el nodo superior se llama raíz. A diferencia de las estructuras de datos lineales que solo se pueden atravesar de una manera, un árbol se puede atravesar de diferentes maneras. Podemos atravesar un árbol explorando a lo largo o ancho. El primer enfoque se denomina recorrido en profundidad primero, y el segundo se denomina recorrido en anchura primero. En este artículo, analizaremos los recorridos en profundidad.

Hay 3 tipos de recorridos en profundidad: en orden, preorden y posorden. Discutiremos cada uno de ellos uno por uno.

Recorrido de árbol binario

Recorrido en orden

En este recorrido, primero visitamos el subárbol izquierdo, luego la raíz y finalmente el subárbol derecho. Cada nodo se parece a un subárbol. Para BST, el recorrido en orden devuelve todos los elementos en orden ascendente

Recorrido de preorden

En este recorrido, primero visitamos la raíz, luego el subárbol izquierdo y finalmente el subárbol derecho. Cada nodo se parece a un subárbol. Normalmente se usa para replicar, es decir, crear una copia del árbol. El recorrido de prefijo también ayuda a generar una expresión de prefijo a partir de un árbol de expresión.

Recorrido de posorden

En este recorrido, primero visitamos el subárbol izquierdo, luego el subárbol derecho y finalmente la raíz. Cada nodo se parece a un subárbol. Se utiliza para eliminar árboles de forma eficaz. También ayuda a generar una expresión de sufijo a partir de un árbol de expresión.

Ilustración de recorrido de árbol binario

Recorrido de orden: (4, 2, 1, 5, 3, 6, 7, 8, 9)

Llamamos cruce en orden en el nodo raíz 3. Recorra recursivamente a la izquierda para llegar al nodo 4, que es el nodo más a la izquierda, e inclúyalo en nuestra salida; como es la raíz y no tiene nodo izquierdo, visitamos su nodo más a la derecha 2 y lo incluimos en nuestro recorrido. De esta manera, recorremos todo el árbol para obtener el orden anterior como salida.

Recorrido de preorden: (3, 1, 4, 2, 5, 7, 6, 9, 8)

Llamamos recorrido de preorden en el nodo raíz 3 y lo incluimos en nuestra salida. Luego, recorremos recursivamente a la izquierda para llegar al siguiente nodo raíz 1 y luego, posteriormente, 4. Dado que 4 no tiene hijo izquierdo, visitamos el nodo derecho 2. Ahora hemos cubierto el subárbol bajo el nodo raíz 4 y seguimos hasta el nodo 1 y vamos hacia su derecha hasta el nodo 5. De esta manera, atravesamos todo el árbol para obtener el orden anterior como salida.

Recorrido postorden: (2, 4, 5, 1, 6, 8, 9, 7, 3)

Llamamos recorrido postorder en el nodo raíz 3. Recorrer recursivamente a la izquierda para llegar al nodo 4. Antes de incluir 4 en nuestro recorrido, tenemos que visitar su nodo derecho 2. Incluimos 2 y luego 4 en nuestra salida y volvemos a 1. 1 tiene su nodo derecho 5 sin visitar, por lo que primero incluimos 5 y luego 1 en la salida. Luego remontamos al nodo raíz 3 y procedemos a atravesar el subárbol derecho. De esta manera, recorremos todo el árbol para obtener el orden anterior como salida.

Algoritmo de recorrido de árbol binario

Recorrido por el orden

Recorrido de preorden

Recorrido de posorden

Implementación de recorridos de árboles binarios

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
  Node(int x) {
    this->key = x;
    this->left = this->right = NULL;
  }
};

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}
void preorder(Node* root) {
  if (root != NULL) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

void postorder(Node* root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  cout << "The preorder traversal of the tree is : ";
  preorder(root);
  cout << endl;
  cout << "The postorder traversal of the tree is : ";
  postorder(root);
  cout << endl;
}

Complejidad del algoritmo de recorrido de árbol binario

Complejidad del tiempo

• Caso promedio

Hay n nodos en un árbol, en todos los 3 tipos de recorridos, tenemos que ir a visitar cada nodo. Dado que iteramos sobre n nodos, aunque en un orden diferente, la complejidad de tiempo para los 3 recorridos es del orden de O(n). La complejidad de tiempo promedio de los casos es O(n).

• Mejor caso

La complejidad de tiempo en el mejor de los casos es O(n). Es lo mismo que la complejidad del tiempo de caso promedio para todos los recorridos 3.

• Peor caso

La complejidad de tiempo en el peor de los casos es O(n). Es lo mismo que la complejidad del tiempo en el peor de los casos para todos los recorridos 3.

Complejidad espacial

La complejidad espacial del algoritmo es O(n) debido al espacio extra requerido por las llamadas recursivas.