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

Опубликовано 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 минут


Один комментарий : “Поиск поддерева в дереве”

  1. Владислав says:

    Вроде работает.

    struct node {
        int data;
        node* left;
        node* right;
        node(int d): data(d), left(NULL), right(NULL){}
    };
     
    class binary_tree {
         node *tree;
    public:
        binary_tree(): tree(NULL){}
     
        void add(int el) {
            addElem(tree,el);
        }
        void show() {
            print(tree);
        }
        node * getTree(){ return tree;}
    private:
        void print(node * t)    {
            if(t){
                cout << t->data << " ";
            print(t->left);
            print(t->right);
            }
        }
        void addElem(node *&tr, int elem)  {
            if(tr == NULL)
                tr = new node(elem);
            else if(elem < tr->data)
                addElem(tr->left,elem);
            else if(elem >= tr->data)
                addElem(tr->right, elem);
        }
    };
     
    void help_write_data(node * tree, string & str_tree) {
            if(tree){
                str_tree += to_string(tree->data) + " ";
                help_write_data(tree->left, str_tree);
                help_write_data(tree->right, str_tree);
            }
        }
     
    string write_data(node * tree) {
            string str_tree;
            help_write_data(tree, str_tree);
            return str_tree;
        }
     
     
    bool is_sub_tree(node * tree, node *subtree) {
     
        std::string tr = write_data(tree);
        std::string sub = write_data(subtree);
     
        if(tr.find(sub) == std::string::npos)
            return false;
        else
            return true;
    }
     
     
    int main() {
     
        binary_tree tree;
        binary_tree sub_tree;
            tree.add(4);
            tree.add(2);
            tree.add(3);
            tree.add(2);
            tree.add(4);
            sub_tree.add(3);
            sub_tree.add(2);
            sub_tree.add(4);
     
            cout << endl << is_sub_tree(b.getTree(),sub_tree.getTree()) << endl;
        return 0;
    }

Оставить комментарий

Ваш адрес email не будет опубликован.


*