binary tree data structure c
Questo tutorial approfondito sull'albero binario in C ++ spiega tipi, rappresentazione, attraversamento, applicazioni e implementazione di alberi binari in C ++:
Un albero binario è una struttura dati ad albero ampiamente utilizzata. Quando ogni nodo di un albero ha al massimo due nodi figlio, l'albero viene chiamato albero binario.
Quindi un tipico albero binario avrà i seguenti componenti:
- Una sottostruttura di sinistra
- Un nodo radice
- Una sottostruttura a destra
=> Guarda l'elenco completo dei tutorial C ++ in questa serie.
Cosa imparerai:
- Albero binario in C ++
- Tipi di albero binario
- Rappresentazione dell'albero binario
- Implementazione dell'albero binario in C ++
- Attraversamento albero binario
- Applicazioni di albero binario
- Conclusione
- Lettura consigliata
Albero binario in C ++
Di seguito è mostrata una rappresentazione pittorica di un albero binario:
In un dato albero binario, il numero massimo di nodi a qualsiasi livello è 2l-1dove 'l' è il numero del livello.
Pertanto, nel caso del nodo radice al livello 1, il numero massimo di nodi = 21-1= 20= 1
Poiché ogni nodo in un albero binario ha al massimo due nodi, il numero massimo di nodi al livello successivo sarà 2 * 2l-1.
miglior programma per creare diagrammi di flusso
Dato un albero binario di profondità o altezza h, il numero massimo di nodi in un albero binario di altezza h = 2h- 1.
Quindi in un albero binario di altezza 3 (mostrato sopra), il numero massimo di nodi = 23-1 = 7.
Parliamo ora dei vari tipi di alberi binari.
Tipi di albero binario
Di seguito sono riportati i tipi più comuni di alberi binari.
# 1) Albero binario completo
Un albero binario in cui ogni nodo ha 0 o 2 figli è definito albero binario completo.
Sopra è mostrato un albero binario completo in cui possiamo vedere che tutti i suoi nodi tranne i nodi foglia hanno due figli. Se L è il numero di nodi foglia e 'l' è il numero di nodi interni o non foglia, per un albero binario completo, L = l + 1.
# 2) Completa l'albero binario
Un albero binario completo ha tutti i livelli riempiti tranne l'ultimo livello e l'ultimo livello ha tutti i suoi nodi tanto quanto a sinistra.
L'albero mostrato sopra è un albero binario completo. Un tipico esempio di un albero binario completo è un heap binario di cui parleremo nelle esercitazioni successive.
# 3) Albero binario perfetto
Un albero binario viene definito perfetto quando tutti i suoi nodi interni hanno due figli e tutti i nodi foglia sono allo stesso livello.
Un esempio di albero binario mostrato sopra è un albero binario perfetto poiché ciascuno dei suoi nodi ha due figli e tutti i nodi foglia sono allo stesso livello.
Un albero binario perfetto di altezza h ha 2h- 1 numero di nodi.
# 4) Un albero degenerato
Un albero binario in cui ogni nodo interno ha un solo figlio è chiamato albero degenere.
L'albero mostrato sopra è un albero degenere. Per quanto riguarda le prestazioni di questo albero, gli alberi degenerati sono gli stessi delle liste concatenate.
# 5) Albero binario bilanciato
Un albero binario in cui la profondità dei due sottoalberi di ogni nodo non differisce mai di più di 1 è chiamato albero binario bilanciato.
L'albero binario mostrato sopra è un albero binario bilanciato poiché la profondità dei due sottoalberi di ogni nodo non è superiore a 1. Gli alberi AVL di cui parleremo nei nostri successivi tutorial sono un albero bilanciato comune.
Rappresentazione dell'albero binario
A un albero binario viene allocata la memoria in due modi.
# 1) Rappresentazione sequenziale
Questa è la tecnica più semplice per memorizzare una struttura dati ad albero. Un array viene utilizzato per memorizzare i nodi dell'albero. Il numero di nodi in un albero definisce la dimensione dell'array. Il nodo radice dell'albero viene memorizzato nel primo indice dell'array.
In generale, se un nodo è memorizzato in ithposizione, quindi il figlio sinistro e destro viene memorizzato rispettivamente nella posizione 2i e 2i + 1.
Considera il seguente albero binario.
La rappresentazione sequenziale dell'albero binario sopra è la seguente:
Nella rappresentazione sopra, vediamo che il figlio sinistro e destro di ogni nodo è memorizzato nelle posizioni 2 * (node_location) e 2 * (node_location) +1 rispettivamente.
Per esempio, la posizione del nodo 3 nell'array è 3. Quindi il suo figlio sinistro sarà posto a 2 * 3 = 6. Il suo figlio destro sarà nella posizione 2 * 3 +1 = 7. Come possiamo vedere nell'array, children di 3 che sono 6 e 7 vengono posizionati nella posizione 6 e 7 nella matrice.
La rappresentazione sequenziale dell'albero è inefficiente poiché l'array utilizzato per memorizzare i nodi dell'albero occupa molto spazio in memoria. Man mano che l'albero cresce, questa rappresentazione diventa inefficiente e difficile da gestire.
Questo inconveniente viene superato memorizzando i nodi dell'albero in un elenco collegato. Si noti che se l'albero è vuoto, la prima posizione in cui è archiviato il nodo radice sarà impostata su 0.
# 2) Rappresentanza di liste collegate
In questo tipo di rappresentazione, viene utilizzato un elenco collegato per memorizzare i nodi dell'albero. Diversi nodi sono sparsi nella memoria in posizioni non contigue ei nodi sono collegati utilizzando la relazione genitore-figlio come un albero.
Il diagramma seguente mostra una rappresentazione di un elenco collegato per un albero.
Come mostrato nella rappresentazione sopra, ogni nodo dell'elenco collegato ha tre componenti:
- Puntatore sinistro
- Parte dati
- Puntatore a destra
Il puntatore sinistro ha un puntatore al figlio sinistro del nodo; il puntatore destro ha un puntatore al figlio destro del nodo mentre la parte dati contiene i dati effettivi del nodo. Se non ci sono figli per un dato nodo (nodo foglia), i puntatori sinistro e destro per quel nodo vengono impostati su null come mostrato nella figura sopra.
software installato su un computer e utilizzato per gestire le macchine virtuali
Implementazione dell'albero binario in C ++
Successivamente, sviluppiamo un programma ad albero binario utilizzando una rappresentazione di elenco collegato in C ++. Usiamo una struttura per dichiarare un singolo nodo e quindi utilizzando una classe, sviluppiamo un elenco collegato di nodi.
#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: '< Produzione:
Albero binario creato:
5 10 15 20 30 40 45
Attraversamento albero binario
Abbiamo già discusso degli attraversamenti nel nostro tutorial di base sugli alberi. In questa sezione, implementiamo un programma che inserisca i nodi nell'albero binario e che mostri anche tutti e tre gli attraversamenti cioè inorder, preorder e postorder, per un albero binario.
#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:'< Produzione:
Attraversamento in ordine:
A B C D E F G
Attraversamento per corrispondenza:
G F E D C B A
Preordina attraversamento:
A B C D E F G
Applicazioni di albero binario
Un albero binario viene utilizzato in molte applicazioni per la memorizzazione dei dati.
Di seguito sono elencate alcune delle applicazioni importanti degli alberi binari:
- Alberi di ricerca binari: Gli alberi binari vengono utilizzati per costruire un albero di ricerca binario che viene utilizzato in molte applicazioni di ricerca come set e mappe in molte librerie di lingue.
- Alberi hash: Utilizzato per verificare gli hash principalmente in applicazioni di firma di immagini specializzate.
- Mucchi: Gli heap vengono utilizzati per implementare code di priorità utilizzate per router, processori di pianificazione nel sistema operativo, ecc.
- Codifica Huffman: L'albero di codifica di Huffman viene utilizzato negli algoritmi di compressione (come la compressione delle immagini) e nelle applicazioni crittografiche.
- Albero della sintassi: I compilatori spesso costruiscono alberi di sintassi che non sono altro che alberi binari per analizzare le espressioni utilizzate nel programma.
Conclusione
Gli alberi binari sono strutture di dati ampiamente utilizzate nell'industria del software. Gli alberi binari sono gli alberi i cui nodi hanno al massimo due nodi figli. Abbiamo visto vari tipi di alberi binari come un albero binario completo, un albero binario completo, un albero binario perfetto, un albero binario degenerato, un albero binario bilanciato, ecc.
I dati dell'albero binario possono anche essere attraversati utilizzando le tecniche di inorder, preorder e postorder traversal che abbiamo visto nel nostro tutorial precedente. In memoria, un albero binario può essere rappresentato utilizzando un elenco collegato (memoria non contigua) o array (rappresentazione sequenziale).
La rappresentazione di elenchi collegati è più efficiente rispetto agli array, poiché gli array occupano molto spazio.
=> Dai un'occhiata ai migliori tutorial di formazione C ++ qui.
Lettura consigliata
- Struttura dei dati ad albero e heap AVL in C ++
- Struttura dati B Tree e B + Tree in C ++
- Struttura dei dati della coda in C ++ con illustrazione
- Stack Struttura Dati In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato Circolare In C ++ Con Illustrazione
- Struttura Dati Elenco Collegato In C ++ Con Illustrazione
- Introduzione alle strutture dati in C ++
- Priorità Struttura Dati Coda In C ++ Con Illustrazione