Kako ustvariti binarno drevo v C

Kako ustvariti binarno drevo v C. Binarna drevesa v C so dober način za dinamično organiziranje podatkov za enostavno iskanje. Vendar pa je za njihovo vzdrževanje potrebno veliko dela.

Ustvarite binarno drevo

1. korak

Strukturirajte svoje binarno drevo. Vsako binarno drevo potrebuje strukturo, tudi če ima samo eno spremenljivko. Izberite ime, nato pa uporabite typedef, da ga ustvarite:typedef struct student_data STUDENT_DATA;

2. korak

Določite strukturo. Vključite dva kazalca na isto strukturo:struct student_data { int student_ID; int ocena_študenta; STUDENT_DATA levo, desno;};

3. korak

Dodelite kazalec tej podatkovni strukturi in jo inicializirajte na NULL, da bo glava drevesa:STUDENT_DATA *students =NULL;

Dodaj v binarno drevo

1. korak

Podatkovni strukturi dodelite dva začasna kazalca:STUDENT_DATA new_student, cur_student;

2. korak

Uporabite malloc(), da ustvarite nov element, pri čemer vedno preverite napako:if ((new_student =malloc(sizeof(STUDENT_DATA))) ==NULL) { abort(); }

3. korak

Izpolnite polja novega elementa. Njegovo levo in desno polje nastavite na NULL:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;

4. korak

Upoštevajte spremenljivko glave. Če je spremenljivka head enaka NULL, je to prvi element, dodan v drevo, zato nastavite spremenljivko head, da kaže nanjo, in končali ste:if (!students) { students =new_student; vrnitev; }

5. korak

Začnite na vrhu drevesa:cur_student =students;while (cur_student) {

6. korak

Obravnava podvojeni vnos, če sta nova vrednost in trenutna vrednost enaki:if (newID ==cur_student->student_ID) { abort(); }

7. korak

Ukvarjajte se z neenakimi vrednostmi. Če je nova vrednost manjša od trenutne vrednosti, gre nov element na levo. Dodajte ga takoj, če na levi ni ničesar. V nasprotnem primeru se premaknite levo in zankajte:if (newID student_ID) { if (cur_student->left ==NULL) { cur_student->left =newstudent; vrnitev 1; } cur_student =cur_student->left;

8. korak

Naredite isto na desni, drugače:} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; vrnitev 1; } cur_student =cur_student->desno; }}

Iskanje po binarnem drevesu

1. korak

Ustvarite začasno spremenljivko, ki kaže na podatkovno strukturo:STUDENT_DATA *cur_student;

2. korak

Nastavite svojo začasno spremenljivko na spremenljivko head:cur_student =students_head;

3. korak

Pobrskajte po elementih in preverite želeno vrednost:while (cur_student) { if (cur_student->student_ID ==15) { return cur_student->student_grade; }

4. korak

Razvejaj levo ali desno in zanko, če ni najden:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left; }

5. korak

Preverite, ali se zanka konča. Če se, pomeni, da predmeta niste nikoli našli:}return 0;

Čiščenje

1. korak

Sprostite dodelitev binarnega drevesa, ko se vaš program konča, saj vsi operacijski sistemi tega ne bodo obravnavali samodejno. To je najbolje narediti z uporabo rekurzivne funkcije:void deallocate_binary_tree(STUDENT_DATA *tree) {

2. korak

Opazujte:Če ni nobenega drevesa, ni treba storiti ničesar:if (!tree) return;

3. korak

Rekurzivno razporedite levo in desno poddrevo:deallocate_binary_tree(drevo->levo); deallocate_binary_tree(drevo->desno);

4. korak

Sprostite dodelitev elementa in končali ste:free(tree);}

Nasvet

Iskanje in dodajanje v binarna drevesa je mogoče izvesti tudi z uporabo rekurzije. To bo veliko lažje napisati in vzdrževati, a nekoliko težje razumeti, dokler se ne navadite. Običajno je ustvariti binarno drevo, ki vsebuje samo kazalce na drugo podatkovno strukturo C, pogosto matriko ali povezan seznam, kjer se nahajajo dejanski podatki. Vsako binarno drevo je indeks za hitro iskanje po enem polju podatkov seznama.

Opozorilo

Brisanje iz binarnega drevesa je zelo zapleten algoritem v jeziku C, vendar se pri številnih uporabah binarnih dreves elementi nikoli ne izbrišejo.