Differenza tra albero binario completo e albero binario completo

Albero binario completo vs Albero binario completo

L'albero binario è un albero in cui ogni nodo ha uno o due figli. In un albero binario, un nodo non può avere più di due figli. In un albero binario, i bambini vengono chiamati "bambini di sinistra" e "di destra". I nodi figlio contengono un riferimento al loro genitore. Un albero binario completo è un albero binario in cui ogni livello dell'albero binario è completamente riempito tranne l'ultimo livello. Nel livello non completato, i nodi sono collegati a partire dalla posizione più a sinistra. Un albero binario completo è un albero in cui ogni nodo nell'albero ha due figli tranne le foglie dell'albero.

Cos'è l'albero binario completo?

L'albero binario completo è un albero binario in cui ogni nodo dell'albero ha esattamente zero o due figli. In altre parole, ogni nodo dell'albero eccetto le foglie ha esattamente due figli. La Figura 1 sotto mostra un albero binario completo. In un albero binario completo, il numero di nodi (n), il numero di laves (l) e il numero di nodi interni (i) è correlato in un modo speciale tale che se ne conosci uno di questi puoi determinare gli altri due valori come segue:

1. Se un albero binario completo ha i nodi interni:

- Numero di foglie l = i + 1

- Numero totale di nodi n = 2 * i + 1

2. Se un albero binario completo ha n nodi:

- Numero di nodi interni i = (n-1) / 2

- Numero di foglie l = (n + 1) / 2

3. Se un albero binario completo ha le foglie:

- Numero totale di nodi n = 2 * l-1

- Numero di nodi interni i = l-1

Cos'è l'albero binario completo?

Come mostrato in figura 2, un albero binario completo è un albero binario in cui ogni livello dell'albero è completamente riempito tranne l'ultimo livello. Inoltre, nell'ultimo livello, i nodi dovrebbero essere collegati a partire dalla posizione più a sinistra. Un albero binario completo di altezza h soddisfa le seguenti condizioni:

- Dal nodo radice, il livello sopra l'ultimo livello rappresenta un albero binario completo di altezza h-1

- Uno o più nodi nell'ultimo livello possono avere 0 o 1 figli

- Se a, b sono due nodi nel livello sopra l'ultimo livello, allora a ha più figli di b se e solo se a è situato a sinistra di b

Qual è la differenza tra Complete Binary Tree e Full Binary Tree?

Alberi binari completi e alberi binari completi hanno una chiara differenza. Mentre un albero binario completo è un albero binario in cui ogni nodo ha zero o due figli, un albero binario completo è un albero binario in cui ogni livello dell'albero binario è completamente riempito tranne l'ultimo livello. Alcune strutture di dati speciali come gli heap devono essere alberi binari completi mentre non devono essere alberi binari completi. In un albero binario completo, se si conosce il numero di nodi totali o il numero di laves o il numero di nodi interni, è possibile trovare gli altri due molto facilmente. Ma un albero binario completo non ha una proprietà speciale relativa a questi tre attributi.