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.
- darkcommander's blog
- Inicie sesión o regístrese para enviar comentarios
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.