binary tree data structure c
Aquest tutorial en profunditat sobre l'arbre binari en C ++ explica els tipus, la representació, la transversalitat, les aplicacions i la implementació d'arbres binaris en C ++:
Un arbre binari és una estructura de dades d'arbre àmpliament utilitzada. Quan cada node d'un arbre té com a màxim dos nodes fills, l'arbre s'anomena arbre binari.
Per tant, un arbre binari típic tindrà els components següents:
- Un subarbre esquerre
- Un node arrel
- Un subarbre dret
=> Mireu la llista completa de tutorials C ++ d’aquesta sèrie.
Què aprendreu:
- Arbre binari en C ++
- Tipus d’arbre binari
- Representació d'arbres binaris
- Implementació de l'arbre binari en C ++
- Traversal d'arbres binaris
- Aplicacions de l'arbre binari
- Conclusió
- Lectura recomanada
Arbre binari en C ++
A continuació es mostra una representació pictòrica d’un arbre binari:
En un arbre binari determinat, el nombre màxim de nodes a qualsevol nivell és de 2l-1on ‘l’ és el número de nivell.
Així, en el cas del node arrel al nivell 1, el nombre màxim de nodes = 21-1= 20= 1
Com que cada node d'un arbre binari té com a màxim dos nodes, el màxim de nodes al següent nivell serà de 2 * 2l-1.
implementar l'arbre de cerca binària a Java
Donat un arbre binari de profunditat o alçada d’h, el nombre màxim de nodes d’un arbre binari d’alçada h = 2h- 1.
Per tant, en un arbre binari d’alçada 3 (mostrat més amunt), el nombre màxim de nodes = 23-1 = 7.
Ara anem a discutir els diversos tipus d'arbres binaris.
Tipus d’arbre binari
A continuació es detallen els tipus d’arbres binaris més habituals.
# 1) Arbre binari complet
Un arbre binari en què cada node té 0 o 2 fills es denomina arbre binari complet.
A la part superior es mostra un arbre binari complet en el qual podem veure que tots els seus nodes, excepte els nodes de fulla, tenen dos fills. Si L és el nombre de nodes de fulla i ‘l’ és el nombre de nodes interns o no, llavors per a un arbre binari complet, L = l + 1.
# 2) Arbre binari complet
Un arbre binari complet té tots els nivells omplerts, excepte l'últim nivell i l'últim nivell té tots els seus nodes tant com a l'esquerra.
L’arbre que es mostra més amunt és un arbre binari complet. Un exemple típic d'un arbre binari complet és un munt binari que parlarem en els tutorials posteriors.
# 3) Arbre binari perfecte
Un arbre binari es denomina perfecte quan tots els seus nodes interns tenen dos fills i tots els nodes de fulla estan al mateix nivell.
Un exemple d'arbre binari que es mostra més amunt és un arbre binari perfecte, ja que cadascun dels seus nodes té dos fills i tots els nodes de fulla estan al mateix nivell.
Un arbre binari perfecte d’alçada h té 2h- 1 nombre de nodes.
# 4) Un arbre degenerat
Un arbre binari on cada node intern només té un fill es diu arbre degenerat.
L’arbre que es mostra més amunt és un arbre degenerat. Pel que fa al rendiment d’aquest arbre, els arbres degenerats són els mateixos que les llistes enllaçades.
# 5) Arbre binari equilibrat
Un arbre binari en què la profunditat dels dos subarbres de cada node no difereix mai més d’1 s’anomena arbre binari equilibrat.
L’arbre binari que es mostra anteriorment és un arbre binari equilibrat, ja que la profunditat dels dos subarbres de cada node no és superior a 1. Els arbres AVL que tractarem en els nostres tutorials posteriors són un arbre equilibrat comú.
Representació d'arbres binaris
Un arbre binari té assignada memòria de dues maneres.
# 1) Representació seqüencial
Aquesta és la tècnica més senzilla per emmagatzemar una estructura de dades d’arbre. S’utilitza una matriu per emmagatzemar els nodes d’arbre. El nombre de nodes d'un arbre defineix la mida de la matriu. El node arrel de l'arbre s'emmagatzema al primer índex de la matriu.
Preguntes i respostes de l'entrevista sql per a estudiants de primer any
En general, si s’emmagatzema un node a l’ithla ubicació, llavors es troba a l'esquerra i a la dreta, s'emmagatzema a la ubicació 2i i 2i + 1 respectivament.
Penseu en el següent arbre binari.
La representació seqüencial de l'arbre binari anterior és la següent:
A la representació anterior, veiem que el fill esquerre i dret de cada node s’emmagatzema a les ubicacions 2 * (node_location) i 2 * (node_location) +1 respectivament.
Per exemple, la ubicació del node 3 a la matriu és 3. Per tant, el fill esquerre es col·locarà a 2 * 3 = 6. El fill dret estarà a la ubicació 2 * 3 +1 = 7. Com podem veure a la matriu, els nens de 3 que són 6 i 7 es col·loquen a la ubicació 6 i 7 de la matriu.
La representació seqüencial de l'arbre és ineficient ja que la matriu que s'utilitza per emmagatzemar els nodes d'arbre ocupa molt espai a la memòria. A mesura que l'arbre creix, aquesta representació es torna ineficient i difícil de manejar.
Aquest desavantatge es supera emmagatzemant els nodes d’arbre en una llista enllaçada. Tingueu en compte que si l'arbre està buit, la primera ubicació que emmagatzemi el node arrel s'establirà a 0.
# 2) Representació de llista enllaçada
En aquest tipus de representació, s’utilitza una llista enllaçada per emmagatzemar els nodes d’arbre. Hi ha diversos nodes dispersos a la memòria en ubicacions no contigües i els nodes es connecten utilitzant la relació pare-fill com un arbre.
El següent diagrama mostra una representació de llista enllaçada per a un arbre.
Com es mostra a la representació anterior, cada node de llista enllaçat té tres components:
- Punter esquerre
- Part de dades
- Punter dret
El punter esquerre té un punter cap al nen esquerre del node; el punter dret té un punter cap al nen secundari dret del node, mentre que la part de dades conté les dades reals del node. Si no hi ha fills per a un node determinat (node de fulla), els indicadors esquerre i dret d’aquest node s’estableixen a nuls tal com es mostra a la figura anterior.
Implementació de l'arbre binari en C ++
A continuació, desenvolupem un programa d'arbre binari mitjançant una representació de llista enllaçada en C ++. Utilitzem una estructura per declarar un sol node i, a continuació, mitjançant una classe, desenvolupem una llista enllaçada de nodes.
#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: '< Sortida:
Arbre binari creat:
5 10 15 20 30 40 45
Traversal d'arbres binaris
Ja hem parlat de les travesses al nostre tutorial bàsic sobre arbres. En aquesta secció, implementem un programa que insereix nodes a l’arbre binari i que també mostra els tres recorreguts, és a dir, inorder, preorden i postorder, per a un arbre binari.
#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:'< Sortida:
Recorregut per ordre:
A B C D E F G
Recorregut de comandes per correu:
G F E D C B A
Recorregut de la comanda prèvia:
A B C D E F G
Aplicacions de l'arbre binari
Un arbre binari s’utilitza en moltes aplicacions per emmagatzemar dades.
A continuació es detallen algunes de les aplicacions importants dels arbres binaris:
- Arbres de cerca binària: Els arbres binaris s’utilitzen per construir un arbre de cerca binari que s’utilitza en moltes aplicacions de cerca, com ara conjunts i mapes en moltes biblioteques d’idiomes.
- Arbres Hash: S’utilitza per verificar els hashs principalment en aplicacions de signatura d’imatges especialitzades.
- Munts: Els munts s’utilitzen per implementar cues de prioritat que s’utilitzen per a encaminadors, programació de processadors al sistema operatiu, etc.
- Codificació Huffman: L’arbre de codificació Huffman s’utilitza en algorismes de compressió (com la compressió d’imatges), així com en aplicacions criptogràfiques.
- Arbre de sintaxi: Els compiladors sovint construeixen arbres de sintaxi que no són res més que arbres binaris per analitzar les expressions utilitzades al programa.
Conclusió
Els arbres binaris són estructures de dades àmpliament utilitzades a tota la indústria del programari. Els arbres binaris són els arbres els nodes dels quals tenen com a màxim dos nodes fills. Hem vist diversos tipus d’arbres binaris com un arbre binari complet, un arbre binari complet, un arbre binari perfecte, un arbre binari degenerat, un arbre binari equilibrat, etc.
Les dades de l’arbre binari també es poden recórrer mitjançant tècniques de recorregut per ordre, preordre i postordre que hem vist al nostre tutorial anterior. A la memòria, es pot representar un arbre binari mitjançant una llista enllaçada (memòria no contigua) o matrius (representació seqüencial).
La representació de llistes enllaçades és més eficient en comparació amb matrius, ja que les matrius ocupen molt d’espai.
=> Consulteu aquí els millors tutorials de formació en C ++.
Lectura recomanada
- Arbre AVL i estructura de dades de Heap a C ++
- Estructura de dades d’arbre B i arbre B + en C ++
- Estructura de dades de la cua en C ++ amb il·lustració
- Estructura de dades de pila en C ++ amb il·lustració
- Estructura de dades de llistes enllaçades circulars en C ++ amb il·lustració
- Estructura de dades de la llista enllaçada en C ++ amb il·lustració
- Introducció a les estructures de dades en C ++
- Estructura de dades de la cua de prioritat en C ++ amb il·lustració