Differenza tra albero binario completo e albero binario completo

Albero binario completo vs albero binario completo

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 bambini. In un albero binario, i bambini sono chiamati "bambini" sinistro e "giusto". 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 soddisfatto, i nodi sono collegati a partire dalla posizione più sinistra. Un albero binario completo è un albero in cui ogni nodo dell'albero ha due figli ad eccezione delle foglie dell'albero.

Che cosa è 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 riporta un albero binario completo. In un albero binario completo, il numero di nodi (n), il numero di lavati (l) e il numero di nodi interni (i) sono legati in modo speciale in modo tale che se conosci uno di essi è possibile 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 foglie l:

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

- Numero di nodi interni i = l-1

Che cosa è 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ù sinistra. Un albero binario completo di altezza h soddisfa le seguenti condizioni:

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

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

- Se a, b sono due nodi al livello sopra l'ultimo livello, allora un ha più bambini di b se e solo se si trova a sinistra di b

Qual è la differenza tra l'albero binario completo e l'albero binario completo?

Gli alberi binari completi e gli 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 dati speciali come le colonne 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 lavas o il numero di nodi interni, puoi trovare gli altri due facilmente.Ma un albero binario completo non dispone di una proprietà speciale relativa a tre attributi.