Binary Tree representado usando array

Question

Considere la siguiente matriz, que se afirma que se han representado un árbol binario:

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

Dado que la índice con valor -1 indica el elemento raíz, tengo preguntas a continuación:

a) ¿Cómo se representa esto realmente?

¿Deberíamos seguir las siguientes fórmulas (source from this link) para descubrir el árbol? tres fórmulas simples permiten que pase a partir del índice de la matriz con el índice de sus hijos y 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) 

Si utilizamos las fórmulas anteriores, entonces el índice (de raíz) = 3, índice (hijo izquierdo) = 7, que no existe.

b) ¿Es importante saber si es un árbol binario completo o no?

Answer 1

Dada una matriz, se podría pensar de varias maneras cómo podría esa matriz representar un árbol binario. Entonces no hay forma de saber, tienes que ir a la fuente de esa matriz (lo que sea que sea).

Una de esas formas es la forma en que generalmente se representa el montón binario, según su enlace. Si esta fue la representación utilizada, -1 no sería el elemento raíz. Y el nodo en la posición 3 no tendría hijos, es decir, sería una hoja.

Y, sí, probablemente sea importante saber si se supone que es un árbol completo o no.

En general, no debe tratar de averiguar qué significan algunos datos como este. Debería recibir documentación o el código fuente que usa los datos. Si no tiene eso y realmente necesita una ingeniería inversa, lo más probable es que necesite saber más sobre los datos. Observar el comportamiento del código que lo usa debería ayudarte. O descompilando el código.

Answer 2

Puede que no sea un árbol binario completo, pero tampoco puede ser arbitrario. Puede representar un árbol en el que, como mucho, faltan algunas de las pocas hojas de la derecha (o, si cambia la convención para niños de izquierda y derecha, como mucho algunas de las hojas de la izquierda faltantes).

No se puede representar esto en su conjunto:

A 
/\ 
    B C 
//
D E 

Pero se puede representar este

A 
/\ 
    B C 
/\ 
D E 

o esto:

A 
/\ 
    B C 
    /\ 
    D E 

(para el último, tienen 2k +1 sea el derecho hijo y 2k + 2 el dejado hijo)

Solo necesita saber la cantidad de nodos en los tres.

Answer 3

N = 0 debe ser el nodo raíz ya que según las reglas enumeradas, no tiene padre. 0 no se puede crear a partir de ninguna de las expresiones (2 * N + 1) o (2 * N + 2), suponiendo que no haya una N negativa.

Nota, el índice no es el valor almacenado en la matriz, es el lugar en la matriz. Para [1, 2, 5, 6, -1, 8, 11] Índice 0 = 1 Índice 1 = 2 Índice 2 = 5, etc.

Si es un árbol completo, entonces -1 es un valor válido y el árbol es

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

-1 también podría ser un puntero "NULL", indica que no hay valor existe en ese nodo.

Así que el árbol se vería como

1 
/\ 
    2 5 
//\ 
6 8 11