Поиск поддерева в дереве

Опубликовано Aug 29, 2011 в Деревья и графы | 1 коммент.


Поиск поддерева в дереве

Напишите функцию, которая бы проверила, что заданное бинарное дерево является поддеревом другого бинарного дерева. Сигнатура функции задана, но можно вводить вспомогательные функции. Например, для деревьев, приведенных на рисунке, должен получиться ответ 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 минут