Considere las secuencias de etiquetas obtenidas por los siguientes pares de recorridos en un árbol binario etiquetado. ¿Cuál de estos pares identifica un árbol de manera única?
(i) preorder and postorder (ii) inorder and postorder (iii) preorder and inorder (iv) level order and postorder
(A) (i) solo
(B) (ii), (iii)
(C) (iii) solo
(D) (iv) solo
Respuesta: (B)
Explicación: Aquí, consideramos todas y cada una de las opciones para verificar si es verdadero o falso.
1) Pedido anticipado y pedido posterior
Para los árboles de arriba,
El pedido anticipado es AB
El pedido posterior es BA
Muestra que el pedido anticipado y el pedido posterior no pueden identificar un árbol de manera única.
2) Inorder y postorder definen un árbol de forma única
3) Preorder e Inorder también definen un árbol de forma única
4) Levelorder y postorder no pueden definir un árbol de forma única. Para el ejemplo anterior,
El orden de nivel es AB
El pedido posterior es BA
Ver https://www.geeksforgeeks.org/if-you-are-given-two-traversal-sequences-can-you-construct-the-binary-tree/ para más detalles
Esta solución es aportada por Anil Saikrishna Devarasetty
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