L'albero binario significa che il nodo può avere un massimo di due figli. Qui, il nome binario stesso suggerisce che 'due'; pertanto, ciascun nodo può avere 0, 1 o 2 figli.

Comprendiamo l'albero binario attraverso un esempio.

reti di computer

L'albero sopra è un albero binario perché ogni nodo contiene al massimo due figli. La rappresentazione logica dell'albero sopra è riportata di seguito:

Nell'albero precedente, il nodo 1 contiene due puntatori, ovvero un puntatore sinistro e uno destro che puntano rispettivamente al nodo sinistro e destro. Il nodo 2 contiene entrambi i nodi (nodo sinistro e nodo destro); pertanto, ha due puntatori (sinistro e destro). I nodi 3, 5 e 6 sono i nodi foglia, quindi tutti questi nodi contengono NULLO puntatore su entrambe le parti sinistra e destra.

Proprietà dell'albero binario

• Ad ogni livello di i, il numero massimo di nodi è 2^io.
• L'altezza dell'albero è definita come il percorso più lungo dal nodo radice al nodo foglia. L'albero sopra rappresentato ha altezza pari a 3. Pertanto il numero massimo di nodi possibili ad altezza 3 è pari a (1+2+4+8) = 15. In generale il numero massimo di nodi possibili ad altezza h è (2⁰+2¹+2²+….2^H) = 2^h+1-1.
• Il numero minimo di nodi possibili all'altezza h è pari a h+1 .
• Se il numero di nodi fosse minimo, l'altezza dell'albero sarebbe massima. Al contrario, se il numero di nodi fosse massimo, l’altezza dell’albero sarebbe minima.

Se c'è un numero 'n' di nodi nell'albero binario.

L'altezza minima può essere calcolata come:

Come sappiamo,

n = 2^h+1-1

n+1 = 2^h+1

Prendendo il tronco su entrambi i lati,

tronco d'albero₂(n+1) = log2(2^h+1)

tronco d'albero₂(n+1) = h+1

h = logaritmo₂(n+1) - 1

L'altezza massima può essere calcolata come:

Come sappiamo,

n = h+1

h=n-1

logica di trasferimento dei registri

Tipi di albero binario

Esistono quattro tipi di alberi binari:

Albero binario completo/proprio/rigoroso Albero binario completo Albero binario perfetto Albero binario degenere Albero binario bilanciato

1. Albero binario completo/proprio/rigoroso

codice fibonacci java

L'albero binario completo è noto anche come albero binario rigoroso. L'albero può essere considerato come l'albero binario completo solo se ciascun nodo deve contenere 0 o 2 figli. L'albero binario completo può anche essere definito come l'albero in cui ciascun nodo deve contenere 2 figli tranne i nodi foglia.

Diamo un'occhiata al semplice esempio dell'albero binario completo.

Nell'albero sopra, possiamo osservare che ogni nodo contiene zero o due figli; pertanto, è un albero binario completo.

Proprietà dell'albero binario completo

• Il numero di nodi foglia è uguale al numero di nodi interni più 1. Nell'esempio sopra, il numero di nodi interni è 5; pertanto, il numero di nodi foglia è pari a 6.
• Il numero massimo di nodi è uguale al numero di nodi nell'albero binario, ovvero 2^h+1-1.
• Il numero minimo di nodi nell'albero binario completo è 2*h-1.
• L'altezza minima dell'intero albero binario è tronco d'albero₂(n+1) - 1.
• L'altezza massima dell'intero albero binario può essere calcolata come:

n=2*h - 1

n+1 = 2*h

h = n+1/2

Albero binario completo

L'albero binario completo è un albero in cui tutti i nodi sono completamente riempiti tranne l'ultimo livello. Nell'ultimo livello, tutti i nodi devono essere il più a sinistra possibile. In un albero binario completo, i nodi dovrebbero essere aggiunti da sinistra.

Jasmine Davis da bambina

Creiamo un albero binario completo.

L'albero sopra è un albero binario completo perché tutti i nodi sono completamente riempiti e tutti i nodi nell'ultimo livello vengono aggiunti per primi a sinistra.

Proprietà dell'albero binario completo

• Il numero massimo di nodi nell'albero binario completo è 2^h+1-1.
• Il numero minimo di nodi nell'albero binario completo è 2^H.
• L'altezza minima di un albero binario completo è tronco d'albero₂(n+1) - 1.
• L'altezza massima di un albero binario completo è

Albero binario perfetto

Un albero è un albero binario perfetto se tutti i nodi interni hanno 2 figli e tutti i nodi foglia sono allo stesso livello.

Consideriamo un semplice esempio di albero binario perfetto.

L'albero sottostante non è un albero binario perfetto perché tutti i nodi foglia non sono allo stesso livello.

Nota: tutti gli alberi binari perfetti sono alberi binari completi così come l'albero binario completo, ma non è vero il contrario, ovvero tutti gli alberi binari completi e gli alberi binari completi sono alberi binari perfetti.

Albero binario degenerato

L'albero binario degenere è un albero in cui tutti i nodi interni hanno un solo figlio.

Comprendiamo l'albero binario degenere attraverso esempi.

L'albero sopra è un albero binario degenere perché tutti i nodi hanno un solo figlio. È anche noto come albero inclinato a destra poiché tutti i nodi hanno solo un figlio destro.

L'albero sopra è anche un albero binario degenere perché tutti i nodi hanno un solo figlio. È anche noto come albero inclinato a sinistra poiché tutti i nodi hanno solo un figlio sinistro.

Albero binario bilanciato

L'albero binario bilanciato è un albero in cui sia l'albero sinistro che quello destro differiscono almeno di 1. Ad esempio, AVL E Alberi rosso-neri sono alberi binari bilanciati.

Comprendiamo l'albero binario bilanciato attraverso degli esempi.

L'albero sopra è un albero binario bilanciato perché la differenza tra il sottoalbero sinistro e quello destro è zero.

attore cinematografico Vijay

L'albero sopra non è un albero binario bilanciato perché la differenza tra il sottoalbero sinistro e quello destro è maggiore di 1.

Implementazione dell'albero binario

Un albero binario viene implementato con l'aiuto di puntatori. Il primo nodo dell'albero è rappresentato dal puntatore radice. Ogni nodo nell'albero è composto da tre parti, ovvero dati, puntatore sinistro e puntatore destro. Per creare un albero binario, dobbiamo prima creare il nodo. Creeremo il nodo definito dall'utente come mostrato di seguito:

 struct node { int data, struct node *left, *right; } 

Nella struttura di cui sopra, dati è il valore, puntatore sinistro contiene l'indirizzo del nodo sinistro e puntatore destro contiene l'indirizzo del nodo destro.

Programma di albero binario in C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Il codice precedente chiama ricorsivamente la funzione create() e crea un nuovo nodo su ogni chiamata ricorsiva. Quando vengono creati tutti i nodi, si forma una struttura ad albero binaria. Il processo di visita dei nodi è noto come attraversamento dell'albero. Esistono tre tipi di attraversamenti utilizzati per visitare un nodo:

• Attraversamento in ordine
• Attraversamento del preordine
• Viaggio del vaglia postale