Solución:
Aquí hay otra sugerencia que facilitaría la solución a esta pregunta:
Si etiqueta los nodos con un índice en orden de amplitud, puede calcular el nivel sin ningún recorrido en el tiempo O (1). Entonces, si está haciendo varias consultas, puede hacer un O (N) BFT y hacer que cada consulta sea respondida en O (1) tiempo.
La fórmula para el nivel es:
level = floor(log(index + 1))
Donde está el tronco a la base 2
Pruébelo en este árbol:
0
/
/
1 2
/ /
/ /
3 4 5 6
Salud.
dejar i sea el índice que busca y n sea el número total de nodos.
Este algoritmo hace lo que quieras:
level = 0
while i != 0 do
i--
n = (n-1)/2
i = i%n
level++
done
0 es el índice de la raíz, si i = 0 entonces estás en el buen nivel, de lo contrario puedes quitar la raíz y obtienes dos subárboles n = (n-1)/2 actualiza el número de nodos es el nuevo árbol (que es un subárbol del antiguo) y i = i%n selecciona solo el subárbol bueno.
Parece que caminar directamente sobre el árbol debería ser lo suficientemente eficiente.
En cada paso del algoritmo, tenga en cuenta el rango de los índices en el subárbol del nodo en el que se encuentra. El primer valor del rango es el nodo raíz, y luego la primera mitad es el rango del subárbol de la izquierda, y la segunda mitad debe ser el rango del subárbol derecho. Luego puede moverse recursivamente hacia abajo hasta que encuentre su nodo.
Por ejemplo, busquemos en un árbol de 4 niveles con 15 elementos
(root node)(left elements)(right elements)
Starting range: (0)(1 2 3 4 5 6 7)(8 9 10 11 12 13 14)
Go left : (1)(2 3 4)(5 6 7)
Go right : (5)(6)(7)
Found node, total depth 2
Debería poder hacer esto con un ciclo simple, usando solo un par de variables para almacenar el inicio y el final de los rangos. También debería poder adaptar esto fácilmente si realiza algunos cambios menores, como usar el recorrido posterior / previo / en orden o iniciar los índices desde 1 en lugar de 0.