PUERTA | PUERTA-CS-2004 | Pregunta 43

Considere el siguiente segmento de programa C

struct CellNode
{
  struct CelINode *leftchild;
  int element;
  struct CelINode *rightChild;
}
  
int Dosomething(struct CelINode *ptr)
{
    int value = 0;
    if (ptr != NULL)
    {
      if (ptr->leftChild != NULL)
        value = 1 + DoSomething(ptr->leftChild);
      if (ptr->rightChild != NULL)
        value = max(value, 1 + DoSomething(ptr->rightChild));
    }
    return (value);
}

El valor devuelto por la función HacerAlgo cuando se pasa como argumento un puntero a la raíz de un árbol no vacío es
(A) El número de Nodes hoja en el árbol
(B) El número de Nodes en el árbol
(C) El número de Nodes internos en el árbol
(D) La altura del árbol

Respuesta: (D)
Explicación:

DoSomething() devuelve max(altura del hijo izquierdo + 1, altura del hijo derecho + 1). Entonces, dado que el puntero a la raíz del árbol se pasa a DoSomething(), devolverá la altura del árbol. Tenga en cuenta que esta implementación sigue la convención donde la altura de un solo Node es 0. Tomemos un árbol de muestra e intentemos ejecutar el código.

El árbol anterior devuelve 3 como salida, que es la altura del árbol (con la convención de la altura de un solo Node como 0), mientras que el número de Nodes hoja en este árbol es 4, el número de Nodes internos es 4 y el total de Nodes es 8, lo que claramente demuestra que las otras opciones están equivocadas.

Consulte http://geeksquiz.com/data-structures-binary-trees-question-23/

Esta solución es aportada por Parul Sharma.
Cuestionario de esta pregunta