Pre-orden + post-orden para ordenar

11

Tarea

Dados los recorridos de orden previo y posterior de un árbol binario completo, devuelva su recorrido en orden.

Los recorridos se representarán como dos listas, ambas con n enteros positivos distintos, cada uno identificando un nodo de forma única. Su programa puede tomar estas listas y generar el recorrido en orden resultante, utilizando cualquier formato de E / S razonable.

Puede suponer que la entrada es válida (es decir, las listas en realidad representan recorridos de algún árbol).

Este es el , por lo que gana el código más corto en bytes.

Definiciones

Un árbol binario completo es una estructura finita de nodos , representada aquí por enteros positivos únicos.

Un árbol binario completo es una hoja , que consta de un solo nodo :

                                      1

O una rama , que consiste en un nodo con dos subárboles (llamados los subárboles izquierdo y derecho ), cada uno de los cuales es, a su vez, un árbol binario completo:

                                      1
                                    /   \
                                  …       …

Aquí hay un ejemplo completo de un árbol binario completo:

                                        6
                                      /   \
                                    3       4
                                   / \     / \
                                  1   8   5   7
                                     / \
                                    2   9

El recorrido de preorden de un árbol binario completo se define de forma recursiva de la siguiente manera:

  • El recorrido de preorden de una hoja que contiene un nodo n es la lista [ n ].
  • El recorrido de preorden de una rama que contiene un nodo ny subárboles (L, R) es la lista [ n ] +  preordenar ( L ) +  preorder ( R ), donde + es el operador de concatenación de lista.

Para el árbol anterior, eso es [6, 3, 1, 8, 2, 9, 4, 5, 7] .


El recorrido de orden posterior de un árbol binario completo se define de forma recursiva de la siguiente manera:

  • El recorrido de orden posterior de una hoja que contiene un nodo n es la lista [ n ].
  • El recorrido postorden de una rama que contiene un nodo n y sub-árboles (L, R) es la lista de orden posterior ( L ) +  postorden ( R ) + [ n ].

Para el árbol anterior, eso es [1, 2, 9, 8, 3, 5, 7, 4, 6] .


El recorrido en orden de un árbol binario completo se define de forma recursiva de la siguiente manera:

  • El recorrido en orden de una hoja que contiene un nodo n es la lista [ n ].
  • El recorrido en orden de una rama que contiene un nodo n y sub-árboles (L, R) es la lista finde ( L ) + [ n ] +  finde ( R ).

Para el árbol anterior, eso es [1, 3, 2, 8, 9, 6, 5, 4, 7] .


En conclusión: dado el par de listas [6, 3, 1, 8, 2, 9, 4, 5, 7] (pre) y [1, 2, 9, 8, 3, 5, 7, 4, 6] (post) como entrada, su programa debería generar [1, 3, 2, 8, 9, 6, 5, 4, 7] .

Casos de prueba

Cada caso de prueba está en el formato preorder, postorder → expected output.

[8], [8] → [8]
[3,4,5], [4,5,3] → [4,3,5]
[1,2,9,8,3], [9,8,2,3,1] → [9,2,8,1,3]
[7,8,10,11,12,2,3,4,5], [11,12,10,2,8,4,5,3,7] → [11,10,12,8,2,7,4,3,5]
[1,2,3,4,5,6,7,8,9], [5,6,4,7,3,8,2,9,1] → [5,4,6,3,7,2,8,1,9]
Lynn
fuente
Como se garantiza que la entrada tendrá una forma específica (un árbol binario completo), realmente no necesita ambas entradas, ¿verdad?
feersum
El árbol binario está lleno , pero no está completo , por lo que un árbol de elementos n puede tener muchas formas y, en general, necesita ambos.
Lynn
¿Puedo representar los nodos como letras individuales que dan cadenas para las órdenes? Por ejemplo, el segundo ejemplo se convertiría en: "CDE" and "DEC" give "DCE"? (incluso usando letras unicode si necesito muchos nodos)
Ton Hospel
@TonHospel Estaría de acuerdo con eso; posiblemente, todo lo que está haciendo es ampliar un poco la definición de una lista de enteros , porque "CDE"no es muy diferente de [67, 68, 69]:)
Lynn

Respuestas:

2

Perl, 69 66 62 56 53 bytes

Incluye +1 para -p

Toma el postorder seguido de preorder como una línea separada por espacio en STDIN (observe el orden de pre y post). Los nodos se representan como letras únicas (cualquier carácter que no sea espacio o nueva línea está bien).

inpost.pl <<< "98231 12983"

inpost.pl:

#!/usr/bin/perl -p
s%(.)(.)+\K(.)(.+)\3(\1.*)\2%$4$5$3$2%&&redo;s;.+ ;;

El uso del formato original puramente numérico necesita mucho más cuidado para identificar exactamente un solo número y viene en 73 bytes

#!/usr/bin/perl -p
s%\b(\d+)(,\d+)+\K,(\d+\b)(.+)\b\3,(\1\b.*)\2\b%$4$5,$3$2%&&redo;s;.+ ;;

Usar como

inpostnum.pl <<< "11,12,10,2,8,4,5,3,7 7,8,10,11,12,2,3,4,5"
Ton Hospel
fuente
-pagrega un ;al final, por lo que no necesita el último ;. s;.* ;;->s;.* ;
Riley
@Riley lo sé. Es por eso que tengo el ;al final. Pero -p en realidad se agrega \n;al final en un -eprograma. En un archivo agrega solo ;si y solo si el archivo no termina \n. Como quiero reclamar -pcomo +1 y no como +3, el programa debe funcionar desde la línea de comandos, así que con -e. Y no quiero la nueva línea espuria en la salida que luego obtendría
Ton Hospel
Si lo ejecutas en la línea de comandos, ¿no lo necesitas '? Si lo ejecuta de la manera en que lo tiene (llame a un archivo <<<), puede dejar el último ;apagado.
Riley
@Riley Depende de la interpretación del método de puntuación para perl. Por lo general, envío mi código como un archivo, ya que creo que es menos efímero. Pero si miras mis presentaciones verás que si el código debe estar en un archivo (porque, por ejemplo, tiene 'o usa, do$0etc.) siempre puntúo -pcomo +3 (espacio, menos, p), pero si el código también funcionaría en la línea de comando donde obtienes el -ey el 'gratis Lo +1e
califico
De acuerdo, simplemente no estaba claro exactamente cómo puntúan las presentaciones de línea de comando. No me di cuenta de que obtienes 'gratis. Gracias por aclarar eso.
Riley
3

Haskell, 84 83 bytes

(a:b:c)#z|i<-1+length(fst$span(/=b)z),h<- \f->f i(b:c)#f i z=h take++a:h drop
a#_=a
dianne
fuente
2

JavaScript (ES6), 100 bytes

f=(s,t,l=t.search(s[1]))=>s[1]?f(s.slice(1,++l+1),t.slice(0,l))+s[0]+f(s.slice(l+1),t.slice(l)):s[0]

I / O está en cadenas de caracteres "seguros" (por ejemplo, letras o dígitos). Enfoque alternativo, también 100 bytes:

f=(s,t,a=0,b=0,c=s.length-1,l=t.search(s[a+1])-b)=>c?f(s,t,a+1,b,l)+s[a]+f(s,t,l+2+a,l+1,c-l-2):s[a]
Neil
fuente