Извлечение поддерева из BST в C ++ - PullRequest
Новая
       5

Извлечение поддерева из BST в C ++

0 голосов
/ 28 июня 2018

Я работаю над заданием на C ++. Проект состоит в создании класса шаблона для дерева двоичного поиска.

Пока что я реализовал основные методы и итераторы, и все, кажется, работает просто отлично. Теперь мне нужно реализовать метод subtree(const T &value), который, учитывая цель value, возвращает дерево с value в качестве корня.

Пока что я определил это: 

binarySearchTree subtree(const T &target) {

        nodo* node = findValue(target);

        binarySearchTree<T> newTree;
        newTree._root = node;

        return newTree;
}

, где findValue: 

nodo* findValue(const T &target){

        if(_root -> value == target) {              
            return _root;
        } 
        else
            return findValueHelper(_root, target);
}

и findValueHelper: 

nodo* findValueHelper(nodo *ptr, const T &val) const {

        if (ptr == NULL)
            return NULL;
        if (val < ptr -> value)
            return findValueHelper(ptr -> left, val);
        else if (val > ptr -> value)
            return findValueHelper(ptr -> right, val);
        else 
            return ptr;

    }

и nodo - это просто моя структура с указателями T value, left и right.

Теперь к проблеме:

Извлеченное поддерево является правильным, но после его печати я получаю ошибку segmentation fault, несмотря на то, что все элементы отображаются правильно.

В main я звоню: 

binarySearchTree<int> sub = t.subtree(2);
std::cout << sub << std::endl;

И я явно переопределил и operator= и operator<<.

1 Ответ

0 голосов
/ 28 июня 2018

Поскольку вы не опубликовали всю свою реализацию, это предположение, но, вероятно, верно.

newTree._root = node; копирует указатель на узел. Теперь у вас есть один узел, используемый в двух деревьях. Но деструктор дерева, вероятно, освобождает узлы. Поэтому, когда одно дерево выходит из области видимости (например, в конце функции), узлы освобождаются, и указатель становится недействительным. В следующий раз, когда что-то выделяется, ваши узлы перезаписываются. Таким образом, печать по-прежнему работает (хотя поведение не определено), но тогда ваше дерево повреждено.

...