Sea LASTPOST, LASTIN y LASTPRE el último vértice visitado en un recorrido en postorden, en orden y en preorden. Respectivamente, de un árbol binario completo. ¿Cuál de las siguientes es siempre cierta? (GATE CS 2000)
(A) LASTIN = LASTPOST
(B) LASTIN = LASTPRE
(C) LASTPRE = LASTPOST
(D) Ninguna de las anteriores
Respuesta: (D)
Explicación: Se da que el árbol dado es un árbol binario completo . Para un árbol binario completo, el último Node visitado siempre será el mismo para el recorrido en orden y en orden previo. Nada de lo anterior es cierto incluso para un árbol binario completo.
La opción (a) es incorrecta porque el último Node visitado en el recorrido Inorder es el hijo derecho y el último Node visitado en el recorrido Postorder es el root.
La opción (c) es incorrecta porque el último Node visitado en el recorrido Preorder es el hijo derecho y el último Node visitado en el recorrido Postorder es root.
Para la opción (b), consulte el siguiente ejemplo de contador. Gracias a Hunaif Muhammed por proporcionar la explicación correcta.
1
/ \
2 3
/ \ /
4 5 6
Inorder traversal is 4 2 5 1 6 3
Preorder traversal is 1 2 4 5 3 6
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