Удаление узла дерева

@Ded_Vasilij · Регистрация: 01.09.2012

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

Добрый вечер.
У меня маленькая проблема - написал шаблон для работы с бинарным деревом поиска. Вроде асе робит, но возникла проблема с удалением внутренних узлов. Листья удаляются нормально, а вот при попытке удаления внутреннего узла программа радостно падает. И в чем дело понять не могу. Выручайте люди добрые... Вот код
Я конечно дико извиняюсь, что он без комментариев, но времени нет...
Отладчик показывает на функцию Del2 - только не могу понять в чем проблема

C++

#pragma once
template <typename TElem>
class Tree
{
    struct TreeElem
    {
        TreeElem* Right;
        TreeElem* Left;
        TElem inf;
        TreeElem(const TElem &x = TElem()): inf(x),Right(0),Left(0)
        {}
    };
    TreeElem* root;
public:
    Tree():root(0){}
    Tree(const TElem &x)
    {
        root = TreeElem(x);
    }
    Tree(const Tree & T)
    {
        root = Copy(T.root);
    }
    ~Tree()
    {
        MakeEmpty(root);
    }
    Tree& operator = (const Tree& T)
    {
        if(this == &T)
        {
            return *this;
        }
        MakeEmpty();
        root = Copy(T.root);
        retutn *this;
    }
    bool Find(const TElem &x) const
    {
        TreeElem *p = root;
        while (p)
        {
            if (x < p->inf)
            {
                p = p->Left;
            }
            else
                if (x > p->inf)
                {
                    p = p->right;
                }
                else
                {
                    return p;
                }       
        }
        return 0;
    }
    void Insert(const TElem &x)
    {
        Insert(root,x);
    }
    void Delete (const TElem &x)
    {
        Delete(root,x);
    }
    void Makeempty()
    {
        MakeEmpty(root);
        root = 0;
    }
    bool IsEmpty()
    {
        return !root;
    }
    void Print()
    {
        Print(root);
    }
private:
    TreeElem* Copy(TreeElem*rt)
    {
        TreeElem *new_rt = 0;
        if(!rt)
        {
            return 0;
        }
        new_rt = new TreeElem(rt->inf);
        try
        {
            new_rt->Left = Copy(rt->Left);
            new_rt->Right = Copy(rt->Right);
            return new_rt;
        }
        catch (bad_alloc)
        {
            MakeEmpty(new_rt);
            throw;
        }
    }
    void MakeEmpty(TreeElem*& rt)
    {
        if(!rt)
        {
            return;
        }
        MakeEmpty(rt->Left);
        MakeEmpty(rt->Right);
        delete rt;
    }
    void Insert(TreeElem *& rt,const TElem &x)
    {
        if(!rt)
        {
            rt = new TreeElem(x);
            return;
        }
        if(x < rt->inf)
        {
            Insert(rt->Left,x);
        }
        else
            if (x > rt-> inf)
            {
                Insert(rt->Right,x);
            }
 
    }
    void Delete(TreeElem*& rt, const TElem &x)
    {
        if(!rt)
        {
            return;
        }
        if(x < rt->inf)
        {
            Delete(rt->Left,x);
        }
        else
            if(x > rt->inf)
            {
                Delete(rt->Right,x);
            }
            else
            {
                TreeElem*pDel = 0;
                if(!rt->Right)
                {
                    rt = rt->Left;
                }
                else
                    if(!rt->Left)
                    {
                        rt = rt->Right;
                    }
                    else
                        Del2(pDel,rt->Left);
                delete pDel;
            }
    }
    void Del2(TreeElem*&p,TreeElem*&q)
    {
        if(q->Right)
        {
            Del2(p,q->Right);
        }
        else
        {
            p->inf = q->inf;
            p = q;
            q = q->Left;
        }
    }
    void Print(const TreeElem*rt)
    {
        if(!rt)
        {
            return;
        }
        Print(rt->Left);
        cout << rt->inf<<"\t";
        Print(rt->Right);
    }
};

@kristi1 · 03.05.2013, 22:44

Не особо вникал в код, но когда вы посередине удаляете звено - что происходит с тем, что ниже идет? Отваливается? Цепляется? Скорее проблема в переобозначении указателей

@Ded_Vasilij · 03.05.2013, 23:28 **[ТС]**

смысл такой - если у узла два потомка, то идем в левое поддерево, ищем там наибольший элемент, и ставим его на место удаляемого, а в левом поддереве происходит переопределение указателей - чтобы дерево осталось упорядоченным - на бумаге сделать могу, не проблема, а вот в коде запутался

Добавлено через 26 минут
Все, разобрался, тема закрыта

@kristi1 · 03.05.2013, 23:28

В чем была проблема?

@Ded_Vasilij · 03.05.2013, 23:46 **[ТС]**

как Вы и сказали, в переопределении указателей - конкретно - в Delete нужно было указателю pDel изначально присвоить rt. Короче Delete теперь выглядит так

C++

void Delete(TreeElem*& rt, const TElem &x)
    {
        if(!rt)
        {
            return;
        }
        if(x < rt->inf)
        {
            Delete(rt->Left,x);
        }
        else
            if(x > rt->inf)
            {
                Delete(rt->Right,x);
            }
            else
            {
                TreeElem*pDel = rt;
                if(!rt->Right)
                {
                    rt = rt->Left;
                }
                else
                    if(!rt->Left)
                    {
                        rt = rt->Right;
                    }
                    else
                        Del2(pDel,rt->Left);
                delete pDel;
            }
    }

@kristi1 11 / 11 / 2 Регистрация: 07.03.2010 Сообщений: 465
	03.05.2013, 22:44	2
	Не особо вникал в код, но когда вы посередине удаляете звено - что происходит с тем, что ниже идет? Отваливается? Цепляется? Скорее проблема в переобозначении указателей 1

@Ded_Vasilij 233 / 215 / 63 Регистрация: 01.09.2012 Сообщений: 2,103
	03.05.2013, 23:28 [ТС]	3
	смысл такой - если у узла два потомка, то идем в левое поддерево, ищем там наибольший элемент, и ставим его на место удаляемого, а в левом поддереве происходит переопределение указателей - чтобы дерево осталось упорядоченным - на бумаге сделать могу, не проблема, а вот в коде запутался Добавлено через 26 минут Все, разобрался, тема закрыта 0

@kristi1 11 / 11 / 2 Регистрация: 07.03.2010 Сообщений: 465
	03.05.2013, 23:28	4
	В чем была проблема? 0

	03.05.2013, 23:46