Meni

Drevesa v jeziku C ++: osnovna terminologija, tehnike prečkanja in drevesne vrste C ++

  • Glavni
  • Drugo
  • Drevesa v jeziku C ++: osnovna terminologija, tehnike prečkanja in drevesne vrste C ++

trees c basic terminology

Preizkusite Naš Instrument Za Odpravo Težav

Ta poglobljena vadnica o drevesih C ++ s slikami in primeri programov razlaga vrste dreves, tehnike prečkanja dreves in osnovno terminologijo:

V tej seriji C ++ smo do zdaj videli linearno strukturo podatkov tako statične kot dinamične narave. Zdaj bomo nadaljevali z nelinearno strukturo podatkov. Prva struktura podatkov v tej kategoriji je 'Drevesa'.

java ustvari vrsto predmetov

Drevesa so nelinearne hierarhične podatkovne strukture. Drevo je zbirka vozlišč, povezanih med seboj s pomočjo 'robov', ki so usmerjeni ali neusmerjeni. Eno od vozlišč je označeno kot »Root vozlišče«, preostala vozlišča pa se imenujejo podrejena vozlišča ali listna vozlišča korenskega vozlišča.

Na splošno ima lahko vsako vozlišče toliko otrok, vendar le eno nadrejeno vozlišče.

=> Oglejte si celotno serijo usposabljanj za C ++

Drevo v jeziku C ++

Vozlišča drevesa se na isti ravni imenujejo sestrska vozlišča ali pa imajo odnos roditelj-otrok. Vozlišča z istim nadrejenim so sorodniška vozlišča.

Kaj se boste naučili:

Drevesa v jeziku C ++

Spodaj je primer drevesa z različnimi deli.

Drevo v jeziku C ++ z različnimi deli

Pojdimo skozi definicije nekaterih osnovnih izrazov, ki jih uporabljamo za drevesa.

  • Koreninsko vozlišče: To je najvišje vozlišče v drevesni hierarhiji. V zgornjem diagramu je vozlišče A korensko vozlišče. Upoštevajte, da korensko vozlišče nima nobenega nadrejenega.
  • Listno vozlišče: Je najnižje vozlišče v drevesni hierarhiji. Listna vozlišča so vozlišča, ki nimajo podrejenih vozlišč. Znani so tudi kot zunanja vozlišča. Vozlišča E, F, G, H in C v zgornjem drevesu so vsa vozlišča listov.
  • Poddrevo: Poddrevo predstavlja različne potomce vozlišča, ko koren ni nič. Drevo je ponavadi sestavljeno iz korenskega vozlišča in enega ali več poddreves. V zgornjem diagramu sta (B-E, B-F) in (D-G, D-H) poddrevesa.
  • Nadrejeno vozlišče: Katero koli vozlišče, razen korenskega vozlišča, ki ima podrejeno vozlišče in rob navzgor proti staršu.
  • Vozlišče prednikov: To je katero koli predhodno vozlišče na poti od korena do tega vozlišča. Upoštevajte, da koren nima prednikov. V zgornjem diagramu sta A in B prednika E.
  • Ključ: Predstavlja vrednost vozlišča.
  • Raven: Predstavlja generiranje vozlišča. Koreninsko vozlišče je vedno na nivoju 1. Podrejena vozlišča korena so na nivoju 2, vnuki korena so na nivoju 3 itd. Na splošno je vsako vozlišče na višji ravni od nadrejenega.
  • Pot: Pot je zaporedje zaporednih robov. V zgornjem diagramu je pot do E A => B-> E.
  • Stopnja: Stopnja vozlišča označuje število podrejenih vozlišč. V zgornjem diagramu je stopnja B in D po 2, stopnja C pa 0.

Vrste dreves C ++

Drevesno strukturo podatkov lahko razvrstimo v naslednje podvrste, kot je prikazano na spodnjem diagramu.

Vrste dreves v jeziku C ++

# 1) Splošno drevo

Splošno drevo je osnovna predstavitev drevesa. Ima vozlišče in eno ali več podrejenih vozlišč. Vozlišče najvišje ravni, tj. Korensko vozlišče, je prisotno na ravni 1, vsa ostala vozlišča pa so lahko prisotna na različnih ravneh.

Splošno drevo je prikazano na spodnji sliki.

Splošno drevo

Kot je prikazano na zgornji sliki, lahko splošno drevo vsebuje poljubno število pod dreves. Vozlišča B, C in D so prisotna na ravni 2 in so vozlišča sorojencev. Podobno so vozlišča E, F, G in H tudi vozlišča.

Vozlišča, prisotna na različnih ravneh, lahko kažejo odnos med starši in otroki. Na zgornji sliki so vozlišča B, C in D podrejena A. Vozlišča E in F so podrejena B, medtem ko sta vozli G in H otroci D.

Splošno drevo je prikazano spodaj z uporabo izvedbe 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; }

Izhod:

Splošno ustvarjeno drevo je naslednje:

10.

/

20. 30

/

40

# 2) Gozdovi

Vsakič, ko iz drevesa izbrišemo koreninsko vozlišče in robove, ki povezujejo elemente naslednje ravni in koren, dobimo ločene nize dreves, kot je prikazano spodaj.

Gozdovi

Na zgornji sliki smo z brisanjem koreninskega vozlišča A in treh robov, ki so koreninsko vozlišče povezovali z vozlišči B, C in D, dobili dva gozda.

# 3) Binarno drevo

Drevesna podatkovna struktura, v kateri ima vsako vozlišče največ dve podrejeni vozlišči, se imenuje binarno drevo. Binarno drevo je najbolj priljubljena drevesna podatkovna struktura in se uporablja v številnih aplikacijah, kot so ocenjevanje izrazov, zbirke podatkov itd.

Naslednja slika prikazuje binarno drevo.

Binarno drevo

Na zgornji sliki vidimo, da imajo vozlišča A, B in D po dva otroka. Binarno drevo, v katerem ima vsako vozlišče točno nič ali dva otroka, se imenuje polno binarno drevo. V tem drevesu ni vozlišč z enim otrokom.

Popolno binarno drevo ima binarno drevo, ki je popolnoma zapolnjeno, z izjemo najnižje ravni, ki je zapolnjena od leve proti desni. Zgoraj prikazano binarno drevo je polno binarno drevo.

Sledi preprost program za prikaz binarnega drevesa. Upoštevajte, da je izhod drevesa zaporedno zaporedje vhodnega drevesa.

#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

# 4) Binarno drevo iskanja

Urejeno binarno drevo se imenuje binarno drevo iskanja. V binarnem drevesu iskanja so vozlišča levo manjša od korenskega vozlišča, medtem ko so vozlišča desno večja ali enaka korenskemu vozlišču.

Primer drevesa binarnega iskanja je prikazan spodaj.

Binarno drevo iskanja

Na zgornji sliki lahko vidimo, da so leva vozlišča manjša od 20, kar je korenski element. Prava vozlišča pa so večja od korenskega vozlišča. Binarno drevo iskanja se uporablja pri tehnikah iskanja in razvrščanja.

# 5) Drevo izraza

Binarno drevo, ki se uporablja za ocenjevanje preprostih aritmetičnih izrazov, se imenuje drevo izrazov.

Preprosto drevo izrazov je prikazano spodaj.

Drevo izrazov

V zgornjem vzorčnem drevesu izrazov predstavljamo izraz (a + b) / (a-b). Kot je prikazano na zgornji sliki, nelistna vozlišča drevesa predstavljajo operaterje izraza, medtem ko listna vozlišča predstavljajo operande.

Drevesa izrazov se v glavnem uporabljajo za reševanje algebrskih izrazov.

Tehnike prečkanja dreves

Videli smo linearne podatkovne strukture, kot so nizi, povezani seznami, skladi, čakalne vrste itd. Vse te podatkovne strukture imajo skupno tehniko prečkanja, ki strukturo prečka samo na en način, tj. Linearno.

Toda pri drevesih imamo različne tehnike prečkanja, kot so navedene spodaj:

# 1) Da: Pri tej tehniki prečkanja najprej prehodimo levo poddrevo, dokler v levem poddrevju ni več vozlišč. Po tem obiščemo korensko vozlišče in nato nadaljujemo s prečkanjem desnega poddrevesa, dokler v desnem poddrevesu ni več vozlišč. Tako je vrstni red prehajanja inOrder levo-> koren-> desno.

# 2) Prednaročilo: Za tehniko preusmeritve prednaročila najprej obdelamo koreninsko vozlišče, nato prehodimo celotno levo poddrevo in na koncu še desno poddrevo. Zato je vrstni red prenosa prednaročil koren-> levo-> desno.

# 3) Po naročilu: V tehniki preusmeritve po naročilu prehodimo levo poddrevo, nato desno poddrevo in na koncu korensko vozlišče. Vrstni red prehoda za tehniko postorder je levi-> desni-> koren.

Če je n korensko vozlišče, 'l' in 'r' pa levo in desno vozlišče drevesa, so algoritmi za prehod drevesa naslednji:

Da bi algoritem (lnr):

  1. Premaknite levo poddrevo z uporabo inOrder (levo - Poddrevo).
  2. Obiščite korensko vozlišče (n).
  3. Premikajte desno poddrevo z uporabo inOrder (desno poddrevo).

Algoritem prednaročila (nlr):

  1. Obiščite korensko vozlišče (n).
  2. Premaknite levo poddrevo z uporabo prednaročila (levo poddrevo).
  3. Prehodite desno poddrevo z uporabo prednaročila (desno poddrevo).

Algoritem po naročilu (lrn):

  1. Premaknite levo poddrevo s pomočjo postOrder (levo poddrevo).
  2. Prehodite desno poddrevo s pomočjo postOrder (desno poddrevo).
  3. Obiščite korensko vozlišče (n).

Iz zgornjih algoritmov prehodnih tehnik vidimo, da jih je mogoče na dano drevo rekurzivno uporabiti, da dobimo želeni rezultat.

Razmislite o naslednjem drevesu.

Algoritem postorder (lrn)

Z uporabo zgornjih tehnik prečkanja je spodnje zaporedje prehodov za zgornje drevo:

  1. Prehod InOrder: 2 3 5 6 10
  2. Prehod po naročilu: 6 3 2 5 10
  3. Prehod PostOrder: 2 5 3 10 6

Zaključek

Drevesa so nelinearna hierarhična podatkovna struktura, ki se uporablja v številnih aplikacijah na področju programske opreme.

Za razliko od linearnih podatkovnih struktur, ki imajo samo en način za prehod po seznamu, lahko drevesa prehodimo na različne načine. V tej vadnici smo podrobno preučili tehnike prečkanja in različne vrste dreves.

=> Tukaj si oglejte vodnik za začetnike C ++

Priporočeno branje

^