Cómo crear un árbol binario en C

Escrito por ehow contributor | Traducido por beatriz sánchez
  • Comparte
  • Twittea
  • Comparte
  • Pin
  • E-mail
Cómo crear un árbol binario en C
(laptop image by liorp200 from Fotolia.com)

Cómo crear un árbol binario en C. Los árboles binarios en C son una buena forma de organizar dinámicamente los datos para una búsqueda sencilla. Sin embargo, su mantenimiento requiere mucho trabajo.

Nivel de dificultad:
Difícil

Otras personas están leyendo

Instrucciones

    Crear el árbol binario

  1. 1

    Estructura tu árbol binario. Cada árbol binario necesitará una estructura, aunque sólo tenga una variable. Elige un nombre, y después usa typedef para crearlo: typedef struct student_data STUDENT_DATA;

  2. 2

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

  3. 3

    Asigna una puntero hacia esta estructura de datos, inicializándolo con NULL, para que sea la raíz del árbol: STUDENT_DATA *students = NULL;

    Añadir a un árbol binario

  1. 1

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

  2. 2

    Usa malloc() para crear un nuevo elemento, comprobando siempre si ocurre algún error: if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

  3. 3

    Rellena el resto de campos del nuevo elemento. Asigna sus campos izquierdo y derecho a NULL: new_student->student_ID = newID;new_student->student_size = newsize;new_student->left = NULL;new_student->right = NULL;

  4. 4

    Piensa en la variable raíz. Si la variable raíz es NULL, éste es el primer elemento que será añadido al árbol, así que asigna la variable raíz para que apunte a él, y habrás terminado: if (!students) { students = new_student; return; }

  5. 5

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

  6. 6

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

  7. 7

    Trata con los valores no iguales. Si el nuevo valor es menor que el valor actual, el nuevo elemento va al izquierda. Añádelo inmediatamente si no hay nada en la izquierda. De lo contrario, cruza a la izquierda e itera: if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = newstudent; return 1; } cur_student = cur_student->left;

  8. 8

    Haz lo mismo en el lado derecho, en otro caso: } else { if (cur_student->right == NULL) { cur_student->right = newstudent; return 1; } cur_student = cur_student->right; }}

    Buscar en el árbol binario

  1. 1

    Crea una variable temporal que apunte a la estructura de datos: STUDENT_DATA *cur_student;

  2. 2

    Asigna tu variable temporal a la variable raíz: cur_student = students_head;

  3. 3

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

  4. 4

    Ve a la rama de la izquierda o la derecha e itera, si no lo encuentras: if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; }

  5. 5

    Comprueba si el bucle termina. Si lo hace, significa que no has encontrado el elemento: }return 0;

    Borrar

  1. 1

    Cancela la asignación de tu árbol binario cuando el programa termine, ya que no todos los sistemas operativos harán esto automáticamente. Lo mejor es usar una función recursiva: void deallocate_binary_tree(STUDENT_DATA *tree) {

  2. 2

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

  3. 3

    Cancela la asignación de los subárboles izquierdo y derecho recursivamente: deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

  4. 4

    Cancela la asignación del elemento y habrás terminado: free(tree);}

Consejos y advertencias

  • También puedes buscar y añadir en árboles binarios usando la recursión. Esto será mucho más fácil de escribir y de mantener, pero un poco más difícil de entender, hasta que te acostumbres.
  • Es habitual crear un árbol binario que contenga sólo punteros en una segunda estructura de datos de C, normalmente un vector o lista anidada, donde los datos reales están almacenados. Cada árbol binario es un índice para buscar rápidamente un único campo en una lista de datos.
  • El borrado de un árbol binario es un algoritmo muy complicado en C, pero en muchos usos de los árboles binarios, los elementos nunca se borran.

No dejes de ver

Filtrar por:
  • Mostrar todos
  • Artículos
  • Galerías de fotos
  • Videos
Ordenar:
  • Más relevante
  • Más popular
  • Más reciente

No se encuentran artículos disponibles

No se encuentran slideshows disponibles

No se encuentran videos disponibles