Estructuras de datos | Recorridos de árboles | Pregunta 4

¿Qué hace la siguiente función para un árbol binario dado?

int fun(struct node *root)
{
   if (root == NULL)
      return 0;
   if (root->left == NULL && root->right == NULL)
      return 0;
   return 1 + fun(root->left) + fun(root->right);
}

(A) Cuenta los Nodes hoja
(B) Cuenta los Nodes internos
(C) Devuelve la altura donde la altura se define como el número de aristas en el camino desde la raíz hasta el Node más profundo
(D) Devuelve el diámetro donde el diámetro es el número de aristas en el camino más largo entre cualquier dos Nodes

Respuesta: (B)
Explicación: La función cuenta los Nodes internos.
1) Si la raíz es NULL o un Node hoja, devuelve 0.
2) De lo contrario, devuelve 1 más el recuento de Nodes internos en el subárbol izquierdo, más el recuento de Nodes internos en el subárbol derecho.

Ver el siguiente programa completo.

#include <stdio.h>
  
struct node
{
  int key;
  struct node *left, *right;
};
  
int fun(struct node *root)
{
   if (root == NULL)
      return 0;
   if (root->left == NULL && root->right == NULL)
      return 0;
   return 1 + fun(root->left) + fun(root->right);
}
  
/* Helper function that allocates a new node with the
   given key and NULL left and right pointers. */
struct node* newNode(int key)
{
  struct node* node = (struct node*)
                       malloc(sizeof(struct node));
  node->key = key;
  node->left = NULL;
  node->right = NULL;
  
  return(node);
}
  
/* Driver program to test above functions*/
int main()
{
  
  /* Constructed binary tree is
            1
          /   \
        2      3
      /  \    /
    4     5  8
  */
  struct node *root = newNode(1);
  root->left        = newNode(2);
  root->right       = newNode(3);
  root->left->left  = newNode(4);
  root->left->right = newNode(5);
  root->right->left = newNode(8);
  
  printf("%d", fun(root));
  
  getchar();
  return 0;
}

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *