¿Qué combinaciones de secuenciación previa, posterior y en orden son únicas?

28

Sabemos post-orden,

post L(x)     => [x]
post N(x,l,r) => (post l) ++ (post r) ++ [x]

y pre-orden

pre L(x)     => [x]
pre N(x,l,r) => [x] ++ (pre l) ++ (pre r)

y transversales en orden resp. secuencialización

in L(x)     => [x]
in N(x,l,r) => (in l) ++ [x] ++ (in r)

Se puede ver fácilmente que ninguno de los dos describe un árbol dado de manera única, incluso si asumimos claves / etiquetas distintas por pares.

¿Qué combinaciones de las tres se pueden usar para ese fin y cuáles no?

Las respuestas positivas deben incluir un algoritmo (eficiente) para reconstruir el árbol y una prueba (idea) de por qué es correcto. Las respuestas negativas deben proporcionar ejemplos contrarios, es decir, diferentes árboles que tienen la misma representación.

Rafael
fuente

Respuestas:

16

Primero, asumiré que todos los elementos son distintos. Ninguna cantidad de secuenciaciones le dirá la forma de un árbol con elementos [3,3,3,3,3]. Es posible reconstruir algunos árboles con elementos duplicados, por supuesto; No sé qué condiciones agradables existen suficientes.

Continuando con los resultados negativos, no puede reconstruir completamente un árbol binario a partir de su secuenciación previa y posterior. [1,2]preordenar, el orden [2,1]posterior debe tener 1en la raíz, pero 2puede ser el hijo izquierdo o el hijo derecho. Si no le importa esta ambigüedad, puede reconstruir el árbol con el siguiente algoritmo:

  • [x1,,xn][yn,,y1]x1=y1
  • x2y2x2=y2[x2,,xn][yn,,y2]
  • ijx2=yiy2=xj[x2,,xj1][xj,,xn]j2=ni+1i2=nj+1
    j2

O(n2)Θ(n2)O(nlg(n))nlg(n)

[x1,,xn][z1,,zn]

  • x1
  • kzk=x1[z1,,zk1][zk+1,,zn][x2,,xk][xk+1,,xn]

O(n2)O(nlg(n))

El orden posterior más el orden es, por supuesto, simétrico.

Gilles 'SO- deja de ser malvado'
fuente
¿Hay un error tipográfico aquí: "[1,2] preordenar, [1,2] el orden posterior debe tener 1 en la raíz, pero 2 puede ser el hijo izquierdo o el derecho". árbol sería [2,1] no [1,2] si 2 es un hijo izquierdo o derecho. Además, ¿quiere decir que si se dan tanto el preorden como el postorder, no podemos reconstruir el árbol, o quiere decir que si solo se nos da uno de ellos, entonces no podemos reconstruir el árbol?
CEGRD
@CEGRD De hecho, el postorder fue un error tipográfico. El ejemplo muestra que no puede reconstruir completamente el árbol en este caso: no puede saber si 2es un hijo izquierdo o un hijo derecho. Esto corresponde al caso del "subárbol único" del algoritmo de reconstrucción.
Gilles 'SO- deja de ser malvado'
¿Cómo cambia esto si sabemos que es un árbol de búsqueda binaria? para el caso simple en su ejemplo ([1,2] preordenar, [2,1] orden posterior) podríamos determinar que la raíz es 1 y que 2 es el hijo correcto (porque 2 es mayor que 1) ... ¿Derecha?
fersarr