Hogyan hozzunk létre bináris fát a C-ben
Hogyan készítsünk bináris fát C-ben. A bináris fák C-ben jó módszert jelentenek az adatok dinamikus rendszerezésére a könnyű keresés érdekében. A karbantartásuk azonban sok munkát igényel.
Bináris fa létrehozása
1. lépés
Strukturálja a bináris fát. Minden bináris fának szüksége lesz egy szerkezetre, még akkor is, ha csak egy változója van. Válasszon egy nevet, majd a typedef használatával hozza létre:typedef struct student_data STUDENT_DATA;
2. lépés
Határozza meg a szerkezetet. Tartalmazzon két mutatót ugyanarra a struktúrára:struct diák_adatok { int diák_azonosítója; int tanulói_évfolyam; STUDENT_DATA balra, jobbra;};
3. lépés
Rendeljen hozzá egy mutatót ehhez az adatstruktúrához, inicializálva azt NULL értékre, hogy ez legyen a fa feje:STUDENT_DATA *students =NULL;
Hozzáadás a bináris fához
1. lépés
Rendeljen két ideiglenes mutatót az adatstruktúrához:STUDENT_DATA new_student, cur_student;
2. lépés
A malloc() használatával hozzon létre egy új elemet, mindig ellenőrizze a hibát:if ((new_student =malloc(sizeof(STUDENT_DATA))) ==NULL) { abort(); }
3. lépés
Töltse ki az új elem mezőit. A bal és jobb oldali mezőket állítsa NULL értékre:new_student->student_ID =newID;new_student->student_size =newsize;new_student->left =NULL;new_student->right =NULL;
4. lépés
Tekintsük a fej változót. Ha a fej változó NULL, akkor ez az első elem, amelyet a fához adunk, ezért állítsuk be a head változót úgy, hogy rá mutasson, és kész is:if (!students) { students =new_student; Visszatérés; }
5. lépés
Kezdje a fa tetején:cur_student =diákok;while (cur_student) {
6. lépés
Kezelje a duplikált bejegyzést, ha az új érték és az aktuális érték egyenlő:if (newID ==cur_student->student_ID) { abort(); }
7. lépés
Foglalkozz az egyenlőtlen értékekkel. Ha az új érték kisebb, mint az aktuális érték, az új elem balra kerül. Azonnal adja hozzá, ha nincs semmi a bal oldalon. Ellenkező esetben lépjen balra, és ciklus:if (újID
8. lépés
Tegye ugyanezt a jobb oldalon, különben:} else { if (cur_student->right ==NULL) { cur_student->right =hírhallgató; visszatérés 1; } cur_student =cur_student->right; }}
Keresés a bináris fában
1. lépés
Hozzon létre egy ideiglenes változót, amely az adatstruktúrára mutat:STUDENT_DATA *cur_student;
2. lépés
Állítsa be ideiglenes változóját a head változóra:cur_student =students_head;
3. lépés
Lapozzon át az elemeken, és ellenőrizze a kívánt értéket:while (cur_student) { if (cur_student->student_ID ==15) { return cur_student->student_grade; }
4. lépés
Elágazás balra vagy jobbra, és ciklus, ha nem található:if (cur_student->student_ID <15) { cur_student =cur_student->right; } else { cur_student =cur_student->left; }
5. lépés
Nézd meg, hogy a hurok véget ér-e. Ha igen, az azt jelenti, hogy soha nem találta meg az elemet:}return 0;
Tisztítás
1. lépés
A program lejártakor bontsa ki a bináris fa kiosztását, mivel nem minden operációs rendszer kezeli ezt automatikusan. Ezt a legjobb rekurzív függvény használatával megtenni:void deallocate_binary_tree(STUDENT_DATA *fa) {
2. lépés
Figyeld meg:Ha nincs fa, nincs mit tenni:if (!fa) visszatérés;
3. lépés
A bal és a jobb oldali részfa rekurzív felosztása:deallocate_binary_tree(tree->left); deallocate_binary_tree(tree->right);
4. lépés
Bontsa ki az elem kiosztását, és kész is:free(tree);}
Tipp
A keresés és a bináris fákhoz való hozzáadás rekurzióval is elvégezhető. Ezt sokkal könnyebb lesz írni és karbantartani, de egy kicsit nehezebb megérteni, amíg meg nem szokja. Gyakori olyan bináris fa létrehozása, amely csak mutatókat tartalmaz egy második C adatszerkezetre, gyakran tömbre vagy linkelt listára, ahol a tényleges adatok találhatók. Minden bináris fa egy index, amellyel gyorsan kereshet a listaadatok egyetlen mezőjében.
Figyelmeztetés
A bináris fából való törlés egy nagyon bonyolult algoritmus a C nyelven, de a bináris fák sok felhasználásánál az elemek soha nem törlődnek.