El número de formas en que se pueden insertar los números 1, 2, 3, 4, 5, 6, 7 en un árbol de búsqueda binario vacío, de modo que el árbol resultante tenga una altura de 6, es _____________
Nota: La altura de un árbol con un solo Node es 0.
[Esta pregunta era originalmente una pregunta para llenar los espacios en blanco]
(A) 2
(B) 4
(C) 64
(D) 32
Respuesta: (C)
Explicación: Para obtener la altura 6, necesitamos poner 1 o 7 en la raíz.
Entonces, el conteo se puede escribir como T(n) = 2*T(n-1) con T(1) = 1
7
/
[1..6]
1
\
[2..7]
Por lo tanto cuenta es 2 6 = 64
Otra explicación:
Considere estos casos,
1 2 3 4 5 6 7
1 2 3 4 5 7 6
1 7 6 5 4 3 2
1 7 6 5 4 2 3
7 6 5 4 3 2 1
7 6 5 4 3 1 2
7 1 2 3 4 5 6
7 1 2 3 4 6 5
Para la altura 6, tenemos 2 opciones. O seleccionamos la raíz como 1 o 7.
Supongamos que seleccionamos 7.
Ahora, tenemos 6 Nodes y altura restante = 5.
Entonces, ahora también tenemos 2 formas de seleccionar la raíz para este subárbol.
Ahora, seguimos repitiendo el mismo procedimiento hasta altura restante = 1
Para este último caso también, tenemos 2 formas.
Por lo tanto, número total de formas = 2 6 = 64
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