Árboles y grafos en C

Los árboles y los grafos son estructuras de datos no lineales que se utilizan para representar datos jerárquicos y de redes.

En esta lección, aprenderá:

• Cómo se estructuran los árboles y los grafos.
• Cómo implementar un árbol binario en C.
• Cómo representar grafos mediante listas y matrices de adyacencia.

¿Qué es un árbol?

Un árbol es una estructura de datos jerárquica formada por nodos.

Términos clave:

• Raíz - El nodo superior.
• Padre e hijo - Nodos conectados directamente.
• Hoja - Un nodo sin hijos.

Ejemplo: nodo de un árbol binario

En C, un nodo de un árbol binario se define mediante una struct con punteros a los hijos izquierdo y derecho.

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

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

struct Node* createNode(int data) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

int main() {
    struct Node *root = createNode(10);
    return 0;
}

Recorrido de un árbol binario

Métodos de recorrido:

• Inorden (LNR) - Izquierda, nodo, derecha.
• Preorden (NLR) - Nodo, izquierda, derecha.
• Postorden (LRN) - Izquierda, derecha, nodo.

Ejemplo: recorrido inorden

Este programa realiza un recorrido inorden de un árbol binario.

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

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

void inorder(struct Node *root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    struct Node *root = malloc(sizeof(struct Node));
    root->data = 10;
    root->left = NULL;
    root->right = NULL;
    inorder(root);
    return 0;
}

¿Qué es un grafo?

Un grafo es un conjunto de nodos (vértices) conectados mediante aristas.

Los grafos pueden ser:

• Dirigidos - Las aristas tienen dirección.
• No dirigidos - Las aristas no tienen dirección.

Representación de grafos

Los grafos se pueden representar mediante:

• Matriz de adyacencia - Un arreglo bidimensional que representa las conexiones.
• Lista de adyacencia - Una lista en la que cada nodo apunta a sus vecinos.

Recorrido de grafos

Métodos de recorrido habituales:

• Búsqueda en anchura (BFS) - Visita todos los vecinos antes de avanzar a un nivel más profundo.
• Búsqueda en profundidad (DFS) - Explora hasta donde sea posible antes de retroceder.

Resumen

En esta lección, ha aprendido:

• Cómo se estructuran los árboles y los grafos.
• Cómo realizar recorridos de árboles.
• Cómo se representan y recorren los grafos.

¡Con esto concluye la sección Estructuras de datos en C!