ESTRUCTURA DE DATOS: ÁRBOLES BINARIOS EN C++

A lo largo de este artículo se analizará la estructura básica de un árbol binario, los principales métodos para recorrerlo y ejemplos prácticos de su aplicación.

Definición y Estructura del Árbol Binario

Un árbol binario es una colección de nodos en la que cada nodo tiene un valor y hasta dos hijos: izquierdo y derecho. La raíz es el nodo superior, desde donde parte toda la estructura. Los nodos sin hijos se denominan hojas.

struct Node {
    int data;
    Node* left;
    Node* right;
};

A partir de esta estructura, es posible construir árboles binarios de manera dinámica utilizando memoria dinámica con punteros en C++.

Inserción de Nodos

Para insertar un valor en un árbol binario, normalmente se sigue una regla específica. Si es un árbol binario de búsqueda (BST), los valores menores se insertan a la izquierda y los mayores a la derecha.

Node* insert(Node* root, int value) {
    if (root == nullptr) {
        Node* newNode = new Node { value, nullptr, nullptr };

        return newNode;
    }

    if (value < root->data)
        root->left = insert(root->left, value);
    else
        root->right = insert(root->right, value);

    return root;
}

Este código crea un árbol binario de búsqueda que mantiene el orden de los datos, lo cual mejora la eficiencia de búsqueda y recorrido.

Tipos de Recorrido en Árboles Binarios

Los recorridos en árboles binarios son fundamentales para procesar la información almacenada. Se clasifican principalmente en tres:

Preorden

Visita primero la raíz, luego el subárbol izquierdo y luego el derecho.

void preorder(Node* root) {
    if (root != nullptr) {
        std::cout << root->data << " ";

        preorder(root->left);
        preorder(root->right);
    }
}

Inorden

Primero recorre el subárbol izquierdo, luego la raíz y finalmente el derecho. Ideal para obtener elementos en orden ascendente en un BST.

void inorder(Node* root) {
    if (root != nullptr) {
        inorder(root->left);

        std::cout << root->data << " ";

        inorder(root->right);
    }
}

Postorden

Recorre primero los subárboles y al final la raíz. Útil cuando se requiere liberar memoria o realizar tareas de destrucción.

void postorder(Node* root) {
    if (root != nullptr) {
        postorder(root->left);
        postorder(root->right);

        std::cout << root->data << " ";
    }
}

Aplicación práctica

Supongamos que se desea almacenar las edades de un grupo de personas para luego consultarlas en orden. Al insertarlas en un árbol binario de búsqueda y aplicar un recorrido inorden, se obtendrán en forma ascendente:

// Edades: 25, 30, 20, 35, 10
Node* root = nullptr;

root = insert(root, 25);
root = insert(root, 30);
root = insert(root, 20);
root = insert(root, 35);
root = insert(root, 10);

inorder(root); // Salida esperada: 10 20 25 30 35

Esta estructura es útil para construir sistemas de gestión de usuarios, clasificación de datos, árboles de expresión matemática, etc.

Ventajas y desventajas

Árbol Binario:

• Permite organizar datos de forma jerárquica y ordenada.
• Búsqueda, inserción y eliminación pueden ser eficientes (O(log n)) si el árbol está balanceado.
• El rendimiento se degrada a O(n) si el árbol está desbalanceado (como una lista enlazada).

Consideraciones de Implementación

• Es recomendable implementar funciones recursivas para recorrer el árbol, por claridad y legibilidad.
• En árboles de búsqueda, se debe evitar insertar valores duplicados o manejar casos especiales explícitamente.
• En aplicaciones reales, es aconsejable usar árboles balanceados como AVL o Red-Black para garantizar eficiencia.

CONCLUSIÓN

Los árboles binarios son estructuras poderosas para resolver problemas de búsqueda, jerarquización y recorrido de datos. En C++, su implementación es clara y eficiente usando punteros y recursión. Comprender sus tipos de recorrido, ventajas y consideraciones prácticas permite al programador diseñar soluciones estructuradas y óptimas.