Árboles binarios en C++

INTRODUCCIÓN: Los árboles binarios son una de las estructuras de datos más fundamentales en la programación. Se utilizan en múltiples áreas como bases de datos, algoritmos de búsqueda, sistemas operativos, y más. En este artículo aprenderás:

• Qué es un árbol binario.

• Cómo se representa en C++.

• Cómo hacer recorridos (pre-orden, in-orden y post-orden).

¿Qué es un Árbol Binario? 

Un árbol binario es un conjunto finito de cero o más nodos tales que:

• Existe un nodo denominado raíz del árbol.
• Cada nodo puede tener 0, 1 ó 2 subárboles, conocidos como subárbol izquierdo y subárbol derecho, comúnmente llamados hijo izquierdo e hijo derecho.

Es ampliamente utilizado en algoritmos de búsqueda, inteligencia artificial, compiladores y más.

Ejemplos de árboles binarios

Representación de un Árbol Binario en C++

#include <iostream>
using namespace std;

struct Nodo {
    int dato;
    Nodo* izquierda;
    Nodo* derecha;

    Nodo(int valor) {
        dato = valor;
        izquierda = nullptr;
        derecha = nullptr;
    }
};

Cada nodo almacena un valor entero y dos punteros: uno al hijo izquierdo y otro al derecho.

Recorrido de un Árbol

Se denomina recorrido de un árbol al proceso que permite acceder de una sola vez a cada uno de los nodos del árbol. Cuando un árbol se recorre, el conjunto completo de nodos se examina.

Existen muchos modos para recorrer un árbol binario. Por ejemplo existen seis diferentes recorridos generales en un árbol binario, simétrico dos a dos.

Los algoritmos de recorrido de un árbol binario presentan tres tipos de actividades comunes:

• Visitar el nodo raíz.
• Recorrer el subárbol izquierdo.
• Recorrer el subárbol derecho.

Estas tres acciones repartidas en diferentes órdenes proporcionan los diferentes recorridos del árbol. Los más frecuentes tienen siempre en común recorrer primero el subárbol izquierdo y luego el subárbol derecho. Los algoritmos anteriores se llaman pre-orden, post-orden, in-orden, y su nombre refleja el momento en que se visita el nodo raíz. En el in-orden el raíz está en el medio del recorrido, en el pre-orden el raíz está primero y en el post-orden el raíz está el último.

Recorrido pre-orden:

1. Visitar el raíz.
2. Recorrer el subárbol izquierdo en pre-orden.
3. Recorrer el subárbol derecho en pre-orden.

Recorrido in-orden:

1. Recorrer el subárbol izquierdo en in-orden.
2. Visitar el raíz.
3. Recorrer el subárbol derecho en in-orden.

Recorrido post-orden:

1. Recorrer el subárbol izquierdo en post-orden.
2. Recorrer el subárbol derecho en post-orden.
3. Visitar el raíz.

Obsérvese que todas estas definiciones tienen naturaleza recursiva. (Recursiva: Función o Procedimiento que se llama a sí mismo)

Autor: Zamora Sarayse Royer