hirdetések

a fa az élek által összekapcsolt csomópontokat jelöli. Megbeszéljük bináris fa vagy bináris keresési fa kifejezetten.

A bináris fa egy speciális adatstruktúra, amelyet adattárolási célokra használnak. A bináris fának különleges feltétele van, hogy minden csomópontnak legfeljebb két gyermeke lehet., A bináris fának mind a rendezett tömb, mind a kapcsolt lista előnyei vannak, mivel a keresés olyan gyors, mint egy rendezett tömbben, a beillesztési vagy törlési művelet pedig olyan gyors, mint a kapcsolt listában.

fontos kifejezések

a következő fontos kifejezések a fa tekintetében.

  • Path-Path utal, hogy a sorrend a csomópontok szélei mentén egy fa.

  • gyökér-a fa tetején lévő csomópontot gyökérnek nevezik. Fánként csak egy gyökér van, a gyökér csomóponttól bármely csomópontig pedig egy út.,

  • szülő − a gyökércsomópont kivételével minden csomópontnak van egy éle felfelé a szülő nevű csomópontig.

  • gyermek-a csomópont alatt egy adott csomópont csatlakozik a széle lefelé nevezzük gyermek csomópont.

  • Leaf-a csomópont, amely nem rendelkezik gyermek csomópont nevezzük a leaf csomópont.

  • Subtree-Subtree jelenti a leszármazottai egy csomópont.

  • A látogatás a csomópont értékének ellenőrzésére utal, amikor a vezérlő a csomóponton van.

  • áthaladó-áthaladó jelenti áthaladó csomópontok egy adott sorrendben.,

  • szintek-egy csomópont szintje egy csomópont generációját jelenti. Ha a gyökércsomópont a 0. szinten van, akkor a következő gyermekcsomópont az 1.szinten van, az unokája a 2. szinten van, stb.

  • keys-Keys-Key egy csomópont értékét jelenti, amely alapján egy csomópont Keresési műveletét kell végrehajtani.

bináris keresési fa reprezentáció

a bináris keresési fa különleges viselkedést mutat. A csomópont bal gyermekének a szülő értékénél kisebb értékűnek kell lennie, a csomópont jobb gyermekének pedig nagyobbnak kell lennie, mint a szülő értékének.,

a fát csomópontobjektummal valósítjuk meg, és referenciákon keresztül kapcsoljuk össze őket.

fa csomópont

a fa csomópont írására szolgáló kód hasonló lenne az alább megadotthoz. Van egy adatrésze és hivatkozásai a bal és a jobb gyermek csomópontjaira.

struct node { int data; struct node *leftChild; struct node *rightChild;};

egy fában minden csomópont közös konstrukcióval rendelkezik.

BST Basic Operations

a bináris keresési fa adatstruktúráján végrehajtható alapvető műveletek a következők –

  • beszúr egy elemet egy fába / hozzon létre egy fát.,

  • keresés-keres egy elemet egy fa.

  • előrendelés egy fa előrendelése.

  • Inorder Traversal-egy fát sorrendben halad át.

  • Postorder Traversal-egy fát utómunkában halad át.

meg kell tanulnunk létrehozni (beilleszteni) egy faszerkezetet, és keresni egy adatelemet egy fában ebben a fejezetben. A következő fejezetben megismerjük a fa áthaladási módszereit.

Beszúrási művelet

az első beillesztés létrehozza a fát., Ezután, amikor egy elemet be kell illeszteni, először keresse meg a megfelelő helyet. Indítsa el a keresést a gyökércsomópontból, majd ha az adatok kisebbek, mint a kulcsérték, keresse meg az üres helyet a bal oldali altípusban, majd helyezze be az adatokat. Ellenkező esetben keresse meg az üres helyet a megfelelő altípusban, majd helyezze be az adatokat.,

Algoritmus

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

Végrehajtási

A végrehajtás a függvény beszúrása lehetőséget kell kinéznie −

Keresés Művelet

Ha egy elem, hogy keresni kezdjétek a gyökér csomópont, akkor, ha az adat kisebb, mint a kulcs értéke, akkor keressük meg a elemet a bal részfa. Ellenkező esetben keresse meg az elemet a megfelelő altípusban. Kövesse ugyanazt az algoritmust minden csomóponthoz.

algoritmus 

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

ennek az algoritmusnak a végrehajtása így néz ki.,

a bináris keresőfák adatstruktúrájának megvalósításáról ide kattintva tájékozódhat.