PUERTA | PUERTA-CS-2000 | Pregunta 14

Considere la siguiente representación anidada de árboles binarios: (XYZ) indica que Y y Z son las subtensiones izquierda y derecha, respectivamente, del Node X. Tenga en cuenta que Y y Z pueden ser NULL o anidados. ¿Cuál de los siguientes representa un árbol binario válido?
(A) (1 2 (4 5 6 7))

(B) (1 (2 3 4) 5 6) 7)
(C) (1 (2 3 4)(5 6 7))
(D) (1 (2 3 NULL) (4 5))

Respuesta: (C )
Explicación: Para resolver esta pregunta tenemos que fijarnos en dos cosas:
1) En un árbol binario, un Node puede tener como máximo 2 hijos.
2) Para construir un árbol binario a partir de las secuencias anteriores, primero se debe trabajar el paréntesis más interno.

En la Opción A: (4 5 6 7) está ahí, que dice que el Node 4 tiene tres hijos, lo cual es incorrecto para un árbol binario, y también en la pregunta, solo (XYZ) está definido, es decir, un Node X puede tener como máximo 2 hijos, que serán las raíces de los subárboles Y y Z.

En la Opción B: después de trabajar en el más interno (2 3 4), donde 2 es un Node del árbol binario, 3 es el subárbol izquierdo del Node 2 y 4 es el subárbol derecho del Node 2. De esto obtenemos (1 2 5 6) . Aquí 2 proviene de la raíz del subárbol (2 3 4). Nuevamente, no tenemos ninguna definición para (1 2 5 6). Por lo tanto inválida.

En la Opción C: después de trabajar en ( 2 3 4 ) y ( 5 6 7 ) obtenemos ( 1 2 5 ) donde 2 proviene de la raíz del subárbol ( 2 3 4 ) y 5 proviene de la raíz del subárbol ( 5 6 7 ). Ahora, en ( 1 2 5 ) el Node 1 es la raíz del árbol binario, y el subárbol con raíz 2 es el subárbol izquierdo y el subárbol con raíz 5 es el subárbol derecho en el Node raíz 1. Por lo tanto, está dando un árbol binario válido.

En la Opción D: se da como ( 2 3 NULL), aquí N, U, L y L se dan como elementos diferentes, lo que nuevamente es incorrecto ya que según la definición (XYZ), un Node puede tener como máximo 2 hijos.
Cuestionario de esta pregunta