Kako stvoriti binarno stablo u C

Kako stvoriti binarno stablo u C-u. Binarno stablo u C-u dobar je način za dinamičko organiziranje podataka za jednostavno pretraživanje. Međutim, njihovo održavanje zahtijeva puno rada.

Stvorite binarno stablo

1. korak

Strukturirajte svoje binarno stablo. Svako binarno stablo će trebati strukturu, čak i ako ima samo jednu varijablu. Odaberite naziv, zatim upotrijebite typedef da ga kreirate:typedef struct student_data STUDENT_DATA;

2. korak

Definirajte strukturu. Uključite dva pokazivača na istu strukturu:struct student_data { int student_ID; int student_grade; STUDENT_DATA lijevo, desno;};

3. korak

Dodijelite pokazivač ovoj strukturi podataka, inicijalizirajući je na NULL, da bude glava stabla:STUDENT_DATA *students =NULL;

Dodaj u binarno stablo

1. korak

Dodijelite dva privremena pokazivača strukturi podataka:STUDENT_DATA novi_student, cur_student;

2. korak

Koristite malloc() za stvaranje novog elementa, uvijek provjeravajući grešku:if ((new_student =malloc(sizeof(STUDENT_DATA))) ==NULL) { abort(); }

3. korak

Popunite polja novog elementa. Postavite lijevo i desno polje na NULL:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;

4. korak

Razmotrite varijablu glave. Ako je varijabla glave NULL, ovo je prvi element dodan stablu, pa postavite varijablu glave da pokazuje na nju i gotovi ste:if (!students) { students =new_student; povratak; }

Korak 5

Započnite na vrhu stabla:cur_student =studenti;while (cur_student) {

Korak 6

Obradite duplikat unosa ako su nova vrijednost i trenutna vrijednost jednake:if (newID ==cur_student->student_ID) { abort(); }

7. korak

Nosite se s nejednakim vrijednostima. Ako je nova vrijednost manja od trenutne vrijednosti, novi element ide lijevo. Dodajte ga odmah ako nema ništa s lijeve strane. U suprotnom, prijeđite lijevo i petljajte:if (newID student_ID) { if (cur_student->left ==NULL) { cur_student->left =newstudent; povratak 1; } cur_student =cur_student->lijevo;

Korak 8

Učinite istu stvar s desne strane, inače:} else { if (cur_student->right ==NULL) { cur_student->right =newstudent; povratak 1; } cur_student =cur_student->desno; }}

Pretražite binarno stablo

1. korak

Napravite privremenu varijablu koja ukazuje na strukturu podataka:STUDENT_DATA *cur_student;

2. korak

Postavite svoju privremenu varijablu na varijablu glave:cur_student =students_head;

3. korak

Prođite kroz elemente, provjeravajući željenu vrijednost:while (cur_student) { if (cur_student->student_ID ==15) { return cur_student->student_grade; }

4. korak

Grananje lijevo ili desno, i petlja, ako nije pronađeno:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left; }

Korak 5

Pogledajte završava li petlja. Ako se dogodi, to znači da nikada niste pronašli stavku:}return 0;

Čišćenje

1. korak

Poništite dodjelu binarnog stabla kada vaš program završi jer neće svi operativni sustavi to automatski riješiti. To je najbolje učiniti pomoću rekurzivne funkcije:void deallocate_binary_tree(STUDENT_DATA *tree) {

2. korak

Promatrajte:Ako nema stabla, nema što učiniti:if (!tree) return;

3. korak

Poništite lijevo i desno podstablo rekurzivno:deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->desno);

4. korak

Poništite dodjelu elementa i gotovi ste:free(tree);}

Savjet

Pretraživanje i dodavanje u binarna stabla također se može izvršiti pomoću rekurzije. Ovo će biti puno lakše napisati i održavati, ali malo teže razumjeti, dok se ne naviknete na to. Uobičajeno je stvoriti binarno stablo koje sadrži samo pokazivače na drugu C podatkovnu strukturu, često niz ili povezani popis, gdje se nalaze stvarni podaci. Svako binarno stablo je indeks za brzo pretraživanje jednog polja podataka popisa.

Upozorenje

Brisanje iz binarnog stabla vrlo je kompliciran algoritam u C-u, ali u mnogim upotrebama binarnog stabla elementi se nikada ne brišu.