Probablemente haya una manera más fácil, pero al menos lo siguiente funciona.
Representemos los nodos mediante una combinación de su profundidad y su índice a esa profundidad. Supongamos que comienza en el nodo [math] i [/ math], que es el nodo [math] j [/ math] (indexado a cero) en profundidad [math] d [/ math]. Deseamos encontrar el índice [math] i ‘[/ math] del niño izquierdo.
Primero, calcule cuántos nodos hay a cierta profundidad. Eso es fácil: [matemáticas] 2 ^ d [/ matemáticas]. Entonces, el número de nodos hasta (pero sin incluir) profundidad [matemática] d [/ matemática] es [matemática] 1 + 2 + 4 + \ ldots + 2 ^ {d-1} = 2 ^ d-1 [/ matemática ] De eso obtenemos la relación entre un índice [matemática] i [/ matemática] y su representación [matemática] (d, j) [/ matemática]: sabemos que [matemática] i (d, j) = 2 ^ d- 1 + j [/ matemáticas].
- ¿Existe una mejor complejidad que O (n log n) para ordenar?
- ¿Cuál es la diferencia entre un problema formal y solo un problema?
- ¿Qué tipo de algoritmos / pruebas / procedimientos analíticos se utilizan en el comercio minorista y para estudiar el comportamiento del consumidor?
- ¿Cómo está negando este código todos los números en mi matriz?
- ¿Cuáles son los algoritmos que se pueden usar en R para la predicción de datos categóricos?
Ahora regrese al nodo [math] i [/ math] que nos interesa. Hay nodos [math] j [/ math] en profundidad [math] d [/ math] cuyos hijos aparecerán antes que los de [math] yo [/ matemáticas]. Por lo tanto, el elemento secundario izquierdo del nodo [matemática] i [/ matemática] será el número de nodo [matemática] 2j [/ matemática] en profundidad [matemática] d + 1 [/ matemática].
Descubrimos antes cómo podríamos calcular el índice de un nodo dado a una profundidad dada. Al conectar [matemáticas] d + 1 [/ matemáticas] y [matemáticas] 2j [/ matemáticas] obtenemos
[matemáticas] i ‘= i (d + 1,2j) = 2 ^ {d + 1} -1 + 2j = 2 (2 ^ d-1 + j) +1 = 2i (d, j) +1 = 2i +1 [/ matemáticas].
