Recorrido de Arboles binarios en java

Hola buen día me pudieran ayudar con el siguiente programa en java utilizando arboles binarios el programa tiene que hacer lo siguiente:

Se da a conocer el recorrido en pre-orden de un determinado árbol binario el cual es es: GEAIBMCLDFKJH y también el recorrido en in-orden el cual es IABEGLDCFMKHJ.

En base a eso debemos diseña una función para dar el recorrido en post-orden dado el recorrido en pre-orden e in-orden donde el recorrido preorden es IBAEDLFCHJKMG pero se debe obtener dicho recorrido en un programa en Java.

Espero y puedan ayudarme de antemano muchas gracias buen dia.

Comentarios

Opciones de visualización de comentarios

Seleccione la forma que prefiera para mostrar los comentarios y haga clic en «Guardar las opciones» para activar los cambios.

Recursion

Analiza los recorridos en la wiki.
http://es.wikipedia.org/wiki/Recorrido_de_árboles

El recorrido preorden es de la forma Raíz,derecho e Izquierdo.
El recorrido en in orden derecho raíz e izquierdo
El recorrido post orden izquierdo derecho y raíz.

Tienes 1245367 en preorden y 4251637 en inorden ahora pasemos a postorden.

Propiedades el primer elemento de el recorrido preorden es siempre la raíz.
En el recorrido inorden la raíz divide a su derecha todos los nodos derecho y a la izquierda todos los nodos izquierdos.

Usemos estas dos propiedades para nuestro algoritmo.

El primer elemento del preorden es 1 por lo tanto usando el inorden dividimos.

425 1 637 ahora sabemos el tamaño del árbol izquierdo y del derecho por lo tanto dividamos en el preorden.

1 245 367 apliquemos las propiedades en dos sub árboles, 2 es el hijo izquierdo del 1 y 3 el hijo derecho.

Encontremos el tamaño de los sub árboles en el inorden.

4 2 5 y 6 3 7 , 4 es hijo izquierdo de 2 y 5 el derecho, 6 es hijo izquierdo 3 y 7 el hijo derecho.

apliquemos el recorrido post orden, primero izquierdos luego derecho y al último la raíz.

4 es izquierdo 2 es raíz y 5 es derecho,pasa a 452, 6 es izquierdo 3 es raíz y 7 derecho ,pasa a 673.

Tomando los anteriores 452 es izquierdo y 673 es derecho la raíz es 1 tenemos.

4526731.

Algoritmo

Postorden regresa en forma de cadena el recorrido Postorden de un árbol dado sus recorridos preorden e in orden en forma de cadenas.

PosicionDe dado dos cadenas regresa la posición de la primera ocurrencia de la segunda cadena en la primera.
PosiciónDe("123","2") es 1
[a...b] regresa una sub cadena de a hasta b.
"Hola"[0...2] regresa "Hol"

Postorden(preorden,inorden)
Si preorden es vacío regresa ""
Raíz = preorden[0]
EncuentraRaiz = posicionDe(inorden,Raíz)
Izquierdo = Postorden(preorden[0...EncuentraRaiz - 1],inorden[0,EncuentraRaiz - 1]
Derecho = Postorden(preorden[EncuentraRaiz +1 ... Fin] , inorden[EncuentraRaiz +1 ... Fin])
Regresa Izquierdo + Derecho + Raíz.