Se sabe que las siguientes tres son las secuencias de orden previo, orden interno y orden posterior de un árbol binario. Pero no se sabe cuál es cuál.
MBCAFHPYK
KAMCBYPFH
MABCKYFPH
Elija la afirmación verdadera de las siguientes.
(A) I y II son secuencias en preorden y en orden, respectivamente
(B) I y III son secuencias en preorden y en orden posterior, respectivamente
(C) II es la secuencia en orden, pero no se puede decir nada más sobre las otras dos secuencias
(D) II y III son las secuencias en preorden y en orden, respectivamente
Respuesta: (D)
Explicación:
El enfoque para resolver esta pregunta es encontrar primero 2 secuencias cuyo primer y último elemento sea el mismo. La razón es que el primer elemento en el pedido previo de cualquier árbol binario es la raíz y el último elemento en el pedido posterior de cualquier árbol binario es la raíz.
Mirando las secuencias dadas,
Pre-order = KAMCBYPFH
Post-order = MBCAFHPYK
La secuencia sobrante MABCKYFPH estará en orden.
Ya que tenemos todos los recorridos identificados, tratemos de dibujar el árbol binario si es posible.
I. Orden postal
II. Pre pedido
III. En orden
Esta solución es aportada por Pranjul Ahuja.
Cuestionario de esta pregunta
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA