Estructuras de Datos

0x0042 INICIALIZANDO...
0x7ffe-stack
*p = malloc(sizeof(Node))
0x3b2a - heap
ptr -> next = NULL
Unidad 09

Árboles Binarios

Hasta ahora, todas nuestras estructuras (arreglos, listas, pilas) eran lineales: un elemento seguía a otro. Los Árboles son estructuras jerárquicas no lineales, ideales para representar datos organizados por niveles, como sistemas de archivos o estructuras HTML.

Imagen 35. Anatomía y terminología de un Árbol

Imagen 35. Anatomía y terminología de un Árbol

Vocabulario esencial: Raíz (root), Padre, Hijo, Hoja (leaf) y Altura. Entender esto es vital para la recursividad.

9.1 Anatomía de un Árbol
Mirar en YouTube

Un Árbol Binario de Búsqueda (BST) impone una regla estricta: para cualquier nodo, todos los elementos en su subárbol izquierdo son MENORES y todos en el derecho son MAYORES. Esto permite búsquedas binarias ultra rápidas.

main.cpp
struct Nodo {
    int dato;
    struct Nodo* izquierdo;
    struct Nodo* derecho;
};

struct Nodo* nuevoNodo(int dato) {
    struct Nodo* nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nodo->dato = dato;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}
struct Nodo {
    int dato;
    struct Nodo* izquierdo;
    struct Nodo* derecho;
};

struct Nodo* nuevoNodo(int dato) {
    struct Nodo* nodo = (struct Nodo*)malloc(sizeof(struct Nodo));
    nodo->dato = dato;
    nodo->izquierdo = NULL;
    nodo->derecho = NULL;
    return nodo;
}
Imagen 36. Estructura lógica de un ABB

Imagen 36. Estructura lógica de un ABB

La propiedad fundamental: Observa cómo cada decisión de ir a la izquierda o derecha descarta la mitad de los datos restantes.

A diferencia de una lista que se recorre de principio a fin, un árbol tiene múltiples caminos. Los principales recorridos en profundidad (DFS) son: Inorden (Izquierda-Raíz-Derecha), Preorden (Raíz-Izquierda-Derecha) y Postorden (Izquierda-Derecha-Raíz).

Imagen 37. Visualización de rutas de recorrido

Imagen 37. Visualización de rutas de recorrido

Mapa de ruta: El Inorden es especial en los ABB porque visita los números en orden ascendente (de menor a mayor) automáticamente.

main.cpp
void inorden(struct Nodo* raiz) {
    if (raiz != NULL) {
        inorden(raiz->izquierdo);
        printf("%d ", raiz->dato);
        inorden(raiz->derecho);
    }
}
void inorden(struct Nodo* raiz) {
    if (raiz != NULL) {
        inorden(raiz->izquierdo);
        printf("%d ", raiz->dato);
        inorden(raiz->derecho);
    }
}
9.3 Recorridos Visuales
Mirar en YouTube

Eliminar es la operación más difícil. Hay 3 casos: 1) Es una hoja (fácil, se borra). 2) Tiene 1 hijo (el hijo sube y ocupa su lugar). 3) Tiene 2 hijos (difícil, requiere encontrar al sucesor inorden para reemplazarlo).

9.4 Eliminación en Árboles (El caso difícil)
Mirar en YouTube
main.cpp
// Lógica simplificada del Caso 3
else {
    // Nodo con dos hijos: obtener el sucesor (menor del subárbol derecho)
    struct Nodo* temp = minValueNode(raiz->derecho);
    // Copiar el contenido del sucesor
    raiz->dato = temp->dato;
    // Eliminar el sucesor original
    raiz->derecho = deleteNode(raiz->derecho, temp->dato);
}
// Lógica simplificada del Caso 3
else {
    // Nodo con dos hijos: obtener el sucesor (menor del subárbol derecho)
    struct Nodo* temp = minValueNode(raiz->derecho);
    // Copiar el contenido del sucesor
    raiz->dato = temp->dato;
    // Eliminar el sucesor original
    raiz->derecho = deleteNode(raiz->derecho, temp->dato);
}
Volver al nivel