Binaire bomen in C zijn een goede manier om dynamisch het ordenen van gegevens voor het gemakkelijke zoeken. Ze vereisen echter een heleboel werk te handhaven.
De binaire boom maken
Structuur uw binaire boom. Elke binaire boom moet een structuur, zelfs als er slechts één variabele. Kies een naam en gebruik vervolgens typedef te maken:
typedef struct student_data STUDENT_DATA;
Definiëren de structuur. Omvatten twee pointers naar dezelfde structuur:
struct student_data { int student_ID; int student_grade; STUDENT_DATA left, right;};Het toewijzen van een pointer naar deze gegevensstructuur, initialiseren op NULL, hoofd van de boom:
STUDENT_DATA *students = NULL;
Toevoegen aan de binaire boom
Twee tijdelijke verwijzingen naar de gegevensstructuur toewijzen:
STUDENT_DATA new_student, cur_student;
Malloc () gebruiken om een nieuw element, altijd controleren op een fout te maken:
if ((new_student = malloc(sizeof(STUDENT_DATA))) == NULL) { abort(); }Het nieuwe element velden worden gevuld. De links en de juiste velden instellen op NULL:
new_student->student_ID = newID;new_student->student_size = newsize;new_student->left = NULL;new_student->right = NULL;
Overwegen de hoofd variabele. Als de hoofd variabele NULL is, dit is het eerste element toegevoegd aan de boom, ingesteld dus de hoofd variabele daarnaar verwijzen, en je bent klaar:
if (!students) { students = new_student; return; }Beginnen bij de top van de boom:
cur_student = students;while (cur_student) {De dubbele post verwerken als de nieuwe waarde en de huidige waarde gelijk zijn:
if (newID == cur_student->student_ID) { abort(); }Omgaan met ongelijke waarden. Als de nieuwe waarde lager dan de huidige waarde is, gaat het nieuwe element aan de linkerkant. Voeg het meteen als er niets aan de linkerkant. Anders, traverse links en loop:
if (newID < cur_student->student_ID) { if (cur_student->left == NULL) { cur_student->left = newstudent; return 1; } cur_student = cur_student->left;Het zelfde ding aan de rechterkant, anders doen:
} else { if (cur_student->right == NULL) { cur_student->right = newstudent; return 1; } cur_student = cur_student->right; }}
De binaire boom zoeken
Maak een tijdelijke variabele die verwijst naar de gegevensstructuur:
STUDENT_DATA *cur_student;
Uw tijdelijke variabele instellen op de hoofd variabele:
cur_student = students_head;
Doorlopen van de elementen, controleren op de gewenste waarde:
while (cur_student) { if (cur_student->student_ID == 15) { return cur_student->student_grade; }Branch links of rechts, en loop, als het niet wordt gevonden:
if (cur_student->student_ID < 15) { cur_student = cur_student->right; } else { cur_student = cur_student->left; }Zie als de lus eindigt. Als dat zo is, betekent dit dat u nooit het item gevonden:
}return 0;
Schoon te maken
Deallocate de binaire boom wanneer uw programma wordt beëindigd, aangezien niet alle besturingssystemen dit automatisch behandelen zal. Dit is het beste gedaan met behulp van een recursieve functie:
void deallocate_binary_tree(STUDENT_DATA *tree) {In acht nemen: Als er geen enigen boom, er is niets te doen:
if (!tree) return;
De linker en rechter substructuren recursief deallocate:
deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);
Het nummer van het element, en je bent klaar:
free(tree);}
- Zoeken en toevoegen aan binaire bomen kan ook worden gedaan met behulp van recursie. Dit is veel makkelijker om te schrijven en te onderhouden, maar een beetje moeilijker te begrijpen, totdat u aan het went.
- Het is gebruikelijk om het maken van een binaire boom die alleen verwijzingen naar een tweede C-gegevensstructuur, vaak een matrix of een gelinkte lijst bevat, waarin de feitelijke gegevens zich bevindt. Elke binaire boom is een index van snel zoeken een enkel veld van de gegevens in de lijst.
- Verwijderen van een binaire boom is een zeer ingewikkeld algoritme in C, maar in vele toepassingen van binaire bomen, elementen worden nooit verwijderd.
