Cómo crear un árbol binario en C
Cómo crear un árbol binario en C. Los árboles binarios en C son una buena manera de organizar dinámicamente los datos para facilitar la búsqueda. Sin embargo, requieren mucho trabajo para mantener.
Crea el Árbol Binario
Paso 1
Estructura tu árbol binario. Cada árbol binario necesitará una estructura, incluso si solo tiene una variable. Elija un nombre, luego use typedef para crearlo:typedef struct student_data STUDENT_DATA;
Paso 2
Definir la estructura. Incluya dos punteros a la misma estructura:struct student_data { int student_ID; int estudiante_grado; STUDENT_DATA izquierda, correcto;};
Paso 3
Asigne un puntero a esta estructura de datos, inicializándolo en NULL, para que sea la cabeza del árbol:STUDENT_DATA *students =NULL;
Añadir al árbol binario
Paso 1
Asigne dos punteros temporales a la estructura de datos:STUDENT_DATA new_student, cur_estudiante;
Paso 2
Use malloc() para crear un nuevo elemento, siempre buscando un error:if ((nuevo_estudiante =malloc(tamaño(tamaño(DATOS_ESTUDIANTE))) ==NULL) { abort();
Paso 3
Rellene los campos del nuevo elemento. Establezca sus campos izquierdo y derecho en NULL:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;
Paso 4
Considere la variable cabeza. Si la variable principal es NULL, este es el primer elemento que se agrega al árbol, así que establezca la variable principal para que apunte a él y listo:if (!estudiantes) { estudiantes =nuevo_estudiante; devolver;
Paso 5
Comience en la parte superior del árbol:cur_student =estudiantes;mientras (cur_student) {
Paso 6
Manejar la entrada duplicada si el nuevo valor y el valor actual son iguales:if (newID ==cur_student->student_ID) { abort();
Paso 7
Tratar con valores desiguales. Si el nuevo valor es menor que el valor actual, el nuevo elemento va a la izquierda. Agréguelo inmediatamente si no hay nada a la izquierda. De lo contrario, atraviese a la izquierda y haga un bucle:if (newID
Paso 8
Haga lo mismo a la derecha, de lo contrario:} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; devolver 1; } cur_estudiante =cur_estudiante->derecho; }}
Buscar en el árbol binario
Paso 1
Cree una variable temporal que apunte a la estructura de datos:STUDENT_DATA *cur_student;
Paso 2
Establezca su variable temporal en la variable principal:cur_student =Students_head;
Paso 3
Recorra los elementos, verificando el valor deseado:while (estudiante_cur) { if (estudiante_cur->ID_estudiante ==15) { return estudiante_cur->calificación_estudiante;
Paso 4
Bifurque a la izquierda oa la derecha, y haga un bucle, si no se encuentra:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left;
Paso 5
A ver si termina el bucle. Si es así, significa que nunca encontraste el artículo:}return 0;
Limpiar
Paso 1
Desasigne el árbol binario cuando finalice su programa, ya que no todos los sistemas operativos manejarán esto automáticamente. Esto se hace mejor usando una función recursiva:void deallocate_binary_tree(STUDENT_DATA *tree) {
Paso 2
Observar:Si no hay ningún árbol, no hay nada que hacer:if (!tree) return;
Paso 3
Desasignar los subárboles izquierdo y derecho recursivamente:desalocate_binary_tree(tree->left); desalocate_binary_tree(árbol->derecha);
Paso 4
Desasignar el elemento y listo:free(tree);}
Consejo
La búsqueda y la adición de árboles binarios también se pueden realizar mediante recursividad. Esto será mucho más fácil de escribir y mantener, pero un poco más difícil de entender, hasta que te acostumbres. Es común crear un árbol binario que contenga solo punteros a una segunda estructura de datos C, a menudo una matriz o una lista vinculada, donde residen los datos reales. Cada árbol binario es un índice para buscar rápidamente un solo campo de los datos de la lista.
Advertencia
Eliminar de un árbol binario es un algoritmo muy complicado en C, pero en muchos usos de los árboles binarios, los elementos nunca se eliminan.