Menu

Alberi in C ++: terminologia di base, tecniche di attraversamento e tipi di alberi C ++

  • Principale
  • Altro
  • Alberi in C ++: terminologia di base, tecniche di attraversamento e tipi di alberi C ++

trees c basic terminology

Prova Il Nostro Strumento Per Eliminare I Problemi

Questo tutorial approfondito sugli alberi C ++ spiega i tipi di albero, le tecniche di attraversamento degli alberi e la terminologia di base con immagini e programmi di esempio:

In questa serie C ++, finora abbiamo visto la struttura dati lineare di natura sia statica che dinamica. Ora procederemo con la struttura dati non lineare. La prima struttura di dati in questa categoria è 'Alberi'.

Gli alberi sono strutture di dati gerarchiche non lineari. Un albero è un insieme di nodi collegati tra loro mediante 'bordi' diretti o non orientati. Uno dei nodi è designato come 'nodo radice' e i nodi rimanenti sono chiamati nodi figlio o nodi foglia del nodo radice.

In generale, ogni nodo può avere tanti figli ma solo un nodo padre.

=> Dai un'occhiata all'intera serie di formazione C ++

Albero in C ++

I nodi di un albero sono allo stesso livello chiamati nodi sorelle oppure possono avere una relazione genitore-figlio. I nodi con lo stesso genitore sono nodi di pari livello.

come creare un array generico in java

Cosa imparerai:

Alberi in C ++

Di seguito è riportato un albero di esempio con le sue varie parti.

Albero in C ++ con le sue varie parti

Esaminiamo le definizioni di alcuni termini di base che utilizziamo per gli alberi.

  • Nodo radice: Questo è il nodo più in alto nella gerarchia ad albero. Nel diagramma sopra, il nodo A è il nodo radice. Tieni presente che il nodo radice non ha alcun genitore.
  • Nodo fogliare: È il nodo più in basso in una gerarchia ad albero. I nodi foglia sono i nodi che non hanno nodi figlio. Sono anche conosciuti come nodi esterni. I nodi E, F, G, H e C nell'albero sopra sono tutti nodi foglia.
  • Sottostruttura: La sottostruttura rappresenta diversi discendenti di un nodo quando la radice non è nulla. Un albero di solito è costituito da un nodo radice e da uno o più sottoalberi. Nel diagramma sopra, (B-E, B-F) e (D-G, D-H) sono sottoalberi.
  • Nodo genitore: Qualsiasi nodo tranne il nodo radice che ha un nodo figlio e un bordo verso l'alto verso il genitore.
  • Nodo antenato: È un qualsiasi nodo predecessore su un percorso dalla radice a quel nodo. Nota che la radice non ha antenati. Nel diagramma sopra, A e B sono gli antenati di E.
  • Chiave: Rappresenta il valore di un nodo.
  • Livello: Rappresenta la generazione di un nodo. Un nodo radice è sempre al livello 1. I nodi figli della radice sono al livello 2, i nipoti della radice sono al livello 3 e così via. In generale, ogni nodo si trova a un livello superiore al suo genitore.
  • Sentiero: Il percorso è una sequenza di bordi consecutivi. Nel diagramma sopra, il percorso verso E è A => B-> E.
  • Grado: Il grado di un nodo indica il numero di figli di un nodo. Nel diagramma sopra, il grado di B e D è 2 ciascuno mentre il grado di C è 0.

Tipi di alberi C ++

La struttura dei dati ad albero può essere classificata nei seguenti sottotipi come mostrato nel diagramma sottostante.

Tipi di albero in C ++

# 1) Albero generale

L'albero generale è la rappresentazione di base di un albero. Ha un nodo e uno o più nodi figlio. Il nodo di primo livello, ovvero il nodo radice, è presente al livello 1 e tutti gli altri nodi possono essere presenti a vari livelli.

Un albero generale è mostrato nella figura seguente.

Albero generale

Come mostrato nella figura sopra, un albero generale può contenere un numero qualsiasi di sottoalberi. I nodi B, C e D sono presenti al livello 2 e sono nodi di pari livello. Allo stesso modo, anche i nodi E, F, G e H sono nodi di pari livello.

I nodi presenti a diversi livelli possono mostrare una relazione genitore-figlio. Nella figura sopra, i nodi B, C e D sono figli di A. I nodi E ed F sono figli di B mentre i nodi G e H sono figli di D.

L'albero generale è illustrato di seguito utilizzando l'implementazione C ++:

#include using namespace std; //declaration for new tree node struct node { int data; struct node *left; struct node *right; }; //allocates new node struct node* newNode(int data) { // declare and allocate new node struct node* node = new struct node(); node->data = data; // Assign data to this node // Initialize left and right children as NULL node->left = NULL; node->right = NULL; return(node); } int main() { /*create root node*/ struct node *rootNode = newNode(10); cout<<'General tree created is as follows:'<data<left = newNode(20); rootNode->right = newNode(30); cout<<' '<left->data<<' '<right->data; cout<left->left = newNode(40); cout<<' '<<'/'<left->left->data; return 0; }

Produzione:

L'albero generale creato è il seguente:

10

/

20 30

/

40

big data come società di servizi

# 2) Foreste

Ogni volta che cancelliamo il nodo radice dall'albero e i bordi che uniscono gli elementi del livello successivo e la radice, otteniamo insiemi disgiunti di alberi come mostrato di seguito.

Foreste

Nella figura sopra, abbiamo ottenuto due foreste eliminando il nodo radice A e i tre bordi che collegavano il nodo radice ai nodi B, C e D.

# 3) Albero binario

Una struttura dati ad albero in cui ogni nodo ha al massimo due nodi figlio è chiamata albero binario. Un albero binario è la struttura dati ad albero più popolare e viene utilizzato in una vasta gamma di applicazioni come la valutazione di espressioni, database, ecc.

La figura seguente mostra un albero binario.

Albero binario

Nella figura sopra, vediamo che i nodi A, B e D hanno due figli ciascuno. Un albero binario in cui ogni nodo ha esattamente zero o due figli è chiamato albero binario completo. In questo albero non ci sono nodi che hanno un figlio.

Un albero binario completo ha un albero binario completamente riempito ad eccezione del livello più basso che viene riempito da sinistra a destra. L'albero binario mostrato sopra è un albero binario completo.

Di seguito è riportato un semplice programma per dimostrare un albero binario. Si noti che l'output dell'albero è la sequenza trasversale in ordine dell'albero di input.

#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

# 4) Albero di ricerca binario

L'albero binario ordinato è chiamato albero binario di ricerca. In un albero di ricerca binario, i nodi a sinistra sono inferiori al nodo radice mentre i nodi a destra sono maggiori o uguali al nodo radice.

Di seguito è mostrato un esempio di albero di ricerca binario.

Albero di ricerca binario

Nella figura sopra, possiamo vedere che i nodi di sinistra sono tutti inferiori a 20, che è l'elemento radice. I nodi di destra, d'altra parte, sono maggiori del nodo radice. L'albero di ricerca binario viene utilizzato nelle tecniche di ricerca e ordinamento.

# 5) Albero delle espressioni

Un albero binario utilizzato per valutare semplici espressioni aritmetiche è chiamato albero delle espressioni.

Di seguito viene mostrato un semplice albero delle espressioni.

Albero delle espressioni

Nell'albero delle espressioni di esempio sopra, rappresentiamo l'espressione (a + b) / (a-b). Come mostrato nella figura sopra, i nodi non foglia dell'albero rappresentano gli operatori dell'espressione mentre i nodi foglia rappresentano gli operandi.

Gli alberi delle espressioni vengono utilizzati principalmente per risolvere espressioni algebriche.

Tecniche di attraversamento degli alberi

Abbiamo visto strutture di dati lineari come array, elenchi concatenati, stack, code, ecc. Tutte queste strutture di dati hanno una tecnica di attraversamento comune che attraversa la struttura solo in un modo, cioè linearmente.

antivirus con VPN incluso

Ma nel caso degli alberi, abbiamo diverse tecniche di attraversamento come elencato di seguito:

# 1) In ordine: In questa tecnica di attraversamento, attraversiamo prima la sottostruttura sinistra finché non ci sono più nodi nella sottostruttura sinistra. Dopodiché, visitiamo il nodo radice e quindi procediamo ad attraversare la sottostruttura destra finché non ci sono più nodi da attraversare nella sottostruttura destra. Quindi l'ordine di inOrder traversal è left-> root-> right.

# 2) Preordina: Per la tecnica di attraversamento del preordine, elaboriamo prima il nodo radice, quindi attraversiamo l'intera sottostruttura sinistra e infine attraversiamo la sottostruttura destra. Quindi l'ordine di attraversamento del preordine è radice-> sinistra-> destra.

# 3) Post-ordine: Nella tecnica di attraversamento post-ordine, attraversiamo la sottostruttura sinistra, quindi la sottostruttura destra e infine il nodo radice. L'ordine di attraversamento per la tecnica del postordine è left-> right-> root.

Se n è il nodo radice e 'l' e 'r' sono rispettivamente i nodi sinistro e destro dell'albero, gli algoritmi di attraversamento dell'albero sono i seguenti:

Algoritmo in ordine (lnr):

  1. Attraversa la sottostruttura sinistra utilizzando inOrder (sinistra-sottostruttura).
  2. Visita il nodo radice (n).
  3. Attraversa la sottostruttura destra utilizzando inOrder (sottostruttura destra).

Algoritmo di preordine (nlr):

  1. Visita il nodo radice (n).
  2. Attraversa la sottostruttura sinistra utilizzando il preordine (sottostruttura sinistra).
  3. Attraversa la sottostruttura destra utilizzando il preordine (sottostruttura destra).

Algoritmo postorder (lrn):

  1. Attraversa la sottostruttura sinistra utilizzando postOrder (sottostruttura sinistra).
  2. Attraversa la sottostruttura destra utilizzando postOrder (sottostruttura destra).
  3. Visita il nodo radice (n).

Dagli algoritmi di cui sopra delle tecniche di attraversamento, vediamo che le tecniche possono essere applicate a un dato albero in modo ricorsivo per ottenere il risultato desiderato.

Considera il seguente albero.

Algoritmo di postorder (lrn)

Utilizzando le tecniche di attraversamento di cui sopra, la sequenza di attraversamento per l'albero sopra è data di seguito:

  1. InOrder traversal: 2 3 5 6 10
  2. Attraversamento preordine: 6 3 2 5 10
  3. PostOrder traversal: 2 5 3 10 6

Conclusione

Gli alberi sono una struttura dati gerarchica non lineare utilizzata in molte applicazioni nel campo del software.

A differenza delle strutture di dati lineari che hanno un solo modo per attraversare l'elenco, possiamo attraversare gli alberi in una varietà di modi. In questo tutorial abbiamo avuto uno studio dettagliato delle tecniche di attraversamento e dei vari tipi di alberi.

=> Dai un'occhiata alla guida per principianti di C ++ qui

Lettura consigliata

^