A2- Posible impugnación: Pregunta 16 bloque III

[scutums]

Buenas, a ver si me podéis echar una mano con la pregunta 16 del Bloque III.

16. Dado un árbol binario, cuyo recorrido en pre-orden es "Redhat, Debian, Fedora, Mandriva, Archilinux", ¿cuál de las siguientes opciones podría ser un recorrido en in-orden?
a) Fedora, Archilinux, Debian, Mandriva, Redhat.
b) Fedora, Debian, Archilinux, Mandriva, Redhat.
c) Debian, Fedora, Redhat, Archilinux, Mandriva.
d) Debian, Mandriva, Fedora, Archilinux, Redhat.

Se da por buena la opción C, pero por lo que estoy viendo, y por mi criterio, ninguna encajaría.
Según tengo entendido, un recorrido en pre-orden en un árbol binario empieza por la raíz, a continuación pasa por el subárbol izquierdo, y luego por el derecho. Por tanto el árbol que estamos recorriendo sería algo así:
1.Redhat
/ \
1.1.Debian 1.2.Archilinux
/ \
1.1.1.Fedora 1.1.2.Mandriva

A continuación, un recorrido in-orden pasaría por subárbol izquierdo, raíz y subárbol derecho; por tanto, mi solución para un recorrido in-orden sería: "Fedora, Debian, Mandriva, Redhat, Archilinux".

¿Qué opinaís? ¿Qué solución habéis dado vosotros?

[phdezv]

Yo estoy de acuerdo 100% contigo, no la respondí porque no me cuadraban las respuestas y tampoco quería perder mucho tiempo comprobando mi "habilidad" con los árboles

[reventador]

Prueba con el árbol que se monta con esta estructura y verás como sí que es la C la respuesta correcta.

Raíz = Redhat (1)
Hijo izquierdo del (1) = Debian (2)
Hijo derecho del (2) = Fedora (3)
Hijo derecho del (1) = Mandriva (4)
Hijo izquierdo del (4) = Archilinux (5)

Saludos.

[grincho]

Yo creo que es impugnable porque son válidas tanto la c como la d. La c con el árbol que se ha puesto en el post anterior y la d con un árbol así:
Raíz = Redhat (1)
Hijo izquierdo del (1) = Debian (2)
Hijo derecho del (2) = Fedora (3)
Hijo izquierdo del (3) = Mandriva (4)
Hijo derecho del (3) = Archilinux (5)

Saludos

[txaved]

Buenas

Sobre el árbol que propones, scutums, evidentemente ninguna respuesta encaja. Pero estás asumiendo que es el único árbol que responde a ese recorrido pre-orden. Entiendo que debemos buscar uno que cumpla ese recorrido pre-orden y uno de los recorridos in-orden entre las respuestas dadas. Y que además solo lo cumpla una de ellas, que es lo que no acabo de tener claro.

Por un lado tenemos la opción que dan como correcta, la c), cuyo árbol es el que propone reventador, y que encaja bien con los dos recorridos.
Por otro lado, el árbol de grincho, que encaja bien con el recorrido pre-orden del enunciado y con el recorrido in-orden de la respuesta d).
A mi se me había ocurrido otro árbol en el examen que encajaría con el recorrido in-orden de la respuesta b). Es el siguiente:

Raiz = Redhat (1)
Hijo izquierdo del (1) = Debian (2)
Hijo izquierdo del (2) = Fedora (3)
Hijo derecho del (2) = Mandriva (4)
Hijo izquierdo del (4) = Archilinux (5)

La única duda que se me plantea es si un árbol binario tiene alguna restricción del tipo que no pueda ser nulo ninguno de sus subárboles o similar. En cuyo caso, ni mi propuesta ni la de grincho serían válidas.

¿Alguien puede darnos su opinión?

Un saludo.

[scutums]

Buenas

Sobre el árbol que propones, scutums, evidentemente ninguna respuesta encaja. Pero estás asumiendo que es el único árbol que responde a ese recorrido pre-orden. Entiendo que debemos buscar uno que cumpla ese recorrido pre-orden y uno de los recorridos in-orden entre las respuestas dadas. Y que además solo lo cumpla una de ellas, que es lo que no acabo de tener claro.

Por un lado tenemos la opción que dan como correcta, la c), cuyo árbol es el que propone reventador, y que encaja bien con los dos recorridos.
Por otro lado, el árbol de grincho, que encaja bien con el recorrido pre-orden del enunciado y con el recorrido in-orden de la respuesta d).
A mi se me había ocurrido otro árbol en el examen que encajaría con el recorrido in-orden de la respuesta b). Es el siguiente:

Raiz = Redhat (1)
Hijo izquierdo del (1) = Debian (2)
Hijo izquierdo del (2) = Fedora (3)
Hijo derecho del (2) = Mandriva (4)
Hijo izquierdo del (4) = Archilinux (5)

La única duda que se me plantea es si un árbol binario tiene alguna restricción del tipo que no pueda ser nulo ninguno de sus subárboles o similar. En cuyo caso, ni mi propuesta ni la de grincho serían válidas.

¿Alguien puede darnos su opinión?

Un saludo.

En mi caso, había dado por supuesto que el árbol fuera completo, y ahí ha estado mi fallo. Aunque tras el examen, empecé a darle vueltas a la cabeza, y entre ellas me salió otra posible respuesta, como es la que ha propuesto grincho. Aun así, considero que puede ser candidata a ser impugnable.