¿Se puede identificar de forma única la estructura de un "árbol binario completo", ser identificado de forma única si solo se dan sus viajeros de pre-pedido o post-pedido o en orden?

Question

No puedo razonar si podemos construir un árbol binario completo si solo se da uno de los siguientes 3 travessals: pre-orden, post-pedido, en orden.

La siguiente es la definición de un árbol binario completo:

Un árbol binario completo es un árbol binario en el que cada nivel, excepto posiblemente el último, está completamente lleno, y todos los nodos están lo más lejos posible.

La definición anterior ha sido tomada de este enlace: https://web.cecs.pdx.edu/~SHEARD / CURSO / CS163 / DOC / FullVSCOMPLETE.HTML

Sería útil Si alguien puede probar o explicar intuitivamente por qué podemos o no podemos construir de manera única un árbol binario completo si solo se da uno de sus 3 travesss.

Answer 1

Dado $ n $ , Hay solo una forma para un árbol binario completo (CBT) con $ n $ nodos.

Para cualquier recorrido determinista, la correspondencia entre la posición de un nodo en una CBT y su posición durante el recorrido de ese CBT está completamente fijado. Entonces, si se da un recorrido determinista, podemos reconstruir la TCC de forma única. Esto se aplica no solo a ninguno de los travesaños de pre-orden, post-pedido o en orden, también se aplica a la respiración: primero Travesional (con el niño izquierdo visitado ante el niño derecho), o cualquier otro recorrido determinista como se mencionó. por Hendrik Jan en su comentario .

Aquí hay un ejemplo. La forma anterior es la única forma para una TCT con 12 nodos, que son, 1 raíz (en profundidad 0), 2 nodos en profundidad 1, 4 nodos en profundidad 2 y 5 nodos en profundidad 3. Un recorrido previo a pedido de eso CBT visita los nodos en el siguiente orden.

1. el nodo raíz.
2. El primer nodo de profundidad 1.
3. El primer nodo de profundidad 2.
4. El primer nodo de profundidad 3.
5. el segundo nodo de profundidad 3.
6. el segundo nodo de profundidad 2.
7. El tercer nodo de profundidad 3.
8. el cuarto nodo de profundidad 3.
9. el segundo nodo de profundidad 1.
10. El tercer nodo de profundidad 2.
11. el quinto nodo de profundidad 3.
12. el cuarto nodo de profundidad 2.

Dar la lista anterior, sabemos que el nodo raíz es el 1 ^{st visitado, el primer nodo de profundidad 1 es el 2 nd -node visitado ,. .., el cuarto nodo de profundidad 3 es el 8 th -node visitado y el quinto nodo de profundidad 3 es el 11 TH -node visitado.}