Si el recorrido de orden posterior de un árbol binario es DEBFCA, ¿cómo puedo encontrar el recorrido de orden previo?

Debería haber publicado la pregunta original tal como se la plantearon: una pregunta de opción múltiple para determinar el postorder, dado el preorden. Vea, en general no es posible determinar la forma de un árbol binario basado solo en los recorridos de preorden y postorder. Sin embargo, dado que no todos los postorder son consistentes con un preorden dado, puede seleccionar la opción que funcione a partir de las opciones que se le ofrecen.

Entonces, la pregunta relevante es dar un algoritmo para determinar si un recorrido previo al pedido y un recorrido postorder dado son consistentes entre sí; es decir, si existe al menos un árbol con esos recorridos.

Primero, notamos que el primer nodo del preorden y el último nodo del postorder deben coincidir porque ese nodo es la raíz del árbol. Si no existe tal coincidencia, los recorridos son inconsistentes. Entonces, si pre [0]! = Post [n-1], devuelve falso.

Ahora hay tres casos: el nodo raíz tiene cero, uno o dos hijos.

El caso de cero hijos es trivial, ya que solo es posible un árbol, que consiste solo en la raíz. Devuelve verdadero en este caso.

Si tiene un hijo, no puede determinar si es un hijo izquierdo o derecho; esta es precisamente la razón por la que no siempre puede determinar la forma del árbol por completo a partir de los dos recorridos. Sin embargo, ya sea un hijo izquierdo o derecho, esperamos que en este caso el penúltimo nodo del postorder coincida con el segundo nodo del preorden.

Entonces, si detectamos que pre [1] == post [n-2], creamos un nodo raíz a partir de pre [0] y le adjuntamos (como hijo izquierdo o derecho) la solución para (pre [1 … n -1], publicar [0 … n-2]). Si no se puede encontrar una solución para este subcase, tampoco hay una solución general.

Si pre [1]! = Post [n-2], puede haber un subárbol izquierdo y derecho. Si ese es el caso, debería haber algún índice x> = 1 y

Según las ideas anteriores, es sencillo codificar una solución.

Dado que Root es el último nodo que se atraviesa en un recorrido de orden posterior, sabemos una cosa con certeza. A es la raíz.
A continuación, solo nos queda DEBFC. Aquí algunos de los nodos pertenecen al lado izquierdo del árbol binario y algunos pertenecen al lado derecho. Cuántos nodos pertenecen a la izquierda y cuántos pertenecen a la derecha. Dado que el lado izquierdo del árbol binario se considera primero, y dado que se espera que cada nodo tenga como máximo dos hijos, DEB será el lado izquierdo del árbol binario y FC sería el derecho.
Ahora, sabemos que FC está en el lado derecho del árbol binario. Nuevamente, el último nodo sería la raíz del subárbol y F su lado izquierdo.
Luego llegamos al lado izquierdo del árbol binario y es DEB. De nuevo B sería la raíz del subárbol. D y E son sus lados izquierdo y derecho respectivamente. Por lo tanto, el árbol binario se vería más o menos así dado a continuación.
Después de construir el árbol binario, escribir el recorrido previo al pedido es muy simple. En preorden, la raíz transversal es lo primero. Como A es la raíz, A aparecerá primero. La raíz siguiente sería el subárbol izquierdo y derecho y, por lo tanto, el subárbol izquierdo sería BDE. Nuevamente, B sería la raíz del subárbol izquierdo seguido de D y E, que son los hijos izquierdo y derecho, respectivamente. Por lo tanto, el recorrido previo al pedido hasta ahora sería ABDE. Por último viene el subárbol derecho. Aquí nuevamente C sería la raíz del subárbol derecho seguido de C su hijo izquierdo. Por lo tanto, todo el recorrido previo al pedido del árbol sería ABDECF .

Estoy de acuerdo en que la raíz será A , pero qué pasa si el lado izquierdo es DE y el derecho como BFC . en este caso el árbol se vería así:
-UNA
-E -C
D B F

y entonces el recorrido de preorden será: AEDCBF

En el recorrido de orden posterior, atravesamos como

PARTE IZQUIERDA-> PARTE DERECHA-> RAÍZ

Entonces, según DEBFCA como orden postal, el árbol sería:

Luego, desde el árbol, de acuerdo con el recorrido previo al pedido, atravesamos como raíz, lado izquierdo, lado derecho. Así que preordenamos como: ABDECF

Método transversal en orden:
1. Visita el subárbol izquierdo
2. Procesar el nodo actual
3. Visite el subárbol derecho

Método transversal de preorden:
1. Nodo actual del proceso
2. Visita el subárbol izquierdo
3. Visite el subárbol derecho

Método de recorrido posterior al pedido:
1. Visita el subárbol izquierdo
2. Visite el subárbol derecho
3. Procesar el nodo actual

Entonces Ur caso DEBFCA

entonces el padre es A

Ahora viene de izquierda a derecha, entonces (DEB) y (FC)

De nuevo en (DEB) B es el padre D si Izquierda y E es el hijo derecho.

Lo mismo en (FC) C es padre y F es hijo correcto.

Ahora combinando todo por las reglas anteriores

el padre A está a la izquierda B y a la derecha C (ABC).

Nuevamente venga al Nodo primario izquierdo B es (ED)

No, finalmente C tiene solo una F

Ahora la serie final es ABCDEF

no puede construir un BT único con solo un pedido posterior, por lo que no puede encontrar el recorrido del pedido posterior de ese BT.

con solo el pedido por correo habrá múltiples soluciones.

para un BT único, debe tener cualquiera de estas combinaciones.

1. pre pedido + en orden
2. publicar pedido + en orden
3. pre pedido + en orden + post pedido

Hay múltiples equivalentes de preorden de este recorrido postorder. No puede distinguir solo las letras cuál era la estructura de árbol original, porque no hay paréntesis que agrupen las letras.

Deberá dibujar el árbol en papel, que produce ese recorrido de orden posterior y ejecutarlo manualmente en un recorrido previo.

no puedes, también necesitas el recorrido en orden