Conosciamo un albero è una struttura dati non lineare. Non ci sono limiti al numero di bambini. UNCos'è un albero binario completo?
Un albero binario completo è un tipo speciale di albero binario in cui tutti i livelli dell'albero sono riempiti completamente tranne i nodi di livello più basso che vengono riempiti il più a sinistra possibile.
Albero binario completo
Alcuni termini dell'albero binario completo:
- Radice – Nodo in cui nessun arco proviene dal genitore. Esempio: nodo A
- Bambino – Il nodo che ha qualche fronte entrante è chiamato figlio. Esempio: i nodi B, F sono figli rispettivamente di A e C.
- Fratello – I nodi che hanno lo stesso genitore sono fratelli. Esempio: D, E sono fratelli poiché hanno lo stesso genitore B.
- Grado di un nodo – Numero di figli di un determinato genitore. Esempio: il grado di A è 2 e il grado di C è 1. Il grado di D è 0.
- Nodi interni/esterni – I nodi foglia sono nodi esterni mentre i nodi non foglia sono nodi interni.
- Livello – Contare i nodi in un percorso per raggiungere un nodo di destinazione. Esempio: il livello del nodo D è 2 poiché i nodi A e B formano il percorso.
- Altezza – Numero di bordi per raggiungere il nodo di destinazione, la radice è all'altezza 0. Esempio – L'altezza del nodo E è 2 poiché ha due bordi dalla radice.
Proprietà dell'albero binario completo:
- Un albero binario completo si dice un albero binario vero e proprio in cui tutte le foglie hanno la stessa profondità.
- In un albero binario completo numero di nodi in profondità D È 2 D .
- In un albero binario completo con N l'altezza dei nodi dell'albero è log(n+1) .
- Tutti i livelli tranne l'ultimo livello sono completamente pieni.
Albero binario perfetto vs albero binario completo:
Un albero binario di altezza “h” avente il massimo numero di nodi è a perfetto albero binario.
Per una data altezza H , il numero massimo di nodi è 2 h+1 -1 .
UN completare albero binario di altezza h è un albero binario perfetto fino all'altezza h h-1 e nell'ultimo livello gli elementi vengono memorizzati nell'ordine da sinistra a destra.
Esempio 1:
Un albero binario
L'altezza dell'albero binario dato è 2 e il numero massimo di nodi in quell'albero è n= 2h+1-1 = 22+1-1 = 23-1 = 7 .
Quindi possiamo concludere che lo sia un albero binario perfetto .
Ora, per un albero binario completo, è pieno fino all'altezza h-1 cioè.; 1 e gli elementi dell'ultimo livello vengono memorizzati nell'ordine da sinistra a destra. Quindi è anche un albero binario completo. Ecco la rappresentazione degli elementi quando memorizzati in un array
Elemento memorizzato in un array livello per livello
Nell'array tutti gli elementi vengono memorizzati in modo continuo.
Esempio 2:
comando cp su Linux
Un albero binario
L'altezza dell'albero binario specificato è 2 e il numero massimo di nodi che dovrebbero essere presenti è 2h+1– 1 = 22+1– 1 = 23– 1 = 7 .
Ma il numero di nodi nell'albero lo è 6 . Quindi lo è non un albero binario perfetto .
Ora, per un albero binario completo, è pieno fino all'altezza h-1 i.e.; 1 e l'ultimo elemento di livello vengono memorizzati nell'ordine da sinistra a destra. Quindi questo è a albero binario completo . Memorizza l'elemento in un array e sarà come;
Elemento memorizzato in un array livello per livello
Esempio 3:
cosa c'è in Python
Un albero binario
L'altezza dell'albero binario è 2 e il numero massimo di nodi che possono esserci è 7, ma ci sono solo 5 nodi quindi è non un albero binario perfetto .
Nel caso di un albero binario completo, vediamo che nell'ultimo livello gli elementi non vengono riempiti dall'ordine da sinistra a destra. Così è non un albero binario completo .
Elemento memorizzato in un array livello per livello
Gli elementi nell'array non sono continui.
Albero binario completo vs albero binario completo:
Per un albero binario completo, ogni nodo ha 2 figli o 0 figli.
Esempio 1:
Un albero binario
Nell'albero binario dato non ci sono nodi di grado 1, né 2 né 0 figli per ogni nodo, quindi è un albero binario completo .
Per un albero binario completo, gli elementi vengono memorizzati livello per livello e non dal lato più a sinistra nell'ultimo livello. Quindi questo è non un albero binario completo . La rappresentazione dell'array è:
Elemento memorizzato in un array livello per livello
Esempio 2:
Un albero binario
Nell'albero binario dato non esiste nessun nodo di grado 1. Ogni nodo ha grado 2 o 0. Quindi è un albero binario completo .
Per un albero binario completo, gli elementi vengono memorizzati livello per livello e riempiti dal lato più a sinistra dell'ultimo livello. Quindi questo a albero binario completo . Di seguito è riportata la rappresentazione dell'array dell'albero:
Elemento memorizzato in un array livello per livello
Esempio 3:
Un albero binario
Nell'albero binario dato il nodo B ha grado 1 che viola la proprietà dell'albero binario completo, quindi lo è non un albero binario completo
mycricketlive
Per un albero binario completo, gli elementi vengono memorizzati livello per livello e riempiti dal lato più a sinistra dell'ultimo livello. Quindi questo è a albero binario completo . La rappresentazione array dell'albero binario è:
Elemento memorizzato in un array livello per livello
Esempio 4:
un albero binario
Nell'albero binario dato il nodo C ha grado 1 che viola la proprietà di un albero binario completo, quindi lo è non un albero binario completo
Per un albero binario completo, gli elementi vengono memorizzati livello per livello e riempiti dal lato più a sinistra dell'ultimo livello. Qui il nodo E viola la condizione. Quindi questo è non un albero binario completo .
convertire da stringa a intero Java
Creazione dell'albero binario completo:
Conosciamo un albero binario completo è un albero in cui, ad eccezione dell'ultimo livello (diciamo l )tutto l'altro livello ha ( 2l ) nodi e i nodi sono allineati da sinistra a destra.
Può essere rappresentato utilizzando un array. Se il genitore è indice io quindi il bambino sinistro è a 2i+1 e il bambino giusto è a 2i+2 .
Albero binario completo e sua rappresentazione in array
Algoritmo:
Per la creazione di a Albero binario completo , abbiamo bisogno di a Passo 1: Inizializza la radice con un nuovo nodo quando l'albero è vuoto.
Passo 2: Se l'albero non è vuoto, prendi l'elemento frontale
- Se l'elemento frontale non ha un figlio sinistro, imposta il figlio sinistro su un nuovo nodo
- Se il figlio destro non è presente, imposta il figlio destro come nuovo nodo
Passaggio 3: Se il nodo ha entrambi i figli allora pop dalla coda.
Passaggio 4: Accodare i nuovi dati.
Illustrazione:
Considera la matrice seguente:
1. Il primo elemento sarà la radice (valore nell'indice = 0 )
A viene preso come radice
xor in C++2. L'elemento successivo (all'indice = 1 ) sarà a sinistra e il terzo elemento (indice = 2 ) sarà il figlio giusto di root
B come figlio sinistro e D come figlio destro
3. quarto (indice = 3 ) e il quinto elemento (indice = 4 ) sarà il figlio sinistro e destro del nodo B
E e F sono figli sinistro e destro di B
4. Elemento successivo (indice = 5 ) sarà figlio di sinistra del nodo D
G diventa figlio sinistro del nodo D
Ecco come viene creato l'albero binario completo.
Implementazione: Per l'implementazione della costruzione di un albero binario completo dall'attraversamento dell'ordine dei livelli viene fornito questo post .
Applicazione dell'albero binario completo:
- Ordinamento heap
- Struttura dei dati basata sull'ordinamento dell'heap
Controlla se un dato albero binario è completo o meno: Seguire questo post per verificare se l'albero binario fornito è completo o meno.