UN
Un albero binario
Ce ne sono diversi tipi di albero binario ma qui discuteremo della differenza di Albero binario completo E Albero binario completo .
Albero binario completo:
Un albero binario completo è un albero binario in cui tutti i nodi hanno 0 o 2 figli . In altri termini, un albero binario completo è un albero binario in cui tutti i nodi, eccetto i nodi foglia, hanno due figli.
il mio cricket dal vivo
Un albero binario completo
Permettere, io essere il numero di nodi interni
N essere il numero totale di nodi
l essere il numero di foglie
l essere il numero di livelliPoi,
Il numero di foglie è (io + 1) .
Il numero totale di nodi è (2i+1) .
Il numero di nodi interni è (n-1) / 2 .
Il numero di foglie è (n+1)/2 .
Il numero totale di nodi è (2l – 1) .
Il numero di nodi interni è (l-1) .
Il numero di foglie è al massimo (2l- 1) .
Albero binario completo:
Un albero binario si dice essere a albero binario completo se tutti i suoi livelli, tranne eventualmente l'ultimo livello, hanno il numero massimo di nodi possibili, e tutti i nodi nel l'ultimo livello apparirà il più a sinistra possibile .
Un albero binario completo
Ci sono 2 punti che puoi riconoscere da qui,
- Il lato più a sinistra del nodo foglia deve essere sempre riempito per primo.
- Non è necessario che l'ultimo nodo foglia abbia un fratello destro.
Controlla i seguenti esempi per comprendere meglio l'albero binario completo e completo.
Esempio 1:
Esempio di formato jsonNé completo né completo
- Nodo C ha un solo figlio quindi, non è un albero binario completo.
- Nodo C ha anche un figlio destro ma non un figlio sinistro, quindi inoltre non è un albero binario completo.
Quindi, l'albero binario mostrato sopra lo è albero binario né completo né completo.
Esempio 2:
Pieno ma non completo
- Tutti i nodi ne hanno uno 0 O 2 la prole, quindi, è un albero binario completo .
Non è un albero binario completo perché node B non ha figli mentre node C ha figli e, secondo un albero binario completo, i nodi dovrebbero essere riempiti da lato sinistro .Quindi, l'albero binario mostrato sopra è a Albero binario completo e questo è non un albero binario completo.
Esempio 3:
Completo ma non completo
È un albero binario completo poiché tutti i nodi vengono lasciati riempiti.
- Il nodo B ha un solo figlio, quindi, non è un albero binario completo.
Quindi, l'albero binario mostrato sopra è a Albero binario completo e questo è non un albero binario completo.
Esempio 4:
commento javascriptCompleto e pieno
- È un Binario completo albero perché tutti i nodi lo sono lasciato pieno .
- Tutti i nodi ne hanno uno 0 O 2 prole, quindi, è a albero binario completo .
Quindi, l'albero binario mostrato sopra lo è sia un albero binario completo che un albero binario completo.
| Si No. | Albero binario completo | Albero binario completo |
| 1. | In un albero binario completo, un nodo nell'ultimo livello può avere un solo figlio. | In un albero binario completo, un nodo non può avere un solo figlio. |
| 2. | In un albero binario completo, il nodo dovrebbe essere riempito da sinistra a destra. | Non esiste un ordine di riempimento dei nodi in un albero binario completo. |
| 3. | Gli alberi binari completi vengono utilizzati principalmente nelle strutture dati basate su heap. | L'albero binario completo non ha alcuna applicazione in quanto tale, ma è anche chiamato albero binario vero e proprio. |
| 4. | Un albero binario completo è anche chiamato albero binario quasi completo. | Un albero binario completo chiamato anche albero binario vero e proprio o 2-albero. |
| 5 | Un albero binario completo deve avere l'intero nodo delle foglie esattamente alla stessa profondità. | In un albero binario completo, il livello delle foglie non deve necessariamente trovarsi alla stessa profondità. |