Cos'è un albero binario completo?
Un albero binario completo può essere definito come a albero binario in cui tutti i nodi hanno 0 o due figli. In altre parole, l’albero binario completo può essere definito come un albero binario in cui tutti i nodi hanno due figli tranne i nodi foglia.
L'albero seguente è un albero binario completo:
L'albero sopra è un albero binario completo poiché tutti i nodi tranne i nodi foglia hanno due figli.
Teorema completo dell'albero binario:
macchina virtuale Java
Consideriamo quindi un albero binario T come un albero non vuoto:
- Sia I i nodi interni di un albero e L un nodo foglia di un albero, allora il numero di nodi foglia sarebbe uguale a:
L = io + 1 - Se T ha I numero di nodi interni e N è il numero totale di nodi, allora il numero totale di nodi sarebbe uguale a:
N = 2I + 1 - Se T contiene 'N' il numero totale di nodi e 'I' il numero di nodi interni, allora il numero di nodi interni sarebbe uguale a:
Io = (N-1)/2 - Se 'T' ha 'N' un numero totale di nodi e 'L' è un numero di nodi foglia, il numero di nodi foglia sarebbe uguale a:
L = (N+1)/2 - Se 'T' contiene il numero 'L' di nodi foglia, il numero totale di nodi sarebbe uguale a:
N = 2L - 1 - Se 'T' ha un numero 'L' di nodi foglia e 'I' è un numero di nodi interni, allora il numero di nodi interni sarebbe uguale a:
io = L - 1
Cos'è un albero binario completo?
Un albero binario si dice completo quando tutti i livelli sono completamente riempiti tranne l'ultimo livello, che viene riempito da sinistra.
L'albero seguente è un albero binario completo:
L'albero binario completo è simile all'albero binario completo ad eccezione delle due differenze riportate di seguito:
- Il riempimento del nodo foglia deve iniziare dal lato più a sinistra.
- Non è obbligatorio che l'ultimo nodo foglia abbia il fratello giusto.
Capiamo i punti precedenti attraverso un esempio:
cos'è l'ibernazione in Java
Considera l'albero seguente:
L'albero sopra è un albero binario completo, ma non un albero binario completo poiché il nodo 6 non ha il fratello destro.
lista collegata in Java
Creazione di un albero binario completo
Supponiamo di avere un array di 6 elementi mostrato di seguito:
L'array sopra contiene 6 elementi, ovvero 1, 2, 3, 4, 5, 6. Di seguito sono riportati i passaggi da utilizzare per creare un albero binario completo:
Passo 1: Per prima cosa selezioneremo il primo elemento dell'array, cioè 1, e creeremo un nodo radice dell'albero. Il numero di elementi disponibili nel primo livello è 1.
Passo 2: Ora selezioneremo il secondo e il terzo elemento dell'array. Mantieni il secondo elemento e il terzo elemento dell'array come figlio sinistro e destro del nodo radice rispettivamente mostrati come di seguito:
Come possiamo osservare sopra, il numero di elementi disponibili nel secondo livello è 2.
Passaggio 3: Ora selezioneremo i due elementi successivi dall'array, ovvero 4 e 5. Mantieni questi due elementi a sinistra e a destra del nodo 2 mostrato di seguito:
Come possiamo osservare sopra, i nodi 4 e 5 sono rispettivamente il figlio sinistro e destro del nodo 2.
Passaggio 4: Ora selezioneremo l'ultimo elemento dell'array, ovvero 6, e lo manterremo come figlio sinistro del nodo 3 poiché sappiamo che in un albero binario completo, i nodi sono riempiti dal lato sinistro come mostrato di seguito:
parola chiave volatile Java
Come possiamo osservare che il secondo livello contiene 3 elementi.
Capiamo attraverso le immagini le differenze tra albero binario completo e completo.
- L'albero binario mostrato di seguito non è né un albero binario completo né un albero binario completo. Non è un albero binario completo perché il nodo 3 ha un solo figlio. Inoltre non è un albero binario completo poiché i nodi dovrebbero essere riempiti dal lato sinistro, ma il nodo 3 ha un figlio destro e non ha un figlio sinistro.
- L'albero binario, mostrato di seguito, è un albero binario completo ma non un albero binario completo. È un albero binario completo perché tutti i nodi hanno 0 o 2 figli. Non è un albero binario completo perché il nodo 3 non ha figli mentre il nodo 2 ha i suoi figli e sappiamo che i nodi dovrebbero essere riempiti dal lato sinistro in un albero binario completo.
- L'albero binario mostrato di seguito è un albero binario completo ma non un albero binario completo. È un albero binario completo poiché tutti i nodi vengono lasciati riempiti. Non è un albero binario completo poiché il nodo 2 ha un solo figlio.
- L'albero binario mostrato di seguito è un albero binario completo e completo. È un albero binario completo poiché tutti i nodi vengono lasciati riempiti. È un albero binario completo poiché tutti i nodi hanno 0 o 2 figli.
