binary tree data structure c
Denna djupgående handledning om binärt träd i C ++ förklarar typer, representation, genomgång, applikationer och implementering av binära träd i C ++:
Ett binärt träd är en allmänt använd trädatastruktur. När varje nod i ett träd har högst två barnnoder kallas trädet ett binärt träd.
Så ett typiskt binärt träd kommer att ha följande komponenter:
- Ett vänster underträd
- En rotnod
- En rätt subtree
=> Se upp den fullständiga listan över C ++ -handledning i denna serie.
Vad du kommer att lära dig:
- Binärt träd i C ++
- Typer av binärt träd
- Binär trädrepresentation
- Implementering av binärt träd i C ++
- Binary Tree Traversal
- Tillämpningar av binärt träd
- Slutsats
- Rekommenderad läsning
Binärt träd i C ++
En bildrepresentation av ett binärt träd visas nedan:
I ett givet binärt träd är det maximala antalet noder på vilken nivå som helst 2l-1där 'l' är nivånumret.
Således när det gäller rotnoden på nivå 1 är det maximala antalet noder = 21-1= 20= 1
Eftersom varje nod i ett binärt träd har högst två noder, blir maximala noder på nästa nivå 2 * 2l-1.
testfas för livscykelutveckling av programvara
Med tanke på ett binärt träd med djup eller höjd på h är det maximala antalet noder i ett binärt träd med höjd h = 2h- 1.
Följaktligen i ett binärt träd med höjd 3 (visas ovan) är det maximala antalet noder = 23-1 = 7.
Låt oss nu diskutera de olika typerna av binära träd.
Typer av binärt träd
Följande är de vanligaste typerna av binära träd.
# 1) Fullt binärt träd
Ett binärt träd där varje nod har 0 eller 2 barn kallas ett fullständigt binärt träd.
Ovan visas ett fullständigt binärt träd där vi kan se att alla dess noder utom bladnoder har två barn. Om L är antalet bladnoder och 'l' är antalet interna eller icke-bladnoder, så för ett fullständigt binärt träd, L = l + 1.
# 2) Komplett binärt träd
Ett komplett binärt träd har alla nivåer fyllda förutom den sista nivån och den sista nivån har alla sina noder lika mycket som till vänster.
Trädet som visas ovan är ett komplett binärt träd. Ett typiskt exempel på ett komplett binärt träd är en binär hög som vi kommer att diskutera i de senare självstudierna.
# 3) Perfekt binärt träd
Ett binärt träd kallas perfekt när alla dess inre noder har två barn och alla bladnoder är på samma nivå.
Ett exempel på binärt träd som visas ovan är ett perfekt binärt träd eftersom var och en av dess noder har två barn och alla bladnoder är på samma nivå.
Ett perfekt binärt träd med höjd h har 2h- 1 antal noder.
# 4) Ett degenererat träd
Ett binärt träd där varje intern nod bara har ett barn kallas ett degenererat träd.
Trädet som visas ovan är ett degenererat träd. När det gäller prestationen för detta träd är degenererade träden desamma som länkade listor.
# 5) Balanserat binärt träd
Ett binärt träd där djupet av de två undertråden i varje nod aldrig skiljer sig mer än 1 kallas ett balanserat binärt träd.
Det binära trädet som visas ovan är ett balanserat binärt träd, eftersom djupet på de två undertråden i varje nod inte är mer än 1. AVL-träd som vi ska diskutera i våra efterföljande handledning är ett vanligt balanserat träd.
Binär trädrepresentation
Ett binärt träd tilldelas minne på två sätt.
# 1) Sekventiell representation
Detta är den enklaste tekniken för att lagra en träddatastruktur. En matris används för att lagra trädnoderna. Antalet noder i ett träd definierar storleken på matrisen. Trädets rotnod lagras vid det första indexet i matrisen.
I allmänhet, om en nod lagras vid ithplats så är det vänster och höger barn lagras på 2i respektive 2i + 1 plats.
Tänk på följande binära träd.
Den sekventiella representationen av ovanstående binära träd är som följer:
I ovanstående representation ser vi att vänster och höger barn i varje nod lagras på platserna 2 * (nodlokalisering) respektive 2 * (nodlokalisering) +1.
Till exempel, platsen för nod 3 i matrisen är 3. Så det är kvar barnet kommer att placeras på 2 * 3 = 6. Dess högra barn kommer att vara på platsen 2 * 3 +1 = 7. Som vi kan se i matrisen, barn av 3 som är 6 och 7 placeras på plats 6 och 7 i matrisen.
Den sekventiella representationen av trädet är ineffektiv eftersom arrayen som används för att lagra trädnoderna tar mycket utrymme i minnet. När trädet växer blir denna framställning ineffektiv och svår att hantera.
Denna nackdel övervinns genom att lagra trädnoderna i en länkad lista. Observera att om trädet är tomt, kommer den första platsen som lagrar rotnoden att vara 0.
# 2) Representation för länkad lista
I denna typ av representation används en länkad lista för att lagra trädnoderna. Flera noder är utspridda i minnet på icke-angränsande platser och noderna är anslutna med hjälp av föräldra-barn-relationen som ett träd.
vad är nätverkssäkerhetsnyckeln för trådlöst
Följande diagram visar en länkad representation för ett träd.
Som visas i ovanstående representation har varje länkad listnod tre komponenter:
- Vänster pekare
- Datadel
- Höger pekare
Den vänstra pekaren har en pekare till nodens vänstra barn; den högra pekaren har en pekare till nodens högra barn medan datadelen innehåller nodens faktiska data. Om det inte finns några barn för en viss nod (bladnod), är vänster och höger pekare för den noden inställd på noll som visas i figuren ovan.
Implementering av binärt träd i C ++
Därefter utvecklar vi ett binärt trädprogram med en länkad representation i C ++. Vi använder en struktur för att deklarera en enda nod och sedan använder vi en klass, vi utvecklar en länkad lista med 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: '< Produktion:
Binärt träd skapat:
5 10 15 20 30 40 45
Binary Tree Traversal
Vi har redan diskuterat traversaler i vår grundläggande handledning om träd. I det här avsnittet, låt oss implementera ett program som infogar noder i det binära trädet och visar också alla de tre genomgångarna, dvs inorder, förbeställning och efterbeställning, för ett binärt träd.
#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
Postorder traversal:
G F E D C B A
Förbeställ traversal:
A B C D E F G
Tillämpningar av binärt träd
Ett binärt träd används i många applikationer för lagring av data.
Några av de viktiga tillämpningarna av binära träd listas nedan:
- Binära sökträd: Binära träd används för att konstruera ett binärt sökträd som används i många sökapplikationer som uppsättningar och kartor i många språkbibliotek.
- Hashträd: Används för att verifiera hashes främst i specialiserade bildsignaturapplikationer.
- Högar: Heaps används för att implementera prioritetsköer som används för routrar, schemaläggning av processorer i operativsystemet etc.
- Huffman-kodning: Huffman-kodningsträd används i kompressionsalgoritmer (som bildkomprimering) såväl som kryptografiska applikationer.
- Syntaxträd: Kompilatorer konstruerar ofta syntaxträd som bara är binära träd för att analysera uttryck som används i programmet.
Slutsats
Binära träd används ofta i datastrukturer i programvaruindustrin. Binära träd är de träd vars noder har högst två barnnoder. Vi har sett olika typer av binära träd som ett fullständigt binärt träd, ett komplett binärt träd, ett perfekt binärt träd, ett degenererat binärt träd, ett balanserat binärt träd etc.
Binära träddata kan också spåras med hjälp av inorder, preorder och postorder traversal tekniker som vi har sett i vår tidigare handledning. I minnet kan ett binärt träd representeras med hjälp av en länkad lista (icke sammanhängande minne) eller matriser (sekventiell representation).
Länkad listrepresentation är effektivare jämfört med matriser, eftersom matriser tar mycket utrymme.
=> Kolla in de bästa C ++ träningsövningarna här.
Rekommenderad läsning
- AVL-träd- och högdatastruktur i C ++
- B-träd och B + träddatastruktur i C ++
- Kodatastruktur i C ++ med illustration
- Stack datastruktur i C ++ med illustration
- Cirkulär länkad datastruktur i C ++ med illustration
- Länkad listdatastruktur i C ++ med illustration
- Introduktion till datastrukturer i C ++
- Prioriterad köstruktur i C ++ med illustration