Menu

Datastruktur for binært træ i C ++

binary tree data structure c

Prøv Vores Instrument Til At Fjerne Problemer

Denne dybdegående vejledning om binært træ i C ++ forklarer typer, repræsentation, gennemkørsel, applikationer og implementering af binære træer i C ++:

Et binært træ er en meget anvendt treddatastruktur. Når hvert knudepunkt på et træ højst har to underknudepunkter, kaldes træet et binært træ.

Så et typisk binært træ har følgende komponenter:

  • Et venstre undertræ
  • En rodknude
  • Et rigtigt undertræ

=> Hold øje med den komplette liste over C ++ tutorials i denne serie.

Binært træ i C ++

Hvad du vil lære:

Binært træ i C ++

En billedlig gengivelse af et binært træ er vist nedenfor:

Billedskildring af et binært træ

I et givet binært træ er det maksimale antal noder på ethvert niveau 2l-1hvor 'l' er niveauet nummer.

Således i tilfælde af rodnoden på niveau 1 er det maksimale antal noder = 21-1= 20= 1

Da hver node i et binært træ højst har to noder, vil de maksimale noder på det næste niveau være 2 * 2l-1.

udvælgelse sortere c ++ kode eksempel

Givet et binært træ med dybde eller højde på h, er det maksimale antal noder i et binært træ med højde h = 2h- 1.

Derfor er det maksimale antal noder i et binært træ med højde 3 (vist ovenfor) = 23-1 = 7.

Lad os nu diskutere de forskellige typer binære træer.

Typer af binært træ

Følgende er de mest almindelige typer binære træer.

# 1) Fuldt binært træ

Et binært træ, hvor hver node har 0 eller 2 børn, betegnes som et fuldt binært træ.

Fuldt binært træ

Ovenfor er vist et fuldt binært træ, hvor vi kan se, at alle dets knuder undtagen bladknuderne har to børn. Hvis L er antallet af bladknuder, og 'l' er antallet af interne eller ikke-bladknuder, så for et fuldt binært træ, L = l + 1.

# 2) Komplet binært træ

Et komplet binært træ har alle niveauer fyldt undtagen det sidste niveau, og det sidste niveau har alle dets noder lige så meget som til venstre.

Komplet binært træ

Træet vist ovenfor er et komplet binært træ. Et typisk eksempel på et komplet binært træ er en binær bunke, som vi vil diskutere i de senere tutorials.

# 3) Perfekt binært træ

Et binært træ kaldes perfekt, når alle dets interne noder har to børn, og alle bladnoder er på samme niveau.

Perfekt binært træ

Et eksempel på et binært træ vist ovenfor er et perfekt binært træ, da hver af dets noder har to børn, og alle bladnoder er på samme niveau.

Et perfekt binært træ i højden h har 2h- 1 antal noder.

# 4) Et degenereret træ

Et binært træ, hvor hver intern node kun har et barn, kaldes et degenereret træ.

Et degenereret træ

Træet vist ovenfor er et degenereret træ. For så vidt angår udførelsen af ​​dette træ er degenererede træer de samme som sammenkædede lister.

# 5) Balanceret binært træ

Et binært træ, hvor dybden af ​​de to undertræer i hver node aldrig adskiller sig med mere end 1 kaldes et afbalanceret binært træ.

Balanceret binært træ

Det binære træ vist ovenfor er et afbalanceret binært træ, da dybden af ​​de to undertræer i hver node ikke er mere end 1. AVL-træer, som vi skal diskutere i vores efterfølgende tutorials, er et almindeligt afbalanceret træ.

Binær trærepræsentation

Et binært træ tildeles hukommelse på to måder.

# 1) Sekventiel repræsentation

Dette er den enkleste teknik til at gemme en træstatastruktur. En matrix bruges til at gemme træknudepunkterne. Antallet af noder i et træ definerer størrelsen på arrayet. Træets rodknude er gemt ved det første indeks i matrixen.

Generelt, hvis en node er gemt på ithplacering, så er det venstre og højre barn er gemt på henholdsvis 2i og 2i + 1 placering.

Overvej følgende binære træ.

Prøve på binært træ

Den sekventielle gengivelse af ovenstående binære træ er som følger:

sekventiel repræsentation af binært træ

I ovenstående repræsentation ser vi, at venstre og højre barn i hver node er gemt på henholdsvis placering 2 * (node-placering) og 2 * (node-placering) +1.

For eksempel, placeringen af ​​knudepunkt 3 i arrayet er 3. Så det venstre barn placeres på 2 * 3 = 6. Dets højre barn vil være på stedet 2 * 3 +1 = 7. Som vi kan se i arrayet, børn af 3, der er 6 og 7 er placeret på placering 6 og 7 i arrayet.

Den sekventielle repræsentation af træet er ineffektiv, da det array, der bruges til at gemme træknudepunkterne, tager meget plads i hukommelsen. Når træet vokser, bliver denne repræsentation ineffektiv og vanskelig at styre.

Denne ulempe overvindes ved at gemme træknudepunkterne på en sammenkædet liste. Bemærk, at hvis træet er tomt, vil den første placering, der gemmer rodnoden, blive indstillet til 0.

# 2) Repræsentation med tilknyttet liste

I denne type repræsentation bruges en sammenkædet liste til at gemme træknudepunkterne. Flere noder er spredt i hukommelsen på ikke-sammenhængende steder, og noder er forbundet ved hjælp af forældre-barn-forholdet som et træ.

Følgende diagram viser en sammenkædet listerepræsentation for et træ.

Link-liste repræsentation

Som vist i ovenstående repræsentation har hver sammenkædet listeknude tre komponenter:

  • Venstre markør
  • Datadel
  • Højre markør

Den venstre markør har en markør til knudens venstre barn; den højre markør har en markør til knudens højre underordnede, mens datadelen indeholder nodens faktiske data. Hvis der ikke er nogen børn til en given node (bladnode), er venstre og højre markør for den node indstillet til null som vist i ovenstående figur.

Implementering af binært træ i C ++

Dernæst udvikler vi et binært træprogram ved hjælp af en sammenkædet listerepræsentation i C ++. Vi bruger en struktur til at erklære en enkelt knude og derefter udvikler vi en sammenkædet liste over noder ved hjælp af en klasse.

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

Produktion:

Binært træ oprettet:

5 10 15 20 30 40 45

Binary Tree Traversal

Vi har allerede diskuteret gennemgange i vores grundlæggende vejledning om træer. Lad os i dette afsnit implementere et program, der indsætter noder i det binære træ og også demonstrerer alle de tre gennemgange, dvs. ordre, forudbestilling og efterbestilling til et binært træ.

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

Produktion:

Inorder traversal:

A B C D E F G

Gennemgang af postordre:

G F E D C B A

Forudbestil traversal:

A B C D E F G

Anvendelser af binært træ

Et binært træ bruges i mange applikationer til lagring af data.

Nogle af de vigtige anvendelser af binære træer er anført nedenfor:

java j2ee interview spørgsmål og svar til erfarne
  • Binære søgetræer: Binære træer bruges til at konstruere et binært søgetræ, der bruges i mange søgeapplikationer som sæt og kort i mange sprogbiblioteker.
  • Hash træer: Bruges til at kontrollere hashes hovedsageligt i specialiserede billedsignaturapplikationer.
  • Dynger: Heaps bruges til at implementere prioritetskøer, der bruges til routere, planlægning af processorer i operativsystemet osv.
  • Huffman-kodning: Huffman-kodningstræ bruges i komprimeringsalgoritmer (som billedkomprimering) såvel som kryptografiske applikationer.
  • Syntaks træ: Kompilatorer konstruerer ofte syntaks træer, der kun er binære træer til at analysere udtryk, der bruges i programmet.

Konklusion

Binære træer er meget anvendte datastrukturer på tværs af softwareindustrien. Binære træer er de træer, hvis knuder højst har to barneknuder. Vi har set forskellige typer binære træer som et fuldt binært træ, et komplet binært træ, et perfekt binært træ, et degenereret binært træ, et afbalanceret binært træ osv.

Binære trædata kan også krydses ved hjælp af inorder, preorder og postorder traversal teknikker, som vi har set i vores tidligere tutorial. I hukommelsen kan et binært træ repræsenteres ved hjælp af en sammenkædet liste (ikke sammenhængende hukommelse) eller arrays (sekventiel repræsentation).

Tilknyttet listerepræsentation er mere effektiv sammenlignet med arrays, da arrays optager meget plads.

=> Tjek de bedste C ++ træningsvejledninger her.

Anbefalet læsning

^