Meni

Struktura podataka binarnog stabla u C ++

binary tree data structure c

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj detaljni vodič o binarnom stablu u C ++-u objašnjava vrste, predstavljanje, prelazak, primjene i implementaciju binarnih stabala u C ++:

Binarno stablo je široko korištena struktura podataka stabla. Kada svaki čvor stabla ima najviše dva podređena čvora, stablo se naziva Binarno stablo.

Tako će tipično binarno stablo imati sljedeće komponente:

  • Lijevo podstablo
  • Korijenski čvor
  • Pravo podstablo

=> Pazite na cjelovit popis tutorijala za C ++ u ovoj seriji.

Binarno stablo u C ++

Što ćete naučiti:

Binarno stablo u C ++

Slikovni prikaz binarnog stabla prikazan je u nastavku:

Slikovni prikaz binarnog stabla

U danom binarnom stablu, maksimalni broj čvorova na bilo kojoj razini je 2l-1gdje je 'l' broj razine.

Dakle, u slučaju korijenskog čvora na razini 1, maksimalan broj čvorova = 21-1= 20= 1

Kako svaki čvor u binarnom stablu ima najviše dva čvora, maksimalni čvorovi na sljedećoj razini bit će 2 * 2l-1.

kako stvoriti novi projekt u pomrčini

S obzirom na binarno stablo dubine ili visine h, maksimalan broj čvorova u binarnom stablu visine h = 2h- 1.

Dakle, u binarnom stablu visine 3 (prikazano gore), maksimalni broj čvorova = 23-1 = 7.

Sada ćemo razgovarati o različitim vrstama binarnih stabala.

Vrste binarnog stabla

Slijede najčešće vrste binarnih stabala.

# 1) Potpuno binarno stablo

Binarno stablo u kojem svaki čvor ima 0 ili 2 djece naziva se punim binarnim stablom.

Potpuno binarno stablo

Iznad je prikazano potpuno binarno stablo u kojem možemo vidjeti da svi njegovi čvorovi, osim čvorova lista, imaju dvoje djece. Ako je L broj lisnih čvorova, a ‘l’ broj unutarnjih ili nelistnih čvorova, tada je za puno binarno stablo L = l + 1.

# 2) Kompletno binarno stablo

Kompletno binarno stablo ima sve razine ispunjene, osim posljednje razine, a zadnja razina ima sve svoje čvorove koliko je lijevo.

Kompletno Binarno stablo

Gore prikazano stablo kompletno je binarno stablo. Tipičan primjer cjelovitog binarnog stabla je binarna hrpa o kojoj ćemo razgovarati u kasnijim tutorijalima.

# 3) Savršeno binarno stablo

Binarno stablo naziva se savršenim kada svi njegovi unutarnji čvorovi imaju dvoje djece i kada su svi čvorići lista na istoj razini.

Savršeno binarno stablo

Primjer binarnog stabla prikazan gore je savršeno binarno stablo jer svaki od njegovih čvorova ima dvoje djece i svi su čvorići lista na istoj razini.

Savršeno binarno stablo visine h ima 2h- 1 broj čvorova.

# 4) Izrođeno stablo

Binarno stablo u kojem svaki unutarnji čvor ima samo jedno dijete naziva se izrođeno stablo.

Izrođeno stablo

Stablo prikazano gore je izrođeno stablo. Što se tiče izvedbe ovog stabla, izrođena stabla jednaka su povezanim popisima.

# 5) Uravnoteženo binarno stablo

Binarno stablo u kojem se dubina dva podstabla svakog čvora nikada ne razlikuje za više od 1 naziva se uravnoteženim binarnim stablom.

Uravnoteženo binarno stablo

Gore prikazano binarno stablo uravnoteženo je binarno stablo, jer dubina dva podstabla svakog čvora nije veća od 1. AVL stabla o kojima ćemo raspravljati u sljedećim vodičima uobičajeno su uravnoteženo stablo.

Prikaz binarnog stabla

Binarnom stablu memorija se dodjeljuje na dva načina.

# 1) Sekvencijalno predstavljanje

Ovo je najjednostavnija tehnika za pohranu strukture podataka stabla. Niz se koristi za spremanje čvorova stabla. Broj čvorova u stablu definira veličinu niza. Korijenski čvor stabla pohranjuje se kod prvog indeksa u nizu.

regularni izrazi u c ++

Općenito, ako je čvor pohranjen na ithmjesto tada je lijevo i desno dijete pohranjeno na 2i odnosno 2i + 1 mjestu.

Razmotrite sljedeće Binarno stablo.

Uzorak binarnog stabla

Sekvencijalni prikaz gornjeg binarnog stabla je sljedeći:

sekvencijalni prikaz binarnog stabla

U gornjem prikazu vidimo da su lijevo i desno podređeno mjesto svakog čvora pohranjeni na mjestima 2 * (mjesto čvora) i 2 * (mjesto čvora) +1.

Na primjer, mjesto čvora 3 u polju je 3. Dakle, njegovo lijevo dijete bit će postavljeno na 2 * 3 = 6. Njegovo desno dijete bit će na mjestu 2 * 3 +1 = 7. Kao što možemo vidjeti u nizu, djeca od 3 koji su 6 i 7 smješteni su na mjestu 6 i 7 u nizu.

Sekvencijalni prikaz stabla je neučinkovit jer niz koji se koristi za spremanje čvorova stabla zauzima puno prostora u memoriji. Kako stablo raste, taj prikaz postaje neučinkovit i teško za upravljanje.

Ovaj se nedostatak prevladava spremanjem čvorova stabla na povezani popis. Imajte na umu da ako je stablo prazno, tada će prvo mjesto na kojem se nalazi korijenski čvor biti postavljeno na 0.

# 2) Zastupljenost na povezanom popisu

U ovoj vrsti predstavljanja, povezani popis koristi se za spremanje čvorova stabla. Nekoliko čvorova raštrkano je u memoriji na nestalnim mjestima i čvorovi su povezani pomoću odnosa roditelj-dijete poput stabla.

Sljedeći dijagram prikazuje prikaz povezanog popisa za stablo.

Zastupljenost na povezanom popisu

Kao što je prikazano u gornjem prikazu, svaki povezani čvor popisa ima tri komponente:

  • Lijevi pokazivač
  • Dio podataka
  • Desni pokazivač

Lijevi pokazivač ima pokazivač na lijevo podređeno mjesto čvora; desni pokazivač ima pokazivač na desno podređeno mjesto čvora, dok dio podataka sadrži stvarne podatke čvora. Ako nema djece za dati čvor (lisni čvor), tada su lijevi i desni pokazivači za taj čvor postavljeni na nulu, kao što je prikazano na gornjoj slici.

Implementacija binarnog stabla u C ++

Dalje, razvijamo program binarnog stabla koristeći povezano predstavljanje popisa u C ++. Koristimo strukturu za deklariranje pojedinog čvora, a zatim pomoću klase razvijamo povezani popis čvorova.

#include using namespace std; struct bintree_node{ bintree_node *left; bintree_node *right; int data; } ; class bst{ bintree_node *root; public: bst(){ root=NULL; } int isempty() { return(root==NULL); } void insert(int item); void displayBinTree(); void printBinTree(bintree_node *); }; void bst::insert(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL){ parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bst::displayBinTree(){ printBinTree(root); } void bst::printBinTree(bintree_node *ptr){ if(ptr!=NULL){ printBinTree(ptr->left); cout<<' '<data<<' '; printBinTree(ptr->right); } } int main(){ bst b; b.insert(20); b.insert(10); b.insert(5); b.insert(15); b.insert(40); b.insert(45); b.insert(30); cout<<'Binary tree created: '<

Izlaz:

Stvoreno binarno stablo:

5 10 15 20 30 40 45

Prijelaz binarnog stabla

Već smo razgovarali o prijelazima u našem osnovnom vodiču o drveću. U ovom ćemo odjeljku implementirati program koji ubacuje čvorove u binarno stablo i također demonstrira sva tri prelaza, tj. Inorder, preorder i postorder, za binarno stablo.

#include using namespace std; //binary tree node declaration struct bintree_node{ bintree_node *left; bintree_node *right; char data; } ; class bintree_class{ bintree_node *root; public: bintree_class(){ root=NULL; } int isempty() { return(root==NULL); } void insert_node(int item); void inorder_seq(); void inorder(bintree_node *); void postorder_seq(); void postorder(bintree_node *); void preorder_seq(); void preorder(bintree_node *); }; void bintree_class::insert_node(int item){ bintree_node *p=new bintree_node; bintree_node *parent; p->data=item; p->left=NULL; p->right=NULL; parent=NULL; if(isempty()) root=p; else{ bintree_node *ptr; ptr=root; while(ptr!=NULL) { parent=ptr; if(item>ptr->data) ptr=ptr->right; else ptr=ptr->left; } if(itemdata) parent->left=p; else parent->right=p; } } void bintree_class::inorder_seq() { inorder(root); } void bintree_class::inorder(bintree_node *ptr) { if(ptr!=NULL){ inorder(ptr->left); cout<<' '<data<<' '; inorder(ptr->right); } } void bintree_class::postorder_seq() { postorder(root); } void bintree_class::postorder(bintree_node *ptr) { if(ptr!=NULL){ postorder(ptr->left); postorder(ptr->right); cout<<' '<data<<' '; } } void bintree_class::preorder_seq() { preorder(root); } void bintree_class::preorder(bintree_node *ptr) { if(ptr!=NULL){ cout<<' '<data<<' '; preorder(ptr->left); preorder(ptr->right); } } int main() { bintree_class bintree; bintree.insert_node('A'); bintree.insert_node('B'); bintree.insert_node('C'); bintree.insert_node('D'); bintree.insert_node('E'); bintree.insert_node('F'); bintree.insert_node('G'); cout<<'Inorder traversal:'<

Izlaz:

Neobavezno zaobilaženje:

A B C D E F G

Prijelaz putem pošte:

G F E D C B A

Prijelaz predbilježbe:

A B C D E F G

Primjene binarnog stabla

Binarno stablo koristi se u mnogim aplikacijama za pohranu podataka.

U nastavku su navedene neke od važnih primjena binarnih stabala:

  • Binarna stabla za pretraživanje: Binarna stabla koriste se za izgradnju binarnog stabla pretraživanja koje se koristi u mnogim aplikacijama za pretraživanje poput skupova i karata u mnogim jezičnim knjižnicama.
  • Hash drveće: Koristi se za provjeru raspršivanja uglavnom u specijaliziranim aplikacijama za potpisivanje slika.
  • Hrpe: Gomile se koriste za implementaciju prioritetnih redova koji se koriste za usmjerivače, procesore raspoređivanja u operativnom sustavu itd.
  • Huffmanovo kodiranje: Huffmanovo stablo kodiranja koristi se u algoritmima kompresije (poput kompresije slike), kao i u kriptografskim aplikacijama.
  • Sintaksno stablo: Prevoditelji često grade sintaksna stabla koja nisu ništa drugo do binarna stabla za raščlanjivanje izraza korištenih u programu.

Zaključak

Binarna stabla su široko korištene podatkovne strukture u softverskoj industriji. Binarna stabla su stabla čiji čvorovi imaju najviše dva podređena čvora. Vidjeli smo razne vrste binarnih stabala poput punog binarnog stabla, cjelovitog binarnog stabla, savršenog binarnog stabla, izrođenog binarnog stabla, uravnoteženog binarnog stabla itd.

Binarnim podacima o stablu također se može prelaziti pomoću tehnika zaokruživanja inorder, preorder i postorder koje smo vidjeli u našem prethodnom vodiču. U memoriji se binarno stablo može predstaviti pomoću povezanog popisa (nesuvisla memorija) ili nizova (sekvencijalni prikaz).

Prikazivanje povezanih popisa učinkovitije je u usporedbi s nizovima, jer nizovi zauzimaju puno prostora.

=> Ovdje pogledajte najbolje tutorijale za C ++.

Preporučena literatura

^