Cómo crear un árbol binario en C

Los árboles binarios en C son una buena forma de organizar datos dinámicamente para búsquedas fáciles. Sin embargo, requieren mucho trabajo para mantenerlos.

Crear el árbol binario

Paso 1

Estructura tu árbol binario. Cada árbol necesitará una estructura, aunque solo tenga una variable. Elige un nombre y usa typedef: typedef struct student_data STUDENT_DATA;

Paso 2

Define la estructura. Incluye dos punteros a la misma estructura: struct student_data { int student_ID; int student_grade; STUDENT_DATA *left, *right; };

Paso 3

Asigna un puntero a esta estructura, inicializándolo a NULL, para ser la cabeza del árbol: STUDENT_DATA *students = NULL;

Agregar al árbol binario

Paso 1

Asigna dos punteros temporales a la estructura: STUDENT_DATA *new_student, *cur_student;

Paso 2

Usa malloc() para crear un nuevo elemento, comprobando siempre errores: if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

Paso 3

Rellena los campos del nuevo elemento. Establece left y right a NULL: new_student->student_ID = newID; new_student->student_size = newsize; new_student->left = NULL; new_student->right = NULL;

Paso 4

Considera la variable cabeza. Si es NULL, es el primer elemento, así que apúntala al nuevo y termina: if (!students) { students = new_student; return; }

Paso 5

Empieza en la cima del árbol: cur_student = students; while (cur_student) {

Paso 6

Maneja entrada duplicada si el nuevo valor y el actual son iguales: if (newID == cur_student->student_ID) { abort(); }

Paso 7

Trata valores desiguales. Si el nuevo valor es menor, va a la izquierda. Agrégalo inmediatamente si no hay nada a la izquierda. Si no, recorre a la izquierda y repite: if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = new_student; return 1; } cur_student = cur_student->left; }

Paso 8

Haz lo mismo a la derecha: } else { if (cur_student->right == NULL) { cur_student->right = new_student; return 1; } cur_student = cur_student->right; } }

Buscar en el árbol binario

Paso 1

Crea una variable temporal apuntando a la estructura: STUDENT_DATA *cur_student;

Paso 2

Establece tu variable temporal a la variable cabeza: cur_student = students_head;

Paso 3

Recorre los elementos buscando el valor deseado: while (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }

Paso 4

Ramifica izquierda o derecha y repite si no se encuentra: if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; } }

Paso 5

Verifica si el bucle termina. Si lo hace, no encontraste el elemento: return 0;

Limpiar

Paso 1

Libera el árbol binario al terminar el programa, ya que no todos los SO lo hacen automáticamente. Mejor con función recursiva: void deallocate_binary_tree(STUDENT_DATA *tree) {

Paso 2

Observa: si no hay árbol, no hay nada que hacer: if (!tree) return;

Paso 3

Libera los subárboles izquierdo y derecho recursivamente: deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

Paso 4

Libera el elemento y listo: free(tree); }

Consejo

Buscar y agregar a árboles binarios también puede hacerse con recursión. Es más fácil de escribir y mantener, pero un poco más difícil de entender al principio. Es común crear un árbol que contenga solo punteros a una segunda estructura de datos en C, a menudo un array o lista enlazada, donde residen los datos reales. Cada árbol es un índice para buscar rápidamente un campo de los datos de la lista.

Advertencia

Eliminar de un árbol binario es un algoritmo muy complicado en C, pero en muchos usos los elementos nunca se eliminan.