Resumen: implementar la estructura de datos de árbol, árbol binario, binary tree o simplemente tree en C y mostrar operaciones para:
Vamos a usar recursividad para algunas operaciones. Al insertar elementos vamos a compararlos para insertarlos a la izquierda si son menores que el nodo padre, o a la derecha en caso contrario.
Un árbol binario tiene un nodo raíz que tiene dos elementos a los que llamamos izquierda y derecha. Cada elemento es a su vez otro nodo que puede tener izquierda y derecha, infinitamente.
Veamos cómo crear un nodo u hoja. Tenemos el struct
del nodo que es así:
struct Nodo {
int dato;
struct Nodo *izquierda;
struct Nodo *derecha;
};
Tiene un dato, que será el verdadero dato que tiene. Aquí puede haber una cadena, un flotante, etcétera. Además, tiene dos apuntadores a un struct
del mismo tipo que es izquierda y derecha.
Nota: ya he implementado un árbol de tipo string en C, míralo aquí.
Para crear un nodo del árbol binario en C tenemos la siguiente función ayudante:
struct Nodo *nuevoNodo(int dato) {
// Solicitar memoria
size_t tamanioNodo = sizeof(struct Nodo);
struct Nodo *nodo = (struct Nodo *) malloc(tamanioNodo);
// Asignar el dato e iniciar hojas
nodo->dato = dato;
nodo->izquierda = nodo->derecha = NULL;
return nodo;
}
Lo que hace es alojar memoria (con malloc
memory allocation) para el nuevo nodo y regresar el apuntador. Estamos casteando el apuntador a un Nodo
en la línea 4. Después, en la línea 6 y 7 iniciamos los datos del nodo.
Con esto ya tenemos todo lo necesario, es hora de ver las operaciones del árbol binario.
Como lo dije, vamos a insertar los elementos de tal forma que los menores queden a la izquierda de la raíz y los mayores a la derecha.
En caso de que el nodo en donde vayamos a insertar ya esté ocupado, intentamos insertarlo en un nodo hijo. Y si ese hijo está ocupado, entonces vamos a más profundidad. Esto se logra con recursión / recursividad.
void insertar(struct Nodo *nodo, int dato) {
// ¿Izquierda o derecha?
// Si es mayor va a la derecha
if (dato > nodo->dato) {
// Tienes espacio a la derecha?
if (nodo->derecha == NULL) {
nodo->derecha = nuevoNodo(dato);
} else {
// Si la derecha ya está ocupada, recursividad ;)
insertar(nodo->derecha, dato);
}
} else {
// Si no, a la izquierda
if (nodo->izquierda == NULL) {
nodo->izquierda = nuevoNodo(dato);
} else {
// Si la izquierda ya está ocupada, recursividad ;)
insertar(nodo->izquierda, dato);
}
}
}
El primer if
es el que indica si lo insertamos a la izquierda o derecha. Después comprobamos si está disponible (línea 6 y 14, en caso de que sí, alojamos un nuevo nodo.
Si no, invocamos a la función dentro de sí misma (recursión) pero le pasamos el nodo a la derecha o izquierda, eso es en la línea 10 y 18.
Como puedes notar, entre mayor sea el árbol, la inserción será un poco más lenta, pero es un sacrificio que se hace para poder buscar y recorrer en menor tiempo.
Ahora vamos a ver las tres formas de recorrer un árbol, en donde simplemente imprimimos el dato e invocamos a la función con recursividad.
Como puedes ver en el código, la condición de salida es que encontremos un nodo nulo, es decir, que lleguemos al final de una rama.
El único argumento que reciben las funciones de recorrido son el nodo raíz o padre.
En este caso se recorre la raíz, luego la izquierda y finalmente la derecha. Queda así:
void preorden(struct Nodo *nodo) {
if (nodo != NULL) {
printf("%d,", nodo->dato);
preorden(nodo->izquierda);
preorden(nodo->derecha);
}
}
De este modo el primer elemento será la raíz y después todas las izquierdas. Finalmente todas las derechas.
Este recorrido es muy interesante, pues tenemos los datos ordenados de forma ascendente al recorrerlo de esta forma. Esto es debido a que primero recorremos la izquierda, luego la raíz y finalmente la derecha.
Esta es una de las ventajas de los árboles binarios, pues los datos ya están acomodados al insertarlos, así que ya no tenemos que usar un algoritmo de ordenamiento más tarde.
void inorden(struct Nodo *nodo) {
if (nodo != NULL) {
inorden(nodo->izquierda);
printf("%d,", nodo->dato);
inorden(nodo->derecha);
}
}
Veamos el último caso, queda así:
void postorden(struct Nodo *nodo) {
if (nodo != NULL) {
postorden(nodo->izquierda);
postorden(nodo->derecha);
printf("%d,", nodo->dato);
}
}
Como puedes ver, primero visitamos la izquierda, después la derecha, y finalmente la raíz.
Para usarlo solo tienes que crear un nodo que será la raíz y después invocar al método insertar
. No te preocupes, la función se encargará de acomodarlo.
int main(void) {
struct Nodo *raiz = nuevoNodo(28);
insertar(raiz, 11);
insertar(raiz, 96);
insertar(raiz, 21);
insertar(raiz, 6);
insertar(raiz, 97);
insertar(raiz, 1);
insertar(raiz, 30);
insertar(raiz, 10);
insertar(raiz, 2);
printf("\nImprimiendo preorden\n");
preorden(raiz);
printf("\nImprimiendo inorden\n");
inorden(raiz);
printf("\nImprimiendo postorden\n");
postorden(raiz);
}
Como puedes ver, en el código estoy insertando a varios elementos y después imprimiendo.
Todo el código queda así:
/**
* Árboles binarios en C
* Operaciones de:
* Inserción
* Recorrido inorden, postorden y preorden
* Uso de malloc
*
* @author parzibyte
* @see https://parzibyte.me/blog
* */#include <stdio.h>
#include <stdlib.h>
struct Nodo {
int dato;
struct Nodo *izquierda;
struct Nodo *derecha;
};
struct Nodo *nuevoNodo(int dato) {
// Solicitar memoria
size_t tamanioNodo = sizeof(struct Nodo);
struct Nodo *nodo = (struct Nodo *) malloc(tamanioNodo);
// Asignar el dato e iniciar hojas
nodo->dato = dato;
nodo->izquierda = nodo->derecha = NULL;
return nodo;
}
void insertar(struct Nodo *nodo, int dato) {
// ¿Izquierda o derecha?
// Si es mayor va a la derecha
if (dato > nodo->dato) {
// Tienes espacio a la derecha?
if (nodo->derecha == NULL) {
nodo->derecha = nuevoNodo(dato);
} else {
// Si la derecha ya está ocupada, recursividad ;)
insertar(nodo->derecha, dato);
}
} else {
// Si no, a la izquierda
if (nodo->izquierda == NULL) {
nodo->izquierda = nuevoNodo(dato);
} else {
// Si la izquierda ya está ocupada, recursividad ;)
insertar(nodo->izquierda, dato);
}
}
}
void preorden(struct Nodo *nodo) {
if (nodo != NULL) {
printf("%d,", nodo->dato);
preorden(nodo->izquierda);
preorden(nodo->derecha);
}
}
void inorden(struct Nodo *nodo) {
if (nodo != NULL) {
inorden(nodo->izquierda);
printf("%d,", nodo->dato);
inorden(nodo->derecha);
}
}
void postorden(struct Nodo *nodo) {
if (nodo != NULL) {
postorden(nodo->izquierda);
postorden(nodo->derecha);
printf("%d,", nodo->dato);
}
}
int main(void) {
struct Nodo *raiz = nuevoNodo(28);
insertar(raiz, 11);
insertar(raiz, 96);
insertar(raiz, 21);
insertar(raiz, 6);
insertar(raiz, 97);
insertar(raiz, 1);
insertar(raiz, 30);
insertar(raiz, 10);
insertar(raiz, 2);
printf("\nImprimiendo preorden\n");
preorden(raiz);
printf("\nImprimiendo inorden\n");
inorden(raiz);
printf("\nImprimiendo postorden\n");
postorden(raiz);
}
Así funciona un árbol binario en C. Si quieres más sobre estructuras de datos puedes ver una pila dinámica en C.
En el futuro escribiré más sobre C, te invito a seguirme. Mientras tanto puedes ver otros posts de este tema.
Aquí no he tocado el tema de búsqueda en el árbol, pero sí lo he hecho en mi otro post.
Hoy te voy a presentar un creador de credenciales que acabo de programar y que…
Ya te enseñé cómo convertir una aplicación web de Vue 3 en una PWA. Al…
En este artículo voy a documentar la arquitectura que yo utilizo al trabajar con WebAssembly…
En un artículo anterior te enseñé a crear un PWA. Al final, cualquier aplicación que…
Al usar Comlink para trabajar con los workers usando JavaScript me han aparecido algunos errores…
En este artículo te voy a enseñar cómo usar un "top level await" esperando a…
Esta web usa cookies.
Ver comentarios
Gracias por la informacion!
Esta bueno el post, mi pregunta es en que momento se equilibra el árbol y se hacen los balanceos?
esta muy bueno tu ejemplo... pero falta el metodo o funcion para borrar un elemento del arbol