Meni

Stabla u C ++: Osnovna terminologija, tehnike prelaska i tipovi stabala C ++

  • Glavni
  • Ostalo
  • Stabla u C ++: Osnovna terminologija, tehnike prelaska i tipovi stabala C ++

trees c basic terminology

Isprobajte Naš Instrument Za Uklanjanje Problema

Ovaj produbljeni vodič o drveću C ++ objašnjava tipove drveća, tehnike prelaska stabala i osnovnu terminologiju sa slikama i primjerima programa:

U ovoj C ++ seriji do sada smo vidjeli linearnu strukturu podataka i statičke i dinamičke prirode. Sada ćemo nastaviti s nelinearnom strukturom podataka. Prva struktura podataka u ovoj kategoriji je „Drveće“.

Stabla su nelinearne hijerarhijske strukture podataka. Stablo je skup čvorova međusobno povezanih pomoću 'rubova' koji su usmjereni ili neusmjereni. Jedan od čvorova označen je kao „korijenski čvor”, a preostali čvorovi nazivaju se podređenim čvorovima ili lisnim čvorovima korijenskog čvora.

Općenito, svaki čvor može imati toliko djece, ali samo jedan roditeljski čvor.

=> Pogledajte cijelu C ++ seriju treninga

Stablo u C ++

Čvorovi stabla ili se na istoj razini nazivaju sestrinskim čvorovima ili mogu imati odnos roditelja i djeteta. Čvorovi s istim roditeljem su čvorovi braće i sestara.

Što ćete naučiti:

Drveće u C ++

Slijedi primjer stabla s raznim dijelovima.

Stablo u C ++ s raznim dijelovima

Prođimo kroz definicije nekih osnovnih pojmova koje koristimo za drveće.

  • Korijenski čvor: Ovo je najviši čvor u hijerarhiji stabla. U gornjem dijagramu Čvor A je korijenski čvor. Imajte na umu da korijenski čvor nema roditelja.
  • Lisni čvor: To je najniži čvor u hijerarhiji stabla. Lisnati čvorovi su čvorovi koji nemaju nijedan podređeni čvor. Poznati su i kao vanjski čvorovi. Čvorovi E, F, G, H i C u gornjem stablu su svi čvorovi listova.
  • Podstablo: Podstablo predstavlja različite potomke čvora kada korijen nije null. Stablo se obično sastoji od korijenskog čvora i jednog ili više podstabala. U gornjem dijagramu (B-E, B-F) i (D-G, D-H) su podstabla.
  • Nadređeni čvor: Bilo koji čvor, osim korijenskog čvora koji ima podređeni čvor i rub prema gore prema roditelju.
  • Čvor predaka: To je bilo koji prethodnički čvor na putu od korijena do tog čvora. Imajte na umu da korijen nema pretke. U gornjem dijagramu, A i B su preci E.
  • Ključ: Predstavlja vrijednost čvora.
  • Razina: Predstavlja generiranje čvora. Korijenski čvor uvijek je na razini 1. Podređeni čvorovi korijena su na razini 2, unuci korijena su na razini 3 i tako dalje. Općenito je svaki čvor na razini višoj od svog roditelja.
  • Staza: Put je slijed uzastopnih bridova. U gornjem dijagramu put do E je A => B-> E.
  • Stupanj: Stupanj čvora označava broj djece koju čvor ima. U gornjem dijagramu stupanj B i D je po 2, dok je stupanj C 0.

Vrste drveća C ++

Struktura podataka stabla može se klasificirati u sljedeće podtipove kao što je prikazano na donjem dijagramu.

Vrste stabla u C ++

# 1) Opće stablo

Opće stablo osnovni je prikaz stabla. Ima čvor i jedan ili više podređenih čvorova. Čvor najviše razine, tj. Korijenski čvor prisutan je na razini 1, a svi ostali čvorovi mogu biti prisutni na različitim razinama.

Općenito stablo prikazano je na donjoj slici.

Opće stablo

Kao što je prikazano na gornjoj slici, opće stablo može sadržavati neograničen broj podstabala. Čvorovi B, C i D prisutni su na razini 2 i čvorovi su braće i sestara. Slično tome, čvorovi E, F, G i H također su čvorovi braće i sestara.

Čvorovi prisutni na različitim razinama mogu pokazivati ​​odnos roditelja i djeteta. Na gornjoj slici čvorovi B, C i D djeca su A. Čvorovi E i F djeca su B, dok su čvorovi G i H djeca D.

Općenito stablo prikazano je u nastavku pomoću primjene C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Izlaz:

Stvoreno je opće stablo:

10

/

20 30

/

40

# 2) Šume

Kad god izbrišemo korijenski čvor sa stabla i rubove koji spajaju elemente sljedeće razine i korijen, dobivamo razdvojene skupove stabala kao što je prikazano u nastavku.

Šume

Na gornjoj slici dobili smo dvije šume brisanjem korijenskog čvora A i tri ruba koji su povezivali korijenski čvor s čvorovima B, C i D.

# 3) Binarno stablo

Struktura podataka stabla u kojoj svaki čvor ima najviše dva podređena čvora naziva se binarno stablo. Binarno stablo najpopularnija je struktura podataka stabla i koristi se u nizu aplikacija poput procjene izraza, baza podataka itd.

Sljedeća slika prikazuje binarno stablo.

novi privatni poslužitelj world of warcraft

Binarno stablo

Na gornjoj slici vidimo da čvorovi A, B i D imaju po dvoje djece. Binarno stablo u kojem svaki čvor ima točno nula ili dvoje djece naziva se potpuno binarno stablo. U ovom stablu nema čvorova koji imaju jedno dijete.

Kompletno binarno stablo ima binarno stablo koje je potpuno ispunjeno, osim najniže razine koja se popunjava slijeva udesno. Gore prikazano binarno stablo potpuno je binarno stablo.

Slijedi jednostavan program za demonstraciju binarnog stabla. Imajte na umu da je izlaz stabla redoslijed zaokretnih redoslijeda ulaznog stabla.

#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

# 4) Binarno stablo pretraživanja

Binarno stablo koje je poredano naziva se binarno stablo pretraživanja. U binarnom stablu pretraživanja, čvorovi s lijeve strane manji su od korijenskog, dok su čvorovi s desne strane veći ili jednaki korijenskom čvoru.

Primjer binarnog stabla pretraživanja prikazan je u nastavku.

Binarno stablo pretraživanja

Na gornjoj slici možemo vidjeti da su svi lijevi čvorovi manji od 20, što je korijenski element. S druge strane, pravi čvorovi veći su od korijenskog čvora. Binarno stablo pretraživanja koristi se u tehnikama pretraživanja i sortiranja.

# 5) Stablo izraza

Binarno stablo koje se koristi za procjenu jednostavnih aritmetičkih izraza naziva se stablo izraza.

Jednostavno stablo izraza prikazano je u nastavku.

Stablo izraza

U gornjem uzorku stabla izraza predstavljamo izraz (a + b) / (a-b). Kao što je prikazano na gornjoj slici, nelistni čvorovi stabla predstavljaju operatore izraza, dok lisni čvorovi predstavljaju operande.

Stabla izraza uglavnom se koriste za rješavanje algebarskih izraza.

Tehnike presijecanja stabala

Vidjeli smo linearne strukture podataka kao što su nizovi, povezani popisi, stogovi, redovi itd. Sve ove strukture podataka imaju zajedničku tehniku ​​obilaženja koja strukturu prelazi samo na jedan način, tj. Linearno.

Ali u slučaju drveća, imamo različite tehnike prijelaza kako su navedene u nastavku:

# 1) Redom: U ovoj tehnici prelaska prvo prelazimo lijevo podstablo dok više nema čvorova u lijevom podstablu. Nakon toga posjećujemo korijenski čvor, a zatim nastavljamo s prelaskom desnog podstabla sve dok u desnom podstablu više nema čvorova. Stoga je redoslijed inOrder prelaska lijevo-> korijen-> desno.

# 2) Predbilježba: Za tehniku ​​prelaska predbilježbe prvo obrađujemo korijenski čvor, zatim prelazimo cijelo lijevo podstablo i na kraju prelazimo desno podstablo. Stoga je redoslijed prijelaza predbilježbe korijen-> lijevo-> desno.

# 3) Post-narudžba: U tehnici prijelaza nakon narudžbe prelazimo lijevo podstablo, zatim desno podstablo i na kraju korijenski čvor. Redoslijed prijelaza za tehniku ​​postorder je lijevi-> desni-> korijen.

Ako je n korijenski čvor, a 'l' i 'r' lijevi i desni čvor stabla, tada su algoritmi za prelazak stabla sljedeći:

Redoslijed (lnr) algoritam:

  1. Pređite lijevo podstablo pomoću inOrder (lijevo - Podstablo).
  2. Posjetite korijenski čvor (n).
  3. Pređite desno poddrvo pomoću inOrder (desno poddrevo).

Algoritam prednarudžbe (nlr):

  1. Posjetite korijenski čvor (n).
  2. Prijeđite lijevim podstablom pomoću predbilježbe (lijevo poddrevo).
  3. Pređite desno poddrvo pomoću predbilježbe (desno poddrvo).

Algoritam postorder (lrn):

  1. Pređite lijevo podstablo pomoću postOrder (lijevo poddrevo).
  2. Pređite desno poddrvo pomoću postOrder (desno poddrvo).
  3. Posjetite korijenski čvor (n).

Iz gornjih algoritama tehnika prelaska vidimo da se tehnike mogu primijeniti na određeno stablo rekurzivno kako bi se dobio željeni rezultat.

Uzmite u obzir sljedeće stablo.

Algoritam postorder (lrn)

Koristeći gornje tehnike prelamanja, slijed prelaska za gornje stablo dan je u nastavku:

  1. Prijelaz InOrder: 2 3 5 6 10
  2. Prijelaz PreOrder: 6 3 2 5 10
  3. PostOrder prijelaz: 2 5 3 10 6

Zaključak

Stabla su nelinearna hijerarhijska struktura podataka koja se koristi u mnogim aplikacijama na polju softvera.

Za razliku od linearnih struktura podataka koje imaju samo jedan način za prelazak popisa, drveće možemo prelaziti na razne načine. U ovom smo tutorijalu detaljno proučili tehnike prelaska i raznih vrsta drveća.

=> Ovdje pogledajte vodič za početnike C ++

Preporučena literatura

^