Estructuras de datos | Árboles binarios | Pregunta 15 – Part 1

En un árbol k-ario completo, cada Node interno tiene exactamente k hijos o ningún hijo. El número de hojas en tal árbol con n Nodes internos es:
(A) nk
(B) (n – 1) k+ 1
(C) n( k – 1) + 1
(D) n(k – 1)

Respuesta: (C)
Explicación: para un árbol k-ario donde cada Node tiene k hijos o no tiene hijos, la siguiente relación es
L = (k-1)*n + 1

Donde L es el número de Nodes hoja y n es el número de Nodes internos.
ya que es un árbol k completo, por lo que cada Node interno tendrá K hijo
Veamos lo siguiente, por ejemplo

               o
        /      |      \
      o        o        o
    / | \    / | \    / | \
   o  o  o  o  o  o  o  o  o
                      

k = 3
Number of internal nodes n = 4
Number of leaf nodes = (k-1)*n  + 1
                     = (3-1)*4 + 1
                     = 9 

Cuestionario de esta pregunta