Рубрики

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 21

Рассмотрим корневое двоичное дерево, представленное с помощью указателей. Наилучшая верхняя граница времени требуется для определения количества поддеревьев, имеющих ровно 4 узла O (n a Logn b ). Тогда значение + 10b равно ________
(А) 1
(Б) 11
(С) 12
(D) 21

Ответ: (А)
Объяснение: Мы можем найти поддерево с 4 узлами за O (n) времени. Следующее может быть простым подходом.
1) Обходите дерево снизу вверх и найдите размер поддерева, укорененного в текущем узле.
2) Если размер становится 4, то выведите текущий узел.

Ниже приводится реализация C

#include<stdio.h>
#include<stdlib.h>

  

struct Node

{

    int data;

    struct Node *left, *right;

};

  
// Утилита для создания нового узла Binary Tree

struct Node *newNode(int item)

{

    struct Node *temp =  (struct Node *)malloc(sizeof(struct Node));

    temp->data = item;

    temp->left = temp->right = NULL;

    return temp;

}

  

int print4Subtree(struct Node *root)

{

    if (root == NULL)

      return 0;

    int l =  print4Subtree(root->left);

    int r =   print4Subtree(root->right);

    if ((l + r + 1) == 4)

       printf("%d ", root->data);

    return (l + r + 1);

}

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

int main()

{

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

    root->right->right = newNode(7);

    root->right->left->right = newNode(8);

  

    print4Subtree(root);

  

    return 0;

}

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

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

ВОРОТА | GATE-CS-2014- (Set-1) | Вопрос 21

0.00 (0%) 0 votes