Bináris fa C-ben
C-ben a bináris fa egy fa adatstruktúra példánya szülőcsomóponttal, amely legfeljebb két gyermek csomóponttal rendelkezhet; 0, 1 vagy 2 utódcsomópont. Minden egyes csomópont a bináris fa saját értéke van, és két mutatója van gyermekeire, az egyik a bal oldali, a másik a jobb gyerekre mutat.
A bináris fa nyilatkozata
A bináris fa nevű objektum segítségével deklarálható C-ben struct amely a fa egyik csomópontját ábrázolja.
struct csomópont {
adattípus var_name ;
struct csomópont * bal ;
struct csomópont * jobb ;
} ;
Fent az egyik nyilatkozata látható bináris fa csomópont neve csomópontként. Három értéket tartogat; az egyik az adattároló változó, a másik kettő pedig a gyermekre mutató mutatók. (a szülőcsomópont bal és jobb gyermeke).
A bináris fa tényei
Még nagy adathalmazok esetén is használja a bináris fa könnyebbé és gyorsabbá teszi a keresést. A faágak száma nincs korlátozva. Ellentétben a tömbökkel, bármilyen fát lehet készíteni és növelni az egyedtől elvárások alapján.
Bináris fa megvalósítása C-ben
Az alábbiakban lépésről lépésre bemutatjuk az a Bináris fa C-ben.
1. lépés: deklaráljon egy bináris keresőfát
Hozzon létre egy struktúra-csomópontot, amely három adattípussal rendelkezik, például adatok, *bal_gyermek és *jobb_gyermek, ahol az adatok egész típusúak lehetnek, és mind a *bal_gyermek, mind a *jobb_gyermek csomópontok deklarálhatók NULL-ként vagy nem.
struct csomópont{
int adat ;
struct csomópont * jobb_gyerek ;
struct csomópont * bal_gyerek ;
} ;
2. lépés: Hozzon létre új csomópontokat a bináris keresőfában
Hozzon létre egy új csomópontot egy olyan függvény létrehozásával, amely elfogad egy egész számot argumentumként, és megadja a mutatót az ezzel az értékkel létrehozott új csomópontra. Használja a malloc() függvényt C-ben a dinamikus memóriafoglaláshoz a létrehozott csomóponthoz. Inicializálja a bal és a jobb oldali gyermeket NULL értékre, és adja vissza a nodeName értéket.
struct csomópont * teremt ( adattípus adatok )
{
struct csomópont * nodeName = malloc ( mérete ( struct csomópont ) ) ;
nodeName -> adat = érték ;
nodeName -> bal_gyerek = nodeName -> jobb_gyerek = NULLA ;
Visszatérés nodeName ;
}
3. lépés: Helyezze be a jobb és bal oldali gyermeket a bináris fába
Hozzon létre egy beszúr_bal és beszúr_jobb függvényeket, amelyek két bemenetet fogadnak el, amelyek a beszúrandó érték és a mutató arra a csomópontra, amelyhez mindkét gyermek csatlakozik. Hívja meg a Create függvényt egy új csomópont létrehozásához, és rendelje hozzá a visszaadott mutatót a gyökér szülő bal oldali gyermekének bal mutatójához vagy a jobb oldali utód jobb mutatójához.
struct csomópont * insert_left ( struct csomópont * gyökér , adattípus adatok ) {gyökér -> bal = teremt ( adat ) ;
Visszatérés gyökér -> bal ;
}
struct csomópont * jobb beszúrás ( struct csomópont * gyökér , adattípus adatok ) {
gyökér -> jobb = teremt ( adat ) ;
Visszatérés gyökér -> jobb ;
}
4. lépés: A bináris fa csomópontjainak megjelenítése bejárási módszerekkel
A fákat három bejárási módszerrel tudjuk megjeleníteni C-ben. Ezek a bejárási módszerek a következők:
1: Előrendelési bejárás
Ebben a bejárási módszerben a csomópontokon megyünk keresztül egy irányban szülő_csomópont->bal_gyermek->jobb_gyermek .
üres előrendelés ( csomópont * gyökér ) {ha ( gyökér ) {
printf ( '%d \n ' , gyökér -> adat ) ;
display_pre_order ( gyökér -> bal ) ;
display_pre_order ( gyökér -> jobb ) ;
}
}
2: Rendelés utáni bejárás
Ennél a bejárási módszernél a csomópontokon keresztül megyünk át egy irányban a bal_gyermek->jobb_gyermek->szülőcsomópont-> .
üres display_post_order ( csomópont * gyökér ) {ha ( bináris_fa ) {
display_post_order ( gyökér -> bal ) ;
display_post_order ( gyökér -> jobb ) ;
printf ( '%d \n ' , gyökér -> adat ) ;
}
}
3: In-Order Traversal
Ebben a bejárási módszerben a csomópontokon megyünk keresztül egy irányban bal_csomópont->gyökér-gyermek->jobb_gyermek .
üres megjelenítés_sorrendben ( csomópont * gyökér ) {ha ( bináris_fa ) {
megjelenítés_sorrendben ( gyökér -> bal ) ;
printf ( '%d \n ' , gyökér -> adat ) ;
megjelenítés_sorrendben ( gyökér -> jobb ) ;
}
}
5. lépés: Hajtsa végre a törlést a bináris fában
A létrehozottakat törölhetjük Bináris fa mindkét szülőcsomópont-függvénnyel rendelkező gyermek törlésével a C-ben az alábbiak szerint.
üres delete_t ( csomópont * gyökér ) {ha ( gyökér ) {
delete_t ( gyökér -> bal ) ;
delete_t ( gyökér -> jobb ) ;
ingyenes ( gyökér ) ;
}
}
C Bináris keresőfa programja
A következő a bináris keresési fa teljes megvalósítása a C programozásban:
#include#include
struct csomópont {
int érték ;
struct csomópont * bal , * jobb ;
} ;
struct csomópont * csomópont1 ( int adat ) {
struct csomópont * tmp = ( struct csomópont * ) malloc ( mérete ( struct csomópont ) ) ;
tmp -> érték = adat ;
tmp -> bal = tmp -> jobb = NULLA ;
Visszatérés tmp ;
}
üres nyomtatás ( struct csomópont * gyökér_csomópont ) // a csomópontok megjelenítése!
{
ha ( gyökér_csomópont != NULLA ) {
nyomtatás ( gyökér_csomópont -> bal ) ;
printf ( '%d \n ' , gyökér_csomópont -> érték ) ;
nyomtatás ( gyökér_csomópont -> jobb ) ;
}
}
struct csomópont * csomópont beszúrása ( struct csomópont * csomópont , int adat ) // csomópontok beszúrása!
{
ha ( csomópont == NULLA ) Visszatérés csomópont1 ( adat ) ;
ha ( adat < csomópont -> érték ) {
csomópont -> bal = csomópont beszúrása ( csomópont -> bal , adat ) ;
} más ha ( adat > csomópont -> érték ) {
csomópont -> jobb = csomópont beszúrása ( csomópont -> jobb , adat ) ;
}
Visszatérés csomópont ;
}
int fő- ( ) {
printf ( 'A bináris keresőfa C megvalósítása! \n \n ' ) ;
struct csomópont * szülő = NULLA ;
szülő = csomópont beszúrása ( szülő , 10 ) ;
csomópont beszúrása ( szülő , 4 ) ;
csomópont beszúrása ( szülő , 66 ) ;
csomópont beszúrása ( szülő , Négy öt ) ;
csomópont beszúrása ( szülő , 9 ) ;
csomópont beszúrása ( szülő , 7 ) ;
nyomtatás ( szülő ) ;
Visszatérés 0 ;
}
A fenti kódban először deklaráljuk a csomópont segítségével struct . Ezután inicializálunk egy új csomópontot ' csomópont1 ” és dinamikusan lefoglalja a memóriát a használatával malloc() C-ben adatokkal és két mutatóval írja be a gyerekeket a deklarált csomópont használatával. Ezt követően megjelenítjük a csomópontot printf() függvényt, és hívja be a fő() funkció. Aztán a insertion_node() függvény jön létre, ahol ha a csomópont adata NULL, akkor csomópont1 megszűnt, különben az adatok a csomópont (szülője) a bal és a jobb oldali gyermeknek. A program végrehajtását a fő() függvény, amely egy csomópontot generál néhány minta csomópont felhasználásával gyermekként, majd In-Order bejárási metódusokkal nyomtatja ki a csomópont tartalmát.
Kimenet
Következtetés
A fákat gyakran használják az adatok nem lineáris formában való tárolására. Bináris fák olyan fafajták, ahol minden csomópontnak (szülőnek) két utóda van, a bal és a jobb gyermek. A bináris fa az adatok átvitelének és tárolásának sokoldalú módja. Hatékonyabb a C linked-listához képest. A fenti cikkben láttuk a Bináris fa lépésről lépésre történő megvalósításával a Bináris keresőfa C-ben.