Рубрики

Структуры данных | Обход дерева | Вопрос 4

Что делает следующая функция для данного двоичного дерева?

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) Подсчитывает листовые узлы
(B) Подсчитывает внутренние узлы
(C) Возвращает высоту, где высота определяется как количество ребер на пути от корня до самого глубокого узла
(D) Возвращает диаметр, где диаметр — это число ребер на самом длинном пути между любыми двумя узлами.

Ответ: (Б)
Объяснение: Функция считает внутренние узлы.
1) Если root равен NULL или конечному узлу, он возвращает 0.
2) В противном случае возвращает 1 плюс количество внутренних узлов в левом поддереве плюс количество внутренних узлов в правом поддереве.

Смотрите следующую полную программу.

#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);

}

  
/ * Вспомогательная функция, которая выделяет новый узел с

   данный ключ и NULL левый и правый указатели. * /

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);

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

  

  / * Построенное двоичное дерево

            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;

}

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Обход дерева | Вопрос 4

0.00 (0%) 0 votes