Реализация бинарного дерева поиска

@bugorqwerty · Регистрация: 18.02.2017

Author24 — интернет-сервис помощи студентам

Не выводит значения узлов деревьев, как я понял происходит утечка памяти, но я не пойму, что нужно сделать. Программа ошибку не выдаёт. Просто ничего не выводит.[CPP]template

C++

template <typename T>
class TNode 
    {
    public:
        T data;
        TNode * left;
        TNode * right;
 
        TNode(TNode * left, TNode * right, const T & x) : left(left), right(right), data(x) {};
        TNode(const T & x) : left(nullptr), right(nullptr), data(x) {};
        //TNode() : left(nullptr), right(nullptr), data(T()) {};
    };

C++

template <typename T>
class DTree
{
    TNode<T> * root;
public:
    //Конструктор
    DTree() : root(nullptr) {};

C++

void insert_helper(TNode<T> * r, const T & x)
    {
        if (r == nullptr)
            r = new TNode<T>(nullptr, nullptr, x);
        else
            if (x <= r->data)
                insert_helper(r->left, x);
            else
                if (x >= r->data)
                    insert_helper(r->right, x);
 
    }
 
    void add(const T & x)
    {
        insert_helper(this->root, x);
    }
 
    void prefix(TNode<T> * r) const
    {
        if (r != nullptr)
        {
            std::cout << r->data << std::endl;
            prefix(r->left);
            prefix(r->right);
        }
    }
 
    void printPrefix() const
    {
        prefix(this->root);
    }

C++

int main()
 
{
 
    DTree<int> r;
    //r.add(r,3);
    r.add(10);
    r.add(7);
    r.add(12);
    r.printPrefix();
    
 
}

@igorrr37 · 22.03.2017, 01:06

C++

1	void insert_helper(TNode<T> *& r, const T & x)

нужно передавать указатель по ссылке

@alex white · 22.03.2017, 01:09

C++

void insert_helper(TNode<T> * r, const T & x)
    {
        if (r == nullptr)
            r = new TNode<T>(nullptr, nullptr, x);
        else
            if (x <= r->data)
                insert_helper(r->left, x);
            else
                if (x >= r->data)
                    insert_helper(r->right, x);
 
    }

r - это локальная переменная типа TNode<T>*. Её присвоение не изменит корня дерева (this->root) или какие либо другие поддеревья. Можете передавать указатель в insert_helper по ссылке (TNode<T>*&), либо возвращать и присваивать его новое значение (this->root = insert_helper(this->root, x)).

	22.03.2017, 01:09