albero binario rappresentata utilizzando matrice

Question

consideri il seguente matrice, che viene rivendicata abbia rappresentato un albero binario:

[1, 2, 5, 6, -1, 8, 11]

Dato che la indice con valore -1 indica l'elemento radice, ho le seguenti domande:

a) Come è rappresentato questo in realtà?

Dovremmo seguire le seguenti formule (source from this link) per capire l'albero? Tre semplici formule consentono di passare da l'indice del genitore per l'indice dei suoi figli e viceversa:

* if index(parent) = N, index(left child) = 2*N+1 
* if index(parent) = N, index(right child) = 2*N+2 
* if index(child) = N, index(parent) = (N-1)/2 (integer division with truncation) 

Se usiamo formule di cui sopra, quindi indice (root) = 3, indice (Child Left) = 7, che non esiste.

b) È importante sapere se si tratta di un albero binario completo o no?

Answer 1

Dato un array, è possibile pensare a un numero qualsiasi di modi in cui tale array può rappresentare un albero binario. Quindi non c'è modo di sapere, devi andare alla fonte di quell'array (qualunque cosa sia).

Uno di questi è il modo in cui l'heap binario viene solitamente rappresentato, come per il collegamento. Se questa fosse la rappresentazione usata, -1 non sarebbe l'elemento radice. E il nodo in posizione 3 non avrebbe figli, cioè sarebbe una foglia.

E, sì, probabilmente è importante sapere se si suppone che sia un albero completo o no.

In generale, non si dovrebbe cercare di capire che cosa significano alcuni dati come questo. Dovresti ricevere la documentazione o il codice sorgente che utilizza i dati. Se non lo hai e hai davvero bisogno di decodificarlo, è molto probabile che tu debba saperne di più sui dati. L'osservazione del comportamento del codice che la usa dovrebbe aiutarti. O decompilando il codice.

Answer 2

Potrebbe non essere un albero binario completo, ma potrebbe anche non essere arbitrario. Puoi rappresentare un albero in cui mancano al massimo alcune delle foglie più a destra (o, se scambi la convenzione per i bambini di sinistra e di destra, al massimo mancano alcune delle foglie più a sinistra).

Non si può rappresentare questo nella propria matrice:

A 
/\ 
    B C 
//
D E 

Ma si può rappresentare questa

A 
/\ 
    B C 
/\ 
D E 

o questo:

A 
/\ 
    B C 
    /\ 
    D E 

(per l'ultimo, hanno 2k +1 essere a destra bambino e 2k + 2 il lasciato bambino)

È necessario conoscere solo il numero di nodi nei tre.

Answer 3

N = 0 deve essere il nodo radice poiché dalle regole elencate non ha genitore. 0 non può essere creato da nessuna delle espressioni (2 * N + 1) o (2 * N + 2), assumendo nessun N. negativo

Nota, l'indice non è il valore memorizzato nell'array, è il punto nell'array. Per [1, 2, 5, 6, -1, 8, 11] Indice 0 = 1 N 1 = 2 N 2 = 5, ecc

Se è un albero completo, allora -1 è un valore valido e albero è

1 
/\ 
    2 5 
/\/\ 
6 -1 8 11 

-1 potrebbe anche essere un puntatore "NULL", indicante nessun valore presente in tale nodo.

Così l'albero sarebbe simile

1 
/\ 
    2 5 
//\ 
6 8 11