Meny

Datastruktur for binært tre i C ++

binary tree data structure c

Prøv Instrumentet Vårt For Å Eliminere Problemer

Denne grundige opplæringen om binært tre i C ++ forklarer typer, representasjon, gjennomgang, applikasjoner og implementering av binære trær i C ++:

Et binært tre er en mye brukt datadatastruktur. Når hver node i et tre har høyst to barneknuter, kalles treet et binært tre.

Så et typisk binært tre vil ha følgende komponenter:

  • Et venstre undertreet
  • En rotnode
  • Et riktig undertre

=> Se opp den komplette listen over C ++ opplæringsprogrammer i denne serien.

Binært tre i C ++

Hva du vil lære:

Binært tre i C ++

En billedlig fremstilling av et binært tre er vist nedenfor:

Bildemessig fremstilling av et binært tre

I et gitt binært tre er det maksimale antall noder på ethvert nivå 2l-1der ‘l’ er nivånummeret.

Dermed i tilfelle av rotnoden på nivå 1, er det maksimale antallet noder = 21-1= 20= 1

Ettersom hver node i et binært tre maksimalt har to noder, vil maksimale noder på neste nivå være 2 * 2l-1.

sirkulær koblet liste i c ++

Gitt et binært tre med dybde eller høyde på h, er det maksimale antall noder i et binært tre med høyde h = 2h- 1.

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

La oss nå diskutere de forskjellige typer binære trær.

Typer av binært tre

Følgende er de vanligste typene binære trær.

# 1) Fullt binært tre

Et binært tre der hver node har 0 eller 2 barn, betegnes som et fullstendig binært tre.

Fullt binært tre

Ovenfor er vist et fullstendig binært tre der vi kan se at alle nodene bortsett fra bladnodene har to barn. Hvis L er antall bladnoder og ‘l’ er antallet interne eller ikke-bladnoder, så for et fullstendig binært tre, L = l + 1.

# 2) Komplett binært tre

Et komplett binært tre har alle nivåene fylt bortsett fra det siste nivået, og det siste nivået har alle nodene like mye som til venstre.

Komplett binært tre

Treet vist ovenfor er et komplett binært tre. Et typisk eksempel på et komplett binært tre er en binær bunke som vi vil diskutere i de senere opplæringene.

# 3) Perfekt binært tre

Et binært tre blir betegnet som perfekt når alle dets interne noder har to barn, og alle bladnoder er på samme nivå.

Perfekt binært tre

Et eksempel på et binært tre vist ovenfor er et perfekt binært tre, da hver av nodene har to barn, og alle bladnodene er på samme nivå.

Et perfekt binært tre i høyden h har 2h- 1 antall noder.

# 4) Et utartet tre

Et binært tre der hver intern node bare har ett barn kalles et degenerert tre.

Et utartet tre

Treet vist ovenfor er et degenerert tre. Når det gjelder ytelsen til dette treet, er degenererte trærne de samme som koblede lister.

# 5) Balansert binært tre

Et binært tre der dybden av de to undertrærne til hver node aldri avviker mer enn 1, kalles et balansert binært tre.

Balansert binært tre

Det binære treet vist ovenfor er et balansert binært tre, da dybden til de to undertrærne til hver node ikke er mer enn 1. AVL-trær som vi skal diskutere i de påfølgende opplæringene våre, er et vanlig balansert tre.

Representasjon av binært tre

Et binært tre tildeles minne på to måter.

# 1) Sekvensiell representasjon

Dette er den enkleste teknikken for å lagre en tredatastruktur. En matrise brukes til å lagre treknutene. Antall noder i et tre definerer størrelsen på matrisen. Rotnoden til treet lagres ved den første indeksen i matrisen.

Generelt, hvis en node er lagret på ithplassering så er det venstre og høyre barn lagres på henholdsvis 2i og 2i + 1 sted.

Tenk på følgende binære tre.

Eksempel på binært tre

Den sekvensielle representasjonen av det ovennevnte binære treet er som følger:

hva er den beste e-postmeldingen å bruke

sekvensiell representasjon av binært tre

I den ovennevnte representasjonen ser vi at venstre og høyre barn til hver node er lagret på henholdsvis plasseringene 2 * (node_location) og 2 * (node_location) +1.

For eksempel, plasseringen av node 3 i matrisen er 3. Så det venstre barnet vil bli plassert på 2 * 3 = 6. Det høyre barnet vil være på stedet 2 * 3 +1 = 7. Som vi kan se i matrisen, barn av 3 som er 6 og 7 er plassert på plassering 6 og 7 i matrisen.

Den sekvensielle representasjonen av treet er ineffektiv, da matrisen som brukes til å lagre treknutene tar mye plass i minnet. Når treet vokser, blir denne representasjonen ineffektiv og vanskelig å håndtere.

Denne ulempen løses ved å lagre treknutepunktene i en koblet liste. Merk at hvis treet er tomt, blir den første plasseringen som lagrer rotnoden satt til 0.

# 2) Representasjon for koblet liste

I denne typen representasjon brukes en koblet liste til å lagre treknutene. Flere noder er spredt i minnet på ikke-sammenhengende steder, og nodene er koblet sammen med foreldre-barn-forholdet som et tre.

Følgende diagram viser en lenket representasjon for et tre.

Link-list representasjon

Som vist i representasjonen ovenfor, har hver koblet listenode tre komponenter:

  • Venstre peker
  • Datadel
  • Høyre peker

Den venstre pekeren har en peker mot venstre barn av noden; den høyre pekeren har en peker til det høyre barnet til noden, mens datadelen inneholder de faktiske dataene til noden. Hvis det ikke er barn for en gitt node (bladnode), blir venstre og høyre peker for den noden satt til null som vist i figuren ovenfor.

Implementering av binært tre i C ++

Deretter utvikler vi et binært treprogram ved hjelp av en lenket representasjon i C ++. Vi bruker en struktur for å erklære en enkelt node, og deretter bruker vi en klasse, og vi utvikler en koblet liste over noder.

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

Produksjon:

Binært tre opprettet:

5 10 15 20 30 40 45

Binary Tree Traversal

Vi har allerede diskutert traversaler i vår grunnleggende opplæring om trær. La oss i denne delen implementere et program som setter inn noder i det binære treet, og som også viser alle de tre gjennomgangene, dvs. bestilling, forhåndsbestilling og etterbestilling, for et binært tre.

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

Produksjon:

Inorder traversal:

A B C D E F G

Gjennomgang av postordre:

G F E D C B A

Forhåndsbestill traversal:

A B C D E F G

Anvendelser av binært tre

Et binært tre brukes i mange applikasjoner for lagring av data.

Noen av de viktige anvendelsene av binære trær er listet opp nedenfor:

  • Binære søketrær: Binære trær brukes til å konstruere et binært søketre som brukes i mange søkeapplikasjoner som sett og kart i mange språkbiblioteker.
  • Hash trær: Brukes til å verifisere hashes hovedsakelig i spesialiserte applikasjoner for bildesignatur.
  • Dynger: Heaps brukes til å implementere prioritetskøer som brukes til rutere, planlegge prosessorer i operativsystemet, etc.
  • Huffman-koding: Huffman-kodingstreet brukes i komprimeringsalgoritmer (som bildekomprimering) så vel som kryptografiske applikasjoner.
  • Syntaks tre: Kompilatorer konstruerer ofte syntaksetrær som ikke er annet enn binære trær for å analysere uttrykk som brukes i programmet.

Konklusjon

Binære trær er mye brukt datastrukturer i programvareindustrien. Binære trær er trærne med noder som maksimalt har to barnnoder. Vi har sett forskjellige typer binære trær som et fullt binært tre, et komplett binært tre, et perfekt binært tre, et degenerert binært tre, et balansert binært tre, etc.

Binære tre-data kan også krysses ved hjelp av bestillingsteknikker, forhåndsbestilling og etterbestillingsteknikker som vi har sett i vår forrige opplæring. I minnet kan et binært tre representeres ved hjelp av en koblet liste (ikke sammenhengende minne) eller matriser (sekvensiell representasjon).

Tilknyttet listerepresentasjon er mer effektiv sammenlignet med matriser, da matriser tar mye plass.

=> Sjekk ut de beste C ++ opplæringsveiledningene her.

Anbefalt lesing

^