Comment créer un arbre binaire en C

Les arbres binaires en C organisent dynamiquement les données pour une recherche facile, mais demandent beaucoup de maintenance.

Créer l'arbre binaire

Étape 1

Structurez votre arbre binaire. Tout arbre binaire a besoin d'une structure, même avec une seule variable. Choisissez un nom, puis utilisez typedef : typedef struct student_data STUDENT_DATA;

Étape 2

Définissez la structure. Incluez deux pointeurs vers la même structure : struct student_data { int student_ID; int student_grade; STUDENT_DATA *left, *right; };

Étape 3

Allouez un pointeur vers cette structure, initialisé à NULL, pour être la racine : STUDENT_DATA *students = NULL;

Ajouter à l'arbre binaire

Étape 1

Allouez deux pointeurs temporaires : STUDENT_DATA *new_student, *cur_student;

Étape 2

Utilisez malloc() pour créer un nouvel élément, en vérifiant l'erreur : if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }

Étape 3

Remplissez les champs du nouvel élément. Mettez left et right à NULL : new_student->student_ID = newID; new_student->student_grade = newgrade; new_student->left = NULL; new_student->right = NULL;

Étape 4

Considérez la variable racine. Si NULL, c'est le premier élément : if (!students) { students = new_student; return; }

Étape 5

Partez du sommet de l'arbre : cur_student = students; while (cur_student) {

Étape 6

Gérez les doublons si nouvelle valeur = valeur courante : if (newID == cur_student->student_ID) { abort(); }

Étape 7

Traitez les valeurs inégales. Si nouvelle valeur < valeur courante, va à gauche. Ajoutez immédiatement si rien à gauche. Sinon, traversez gauche et bouclez : if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = new_student; return 1; } cur_student = cur_student->left; }

Étape 8

Même chose à droite sinon : } else { if (cur_student->right == NULL) { cur_student->right = new_student; return 1; } cur_student = cur_student->right; } }

Rechercher dans l'arbre binaire

Étape 1

Créez une variable temporaire pointant vers la structure : STUDENT_DATA *cur_student;

Étape 2

Pointez-la vers la racine : cur_student = students_head;

Étape 3

Parcourez les éléments en cherchant la valeur : while (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }

Étape 4

Branchez gauche ou droite et bouclez si non trouvé : if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; }

Étape 5

Si la boucle se termine, l'item n'a pas été trouvé : } return 0;

Nettoyage

Étape 1

Libérez l'arbre binaire à la fin du programme, tous les OS ne le font pas automatiquement. Utilisez une fonction récursive : void deallocate_binary_tree(STUDENT_DATA *tree) {

Étape 2

Si pas d'arbre, rien à faire : if (!tree) return;

Étape 3

Libérez les sous-arbres gauche et droite récursivement : deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

Étape 4

Libérez l'élément : free(tree); }

Astuce

La recherche et l'ajout peuvent aussi se faire par récursion. Plus facile à écrire/maintenir, mais plus dur à comprendre au début. Courant de créer un arbre binaire ne contenant que des pointeurs vers une seconde structure de données C (tableau ou liste chainée) où résident les vraies données. Chaque arbre est un index pour rechercher rapidement un champ unique des données de la liste.

Avertissement

Supprimer d'un arbre binaire est un algorithme très complexe en C, mais dans beaucoup d'utilisations, les éléments ne sont jamais supprimés.