6. Árboles

a. Definición

Un árbol es una estructura de datos jerárquica compuesta por nodos. Cada nodo puede tener cero o más nodos hijos, y no existen ciclos. El nodo superior se llama raíz, y los nodos sin hijos se llaman hojas.

Terminología:

Raíz (Root): Nodo principal del árbol.
Nodo Padre (Parent): Nodo que tiene uno o más hijos.
Nodo Hijo (Child): Nodo que es descendiente de otro nodo.
Hoja (Leaf): Nodo sin hijos.
Nivel: Distancia desde la raíz (raíz está en nivel 0).

b. Representación en Memoria de Árboles

Los árboles pueden ser representados en memoria mediante nodos que contienen referencias a sus hijos. Una representación común es utilizando arreglos o listas enlazadas.

Ejemplo de Representación con Punteros:

Cada nodo contiene un dato y punteros a sus hijos.

c. Árboles Generales

Un árbol general es un árbol donde cada nodo puede tener cualquier número de hijos. No está restringido a una cantidad específica de hijos por nodo.

Representación de Árbol General en C:

#include <stdio.h>
#include <stdlib.h>

// Definición del nodo del árbol
typedef struct Nodo {
    char dato;
    struct Nodo **hijos;
    int numHijos;
} Nodo;

// Crear un nuevo nodo
Nodo* crearNodo(char valor, int numHijos) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    nuevo->dato = valor;
    nuevo->numHijos = numHijos;
    if (numHijos > 0) {
        nuevo->hijos = (Nodo**)malloc(numHijos * sizeof(Nodo*));
        for (int i = 0; i < numHijos; i++) {
            nuevo->hijos[i] = NULL;
        }
    } else {
        nuevo->hijos = NULL;
    }
    return nuevo;
}

// Ejemplo de uso
int main() {
    Nodo *raiz = crearNodo('A', 2);
    raiz->hijos[0] = crearNodo('B', 2);
    raiz->hijos[1] = crearNodo('C', 0);
    
    raiz->hijos[0]->hijos[0] = crearNodo('D', 0);
    raiz->hijos[0]->hijos[1] = crearNodo('E', 0);
    
    return 0;
}

d. Árboles Binarios

Un árbol binario es un tipo específico de árbol donde cada nodo tiene como máximo dos hijos, denominados hijo izquierdo y hijo derecho.

Características de un Árbol Binario:

Máximo dos hijos por nodo.
Subárbol izquierdo y subárbol derecho.
Aplicaciones comunes: Expresiones aritméticas, estructuras de búsqueda, etc.

e. Inserción de Elementos en Árbol Binario

Definición del Nodo del Árbol Binario:

typedef struct Nodo {
    int dato;
    struct Nodo *izquierdo;
    struct Nodo *derecho;
} Nodo;

Función para Crear un Nuevo Nodo:

Nodo* crearNodo(int valor) {
    Nodo *nuevo = (Nodo*)malloc(sizeof(Nodo));
    nuevo->dato = valor;
    nuevo->izquierdo = NULL;
    nuevo->derecho = NULL;
    return nuevo;
}

Inserción en un Árbol Binario de Búsqueda (BST):

En un Árbol Binario de Búsqueda (BST), para cada nodo, los valores de los nodos en el subárbol izquierdo son menores y en el derecho son mayores.

Nodo* insertarBST(Nodo *raiz, int valor) {
    if (raiz == NULL) {
        return crearNodo(valor);
    }
    if (valor < raiz->dato) {
        raiz->izquierdo = insertarBST(raiz->izquierdo, valor);
    } else if (valor > raiz->dato) {
        raiz->derecho = insertarBST(raiz->derecho, valor);
    }
    // Si el valor ya existe, no se inserta (evita duplicados)
    return raiz;
}

Ejemplo de Uso:

int main() {
    Nodo *raiz = NULL;
    raiz = insertarBST(raiz, 50);
    raiz = insertarBST(raiz, 30);
    raiz = insertarBST(raiz, 70);
    raiz = insertarBST(raiz, 20);
    raiz = insertarBST(raiz, 40);
    raiz = insertarBST(raiz, 60);
    raiz = insertarBST(raiz, 80);
    
    // Aquí podrías implementar funciones para recorrer el árbol, etc.
    
    return 0;
}

f. Recorridos de un Árbol Binario

Los recorridos son formas de visitar todos los nodos de un árbol. Los principales tipos de recorridos en árboles binarios son preorden, en orden y postorden.

1. Recorrido Preorden (Preorder Traversal):

Orden de Visita: Raíz, Subárbol Izquierdo, Subárbol Derecho.

void recorridoPreorden(Nodo *raiz) {
    if (raiz != NULL) {
        printf("%d ", raiz->dato);
        recorridoPreorden(raiz->izquierdo);
        recorridoPreorden(raiz->derecho);
    }
}

2. Recorrido en Orden (Inorder Traversal):

Orden de Visita: Subárbol Izquierdo, Raíz, Subárbol Derecho.

void recorridoEnOrden(Nodo *raiz) {
    if (raiz != NULL) {
        recorridoEnOrden(raiz->izquierdo);
        printf("%d ", raiz->dato);
        recorridoEnOrden(raiz->derecho);
    }
}

3. Recorrido Postorden (Postorder Traversal):

Orden de Visita: Subárbol Izquierdo, Subárbol Derecho, Raíz.

void recorridoPostorden(Nodo *raiz) {
    if (raiz != NULL) {
        recorridoPostorden(raiz->izquierdo);
        recorridoPostorden(raiz->derecho);
        printf("%d ", raiz->dato);
    }
}

Ejemplo de Uso de Recorridos:

int main() {
    Nodo *raiz = NULL;
    raiz = insertarBST(raiz, 50);
    raiz = insertarBST(raiz, 30);
    raiz = insertarBST(raiz, 70);
    raiz = insertarBST(raiz, 20);
    raiz = insertarBST(raiz, 40);
    raiz = insertarBST(raiz, 60);
    raiz = insertarBST(raiz, 80);
    
    printf("Recorrido Preorden: ");
    recorridoPreorden(raiz); // Imprime: 50 30 20 40 70 60 80
    printf("\n");
    
    printf("Recorrido en Orden: ");
    recorridoEnOrden(raiz); // Imprime: 20 30 40 50 60 70 80
    printf("\n");
    
    printf("Recorrido Postorden: ");
    recorridoPostorden(raiz); // Imprime: 20 40 30 60 80 70 50
    printf("\n");
    
    return 0;
}

g. Resumen de Árboles

Árbol General: Cada nodo puede tener múltiples hijos.
Árbol Binario: Cada nodo tiene como máximo dos hijos (izquierdo y derecho).
Recorridos: Preorden, en orden y postorden para visitar todos los nodos.
Aplicaciones: Expresiones aritméticas, árboles de decisión, estructuras de búsqueda, etc.

Ejercicios

Altura de un Árbol Binario:
- Escribe una función en C que calcule la altura de un árbol binario.
Número de Hojas:
- Implementa una función en C que cuente el número de hojas en un árbol binario.
Verificar si es un BST:
- Escribe una función en C que verifique si un árbol binario dado es un Árbol Binario de Búsqueda (BST).
Recorridos Iterativos:
- Implementa los recorridos preorden, en orden y postorden de un árbol binario utilizando métodos iterativos (sin recursión).