Comment créer un arbre binaire en C

Comment créer un arbre binaire en C. Les arbres binaires en C sont un bon moyen d'organiser dynamiquement les données pour faciliter la recherche. Cependant, leur entretien nécessite beaucoup de travail.

Créer l'arborescence binaire

Étape 1

Structurez votre arbre binaire. Chaque arbre binaire aura besoin d'une structure, même s'il n'a qu'une seule variable. Choisissez un nom, puis utilisez typedef pour le créer :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 étudiant_grade ; STUDENT_DATA gauche, à droite ;} ;

Étape 3

Allouez un pointeur à cette structure de données, en l'initialisant à NULL, pour être la tête de l'arbre :STUDENT_DATA *students =NULL;

Ajouter à l'arbre binaire

Étape 1

Allouez deux pointeurs temporaires à la structure de données :STUDENT_DATA new_student, cur_student ;

Étape 2

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

Étape 3

Remplissez les champs du nouvel élément. Définissez ses champs gauche et droit sur NULL :new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL ;

Étape 4

Considérez la variable de tête. Si la variable principale est NULL, c'est le premier élément ajouté à l'arborescence, donc définissez la variable principale pour qu'elle pointe vers elle, et vous avez terminé :if (!students) { Students =new_student; revenir; }

Étape 5

Commencez en haut de l'arborescence :cur_student =Students;while (cur_student) {

Étape 6

Gère l'entrée en double si la nouvelle valeur et la valeur actuelle sont égales :if (newID ==cur_student->student_ID) { abort(); }

Étape 7

Traiter les valeurs inégales. Si la nouvelle valeur est inférieure à la valeur actuelle, le nouvel élément va à gauche. Ajoutez-le immédiatement s'il n'y a rien à gauche. Sinon, parcourez vers la gauche et bouclez :if (newID student_ID) { if (cur_student->left ==NULL) { cur_student->left =newstudent ; retour 1 ; } cur_student =cur_student->gauche ;

Étape 8

Faites la même chose à droite, sinon :} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; retour 1 ; } cur_student =cur_student->right ; }}

Rechercher dans l'arborescence binaire

Étape 1

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

Étape 2

Définissez votre variable temporaire sur la variable principale :cur_student =Students_head ;

Étape 3

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

Étape 4

Branchez à gauche ou à droite, et bouclez, s'il n'est pas trouvé :if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left ; }

Étape 5

Voir si la boucle se termine. Si c'est le cas, cela signifie que vous n'avez jamais trouvé l'élément :}return 0 ;

Nettoyer

Étape 1

Libérez l'arborescence binaire lorsque votre programme se termine, car tous les systèmes d'exploitation ne le géreront pas automatiquement. Il est préférable d'utiliser une fonction récursive :void deallocate_binary_tree(STUDENT_DATA *tree) {

Étape 2

Observez :S'il n'y a pas d'arbre, il n'y a rien à faire :if (!tree) return;

Étape 3

Libérez les sous-arborescences gauche et droite de manière récursive :deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);

Étape 4

Libérez l'élément et vous avez terminé :free(tree);}

Astuce

La recherche et l'ajout d'arbres binaires peuvent également être effectués à l'aide de la récursivité. Ce sera beaucoup plus facile à écrire et à maintenir, mais un peu plus difficile à comprendre, jusqu'à ce que vous vous y habituiez. Il est courant de créer un arbre binaire qui ne contient que des pointeurs vers une seconde structure de données C, souvent un tableau ou une liste chaînée, où résident les données réelles. Chaque arbre binaire est un index pour rechercher rapidement un seul champ des données de la liste.

Avertissement

La suppression d'un arbre binaire est un algorithme très compliqué en C, mais dans de nombreuses utilisations des arbres binaires, les éléments ne sont jamais supprimés.