+380 57 755 34 05 team@fulcrum.software

Напишите функцию, которая бы проверила, что заданное бинарное дерево является поддеревом другого бинарного дерева. Сигнатура функции задана, но можно вводить вспомогательные функции. Например, для деревьев, приведенных на рисунке, должен получиться ответ true.


       sub_tree                    global_tree
          10                           26
        /    \                       /   \
      4       6                     10     3
       \                          /    \     \
        30                      4       6      3
struct node                       \
{                                 30
   int data;
   struct node* left;
   struct node* right;
};

bool contains_sub_tree(struct node* global_tree, 
                       struct node* sub_tree)
{
  // ваш код
}

1Цель заданиябыстрая проверка знаний основных структур
данных, алгоритмов и средств их реализации
2Время
выполнения
30 минут
3Формат
выполнения
код пишется на компьютере или бумаге
на выбор, но без доступа к документации

Критерии оценки FulcrumWeb:

Нужно продемонстрировать знание приемов работы с бинарными деревьями.

Оценка результатов:

Для программиста, который специально не прорабатывал алгоритмы работы с деревьями, задача может показаться сложной. Годится любая реализация, возможно с ошибками, которые будут исправлены после указания на них. Начинать можно с реализации функции обхода дерева в любом порядке. После этого нужно определить, присутствует ли корень поддерева среди узлов дерева. Если — да, то дальше нужно попытаться обходить оба дерева, отслеживая, делаем ли мы только одинаковые шаги и совпадают ли при этом данные в соответствующих узлах.

Для последней процедуры можно описывать пройденный по деревьям путь в виде каких-то строковых конструкций и потом их сравнить. Второй вариант — сравнивать каждый шаг по обоим деревьям и как только где-то возникло расхождение, процесс остановить, вернув false.

Время выполнения: 30 минут