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 denominati come figli "sinistro" e "destro". 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 vuoto, i nodi vengono attaccati a partire dalla posizione più a sinistra. Un albero binario completo è un albero in cui ogni nodo dell'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 tranne le foglie ha esattamente due figli. La figura 1 di seguito mostra un albero binario completo. In un albero binario completo, il numero di nodi (n), il numero di lave (l) e il numero di nodi interni (i) è correlato in modo speciale in modo tale che se ne conosci uno puoi determinare gli altri due valori come segue:
1. Se un albero binario completo ha i nodi interni:
- Numero di ante 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 ante l = (n + 1) / 2
3. Se un albero binario completo ha l foglie:
- Numero totale di nodi n = 2 * l-1
- Numero di nodi interni i = l-1
Cos'è l'albero binario completo?
Come mostrato nella 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 si trova a sinistra di b
Qual è la differenza tra albero binario completo e albero binario completo?
Gli alberi binari completi e gli alberi binari completi hanno una netta 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 conosci il numero di nodi totali o il numero di lave o il numero di nodi interni, puoi trovare gli altri due molto facilmente. Ma un albero binario completo non ha una proprietà speciale che mette in relazione questi tre attributi.
