Meni

Struktura podatkov binarnega drevesa v jeziku C ++

  • Glavni
  • Drugo
  • Struktura podatkov binarnega drevesa v jeziku C ++

binary tree data structure c

Preizkusite Naš Instrument Za Odpravo Težav

Ta poglobljena vadnica o binarnem drevesu v jeziku C ++ razlaga vrste, predstavitev, prehod, aplikacije in izvajanje binarnih dreves v jeziku C ++:

Binarno drevo je pogosto uporabljena drevesna struktura podatkov. Ko ima vsako vozlišče drevesa največ dve podrejeni vozlišči, se drevo imenuje binarno drevo.

Tipično binarno drevo bo torej imelo naslednje komponente:

  • Levo poddrevo
  • Koreninsko vozlišče
  • Desno poddrevo

=> Oglejte si celoten seznam vadnic za C ++ v tej seriji.

Binarno drevo v jeziku C ++

Kaj se boste naučili:

Binarno drevo v jeziku C ++

Slikovna predstavitev binarnega drevesa je prikazana spodaj:

Slikovna predstavitev binarnega drevesa

V danem binarnem drevesu je največje število vozlišč na kateri koli ravni 2l-1kjer je „l“ številka nivoja.

Tako je v primeru korenskega vozlišča na ravni 1 največje število vozlišč = 21-1= 20= 1

Ker ima vsako vozlišče v binarnem drevesu največ dve vozlišči, bo največ vozlišč na naslednji ravni 2 * 2l-1.

c ++ ide s prevajalnikom

Glede na binarno drevo globine ali višine h je največje število vozlišč v binarnem drevesu višine h = 2h- 1.

Zato je v binarnem drevesu višine 3 (prikazano zgoraj) največje število vozlišč = 23.-1 = 7.

Zdaj pa razpravljajmo o različnih vrstah binarnih dreves.

Vrste binarnega drevesa

Sledijo najpogostejše vrste binarnih dreves.

# 1) Polno binarno drevo

Binarno drevo, v katerem ima vsako vozlišče 0 ali 2 otroka, se imenuje polno binarno drevo.

Polno binarno drevo

Zgoraj je prikazano celotno binarno drevo, v katerem lahko vidimo, da imajo vsa njegova vozlišča, razen vozlišč listov, dva otroka. Če je L število listnih vozlišč in 'l' število notranjih ali nelistnih vozlišč, potem je za polno binarno drevo L = l + 1.

# 2) Popolno binarno drevo

Popolno binarno drevo ima zapolnjene vse ravni, razen zadnje ravni, zadnja raven pa ima vsa svoja vozlišča toliko kot levo.

Popolno binarno drevo

Zgoraj prikazano drevo je popolno binarno drevo. Tipičen primer popolnega binarnega drevesa je binarni kup, o katerem bomo razpravljali v kasnejših vajah.

# 3) Popolno binarno drevo

Binarno drevo se imenuje popolno, če imajo vsa njegova notranja vozlišča dva otroka in so vsa vozlišča listov na isti ravni.

Popolno binarno drevo

Zgornji primer binarnega drevesa je popolno binarno drevo, saj ima vsako njegovo vozlišče dva otroka in so vsa vozlišča listov na isti ravni.

Popolno binarno drevo višine h ima 2h- 1 število vozlišč.

# 4) Izrojeno drevo

Binarno drevo, kjer ima vsako notranje vozlišče samo enega otroka, se imenuje izrojeno drevo.

Izrojeno drevo

Zgoraj prikazano drevo je izrojeno drevo. Kar zadeva delovanje tega drevesa, so izrojena drevesa enaka povezanim seznamom.

# 5) Uravnoteženo binarno drevo

Binarno drevo, pri katerem se globina obeh poddreves vsakega vozlišča nikoli ne razlikuje za več kot 1, se imenuje uravnoteženo binarno drevo.

Uravnoteženo binarno drevo

Zgoraj prikazano binarno drevo je uravnoteženo binarno drevo, saj globina obeh pod dreves vsakega vozlišča ni večja od 1. Drevesa AVL, o katerih bomo razpravljali v naslednjih vajah, so običajno uravnoteženo drevo.

Predstavitev binarnega drevesa

Binarnemu drevesu se pomnilnik dodeli na dva načina.

# 1) Zaporedna predstavitev

To je najpreprostejša tehnika za shranjevanje drevesne strukture podatkov. Matrika se uporablja za shranjevanje drevesnih vozlišč. Število vozlišč v drevesu določa velikost polja. Koreninsko vozlišče drevesa je shranjeno pri prvem indeksu v matriki.

Na splošno, če je vozlišče shranjeno na ithlokacija, potem je levi in ​​desni otrok shranjen na lokaciji 2i oziroma 2i + 1.

Razmislite o naslednjem binarnem drevesu.

Vzorec binarnega drevesa

Zaporedna predstavitev zgornjega binarnega drevesa je naslednja:

pretvori matriko char v int c ++

zaporedna predstavitev binarnega drevesa

V zgornji predstavitvi vidimo, da sta levi in ​​desni podrejeni del vsakega vozlišča shranjena na lokacijah 2 * (node_location) in 2 * (node_location) +1.

Na primer, lokacija vozlišča 3 v matriki je 3. Torej bo njen levi otrok postavljen na 2 * 3 = 6. Njegov desni otrok bo na lokaciji 2 * 3 +1 = 7. Kot lahko vidimo v matriki, otroci od 3, ki sta 6 in 7, so nameščeni na lokaciji 6 in 7 v nizu.

Zaporedna predstavitev drevesa je neučinkovita, saj matrika, ki se uporablja za shranjevanje drevesnih vozlišč, zavzame veliko prostora v pomnilniku. Ko drevo raste, postane ta predstavitev neučinkovita in jo je težko upravljati.

To pomanjkljivost odpravimo s shranjevanjem drevesnih vozlišč na povezani seznam. Če je drevo prazno, bo prvo mesto, ki shranjuje korensko vozlišče, nastavljeno na 0.

# 2) Predstavništvo s povezanim seznamom

Pri tej vrsti predstavitve se za shranjevanje drevesnih vozlišč uporablja povezan seznam. Več vozlišč je razpršenih v pomnilniku na ne-sosednjih lokacijah, vozlišča pa so povezana kot razmerje med staršem in otrokom kot drevo.

Naslednji diagram prikazuje predstavitev povezanega seznama za drevo.

Predstavitev povezanega seznama

Kot je prikazano v zgornji predstavitvi, ima vsako povezano vozlišče seznama tri komponente:

  • Levi kazalec
  • Podatkovni del
  • Desni kazalec

Levi kazalec ima kazalec na levega podrejenega vozlišča; desni kazalec ima kazalec na desnega podrejenega vozlišča, medtem ko podatkovni del vsebuje dejanske podatke vozlišča. Če za dano vozlišče (listno vozlišče) ni podrejenih, so levi in ​​desni kazalci za to vozlišče nastavljeni na nič, kot je prikazano na zgornji sliki.

Izvajanje binarnega drevesa v jeziku C ++

Nato razvijemo binarni drevesni program z uporabo povezane predstavitve seznama v jeziku C ++. Za razglasitev enega vozlišča uporabimo strukturo, nato pa s pomočjo razreda razvijemo povezan seznam vozlišč.

#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: '<

Izhod:

Ustvarjeno binarno drevo:

5 10 15 20 30 40 45

Prehod binarnega drevesa

O potekih smo že razpravljali v naši osnovni vaji o drevesih. V tem razdelku izvedimo program, ki v binarno drevo vstavi vozlišča in prikaže tudi vse tri prečke, to je v vrstnem redu, prednaročilo in naknadno naročilo za binarno drevo.

#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:'<

Izhod:

Notranji prehod:

A B C D E F G

Prehod po pošti:

G F E D C B A

Prehod po naročilu:

A B C D E F G

Aplikacije binarnega drevesa

Binarno drevo se uporablja v številnih aplikacijah za shranjevanje podatkov.

Spodaj je navedenih nekaj pomembnih aplikacij binarnih dreves:

  • Binarna drevesa za iskanje: Binarna drevesa se uporabljajo za izdelavo binarnega iskalnega drevesa, ki se uporablja v številnih aplikacijah za iskanje, kot so nabori in zemljevidi v številnih jezikovnih knjižnicah.
  • Hash drevesa: Uporablja se za preverjanje zgoščevanja predvsem v specializiranih aplikacijah za podpisovanje slik.
  • Kupe: Gomile se uporabljajo za izvajanje prioritetnih čakalnih vrst, ki se uporabljajo za usmerjevalnike, procesorje razporejanja v operacijskem sistemu itd.
  • Huffmanovo kodiranje: Huffmanovo kodno drevo se uporablja v algoritmih stiskanja (kot je stiskanje slik) in tudi v kriptografskih aplikacijah.
  • Sintaksno drevo: Prevajalniki pogosto sestavijo sintaksna drevesa, ki niso nič drugega kot binarna drevesa, da razčlenijo izraze, uporabljene v programu.

Zaključek

Binarna drevesa so široko uporabljene podatkovne strukture v industriji programske opreme. Binarna drevesa so drevesa, katerih vozlišča imajo največ dva podrejena vozlišča. Videli smo različne vrste binarnih dreves, kot so polno binarno drevo, popolno binarno drevo, popolno binarno drevo, degenerirano binarno drevo, uravnoteženo binarno drevo itd.

Podatke o binarnem drevesu je mogoče tudi prehoditi s pomočjo tehnik preusmeritve inorder, preorder in postorder, ki smo jih videli v prejšnji vadnici. V pomnilniku je lahko binarno drevo predstavljeno s povezanim seznamom (nespremenljiv pomnilnik) ali nizi (zaporedno predstavljanje).

Predstavitev povezanega seznama je učinkovitejša v primerjavi z nizi, saj polja zavzamejo veliko prostora.

=> Tukaj si oglejte najboljše vadnice za C ++.

Priporočeno branje

^