Algoritmos | Varios | Pregunta 16

En un árbol k-ario completo, cada Node interno tiene exactamente k hijos. El número de hojas en tal árbol con n Nodes internos es: (GATE CS 2005)
(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 ningún hijo, la siguiente relación se cumple
L = (k-1)*n + 1

Donde L es el número de Nodes hoja y n es el número de Nodes internos.

Veamos a continuación 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