Un árbol binario T tiene 20 hojas. El número de Nodes en T que tienen dos hijos es
(A) 18
(B) 19
(C) 17
(D) Cualquier número entre 10 y 20
Respuesta: (B)
Explicación:
Suma de todos los grados = 2 * |E|.
Aquí considerando el árbol como un árbol k-ario:
Sum of degrees of leaves + Sum of degrees for Internal Node except root + Root's degree = 2 * (No. of nodes - 1). Putting values of above terms, L + (I-1)*(k+1) + k = 2 * (L + I - 1) L + k*I - k + I -1 + k = 2*L + 2I - 2 L + K*I + I - 1 = 2*L + 2*I - 2 K*I + 1 - I = L (K-1)*I + 1 = L Given k = 2, L=20 ==> (2-1)*I + 1 = 20 ==> I = 19 ==> T has 19 internal nodes which are having two children.
Ver Handshaking Lemma y Interesting Tree Properties como prueba.
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