Hola!

Me surgió esta duda:

Si me dan el recorrido el posorden de un árbol que no sea una operación algebraica, por ejemplo: d h k l i e b f j g c a. ¿Cómo lo reconstruyo? Si fuese una operación algebraica, es muy fácil reconstruirlo pensandolo como una calculadora en polaca inversa, pero esto me cagó.

El ejemplo es éste arbol:

el recorrido en posorden si no recuerdo se basa en tener en cuenta esto:
"hijo izquierdo, hijo derecho, raiz". Es decir, nombras primero al hijo izquierdo, luego al derecho, y luego a la raiz.
EN tu ejemplo:

Tenes la raiz a, entonces buscas el hijo izquierdo "b", pero este a su vez tiene hijos, asique no lo podes nombrar.
Buscas su hijo izquierdo, y es "d" asique lo nombras. Siguiendo el algoritmo, viene el hijo derecho de "b", que es "e". Pero este tiene hijos; no lo podes nombrar, asique buscas su hijo derecho. Este es "h", asique lo nombras.
Por ahora tenes : d h
Buscas el hijo derecho de "e", siendo este "i", pero como tiene hijos, buscas el hijo izquierdo. Este es "k", lo nombras, y el hijo derecho es "l". Tambien lo nombras.
Como nombraste los 2 hijos, podes nombrar al padre, que es "i".
Hasta ahora tenes : D H K L I

Como nombraste los 2 hijos de "e" (el izquierdo h y el derecho i) podes nombrarlo. Entonces nombras a "e". Del mismo modo, nombraste los 2 hijos de "b", asique lo nombras.
Ahora tenes: D H K L I E B
A todo esto ya nombraste al "hijo izquierdo" de la raiz "a" (que resulto ser todo ese subarbol) asique ahora buscas el hijo derecho de "a"
Este pasa a ser C, pero "c" tiene hijos, asique primero debes nombrar su hijo izquierdo y luego el derecho.
Nombras asi a su hijo izquierdo "f" y luego su hijo derecho, pero este tambien tiene hijos ! "g" tiene hijos, asique debes nombrar a su hijo izquierdo y luego al derecho. Como hay un solo hijo, lo nombras. Nombras asi a "j" y luego a "g".
Ahora tenes: D H K L I E B F J G
como nombraste los 2 hijos de "c" lo podes nombrar. Asique nombras "c"
Ya tenes los 2 hijos (el izquierdo y derecho) de la raiz "a" asique la nombras.
Y te queda el recorrido: D H K L I E B F J G C A

creo que era asi
Una explicacion general seria asi:
La notacion consiste en nombrar al hijo izquierdo, hijo derecho, padre. Si uno de los hijos es raiz de un sub arbol, lo apartas (consideras solo ese subarbol) y aplicas nuevamente la tecnica "hijo izquierdo, hijo derecho, padre". Y hubiese un hijo que a su vez es raiz de un subarbol, seguis aplicando. Considera que no podes nombrar esas "raices" de esos "subarboles" hasta no haber nombrado sus hijos izquierdos y derechos.

Espero que te sirva

Esta buena la generalización, pero la duda en realidad era cómo reconstruir el arbol a partir del recorrido

la puta, eso pasa por leer mal xD

---

dudo que tomen algo asi; necesitas algun dato mas como saber cuales son hijos y cuales no..
Porque si no no sabes donde "partir" para aplicar "este es hijo derecho, este izquierdo, este padre"
en una algebraica justamente es facil, porque sabes que los operadores son padres siempre (nunca hijos) y ahi aplicas para recuperar el arbol

Listo, esa es la respuesta uqe necesitaba, gracias!

Me da la impresión que para ese tipo de ejercicios hay varias respuestas, ya que el que sea n-ario significa que n es la máxima cantidad de hijos que pueden alcanzar los elementos del árbol, en ningun momento te indica cuantos hijos debe tener cada elemento (ya que tampoco es regular), asi que hay muchos árboles que cumplan con la condición de no sobrepasar los n-hijos.
Mirando los finales no encontré ningun ejercicio como el que pusiste, todos son con operaciones. Lo más parecido que vi es el ejercicio 52 de la página 282 del libro, pero ahi te dice cuantos hijos debe tener cada letra.

Claro, justamente, en esa página te dice cuántos hijos debe tener cada letra, entonces ya sabes cuáles son padres y cuales son hijos. Al igual que con las operaciones algebraicas, uno sabría cuáles son los padres y cuáles son los hijos (los padres son las operaciones, los hijos los números).

Está interesante, nunca se tomó, aunque lo podrían tomar porque no es nada del otro mundo si te dan la cantidad de hijos.

Y si no te la dan, es dibujo libre

Claro.. porque hay muchos (infinitos? no creo) arboles posibles con ese recorrido.

claro jaja
a lo sumo lo unico con certeza que podes sacar es que "a" va a ser la raiz

sisi jaja.. esta interesante el tema, si algún dia me interesan los grafos (nunca) estaría bueno probar cuántos posibles arboles binarios con ese recorrido habrían

jaja, yo AME discreta jajajaja
si la profesora no se cambiaba de turno, iba de cabeza como ayudante jajajaa xD

Bueno, aprovecho el thread para poner otra cosa.

En mayo pusieron este ejercicio:



Es obvio que sí, que es posible recorrerlo. El tema es que en la respuesta justifica diciendo sólo se puede recorrer en simétrico si es binario. ¿Porqué? No se puede usar para árboles ternarios por ejemplo? (no se, imaginemonos la suma con 3 hijos, sumarías los 3 hijos entre sí).

saludos

no, porque seria una operacion en la calculadora no realizable
vos lo pensas en tu cabeza, con lo que sabes de suma "claro, sumo los 2 primeros, y el resultado con el 3ro" pero si representas eso en un arbol te da algo asi como este dibujo:

que es binario

Eso seria para tu ejemplo particular; para el del ejercicio, son operaciones binarias (el +, - * y /) osea que usan 2 operandos; osea que el arbol no puede tener 3 hijos porque implica 3 operandos, lo cual es imposible para esos operadores
aclaro qeu conteste todo sin recordar cual era el orden posterior y el simetrico jaja

---

no confundas el que haya 3 numeros para sumar con la cantidad de operandos: el + es operacion binaria, osea que requiere 2 operandos.
Si sumas 3 numeros haces 2 veces la operacion, y su representacion sera como el dibujo q te hice
no podes hacer 3+ 5 + 7 (osea, sumar los 3 numeros de una), sino que haces (3+5)+7 (primero 3+5 y luego el resutlado +7)
Como la suma es asociativa a izquierda, por eso al hacer 3+5+7 es lo mismo que (3+5)+7 (tambiene s lo mismo si pongo 3+(5+7) porque es conmutativa , pero bueno, suponete que no fuese conmutativa)

---

mm nose si respondi tu pregunta jajaj
se me mezcla AM2 con discreta

Si, me olvidé que son operaciones binarias, esa es la justificación de porqué no se puede recorrer algo con 3 hijos en usual.