Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Ded_Vasilij
231 / 213 / 15
Регистрация: 01.09.2012
Сообщений: 2,103
#1

Удаление узла дерева - C++

03.05.2013, 22:41. Просмотров 638. Ответов 4
Метки нет (Все метки)

Добрый вечер.
У меня маленькая проблема - написал шаблон для работы с бинарным деревом поиска. Вроде асе робит, но возникла проблема с удалением внутренних узлов. Листья удаляются нормально, а вот при попытке удаления внутреннего узла программа радостно падает. И в чем дело понять не могу. Выручайте люди добрые... Вот код
Я конечно дико извиняюсь, что он без комментариев, но времени нет...
Отладчик показывает на функцию Del2 - только не могу понять в чем проблема
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
#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);
    }
};
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
03.05.2013, 22:41
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Удаление узла дерева (C++):

Удаление узла из дерева - C++
сделав функции добавления,поиска,пару обходов и вывод ввиде дерева в консоли(жаль что нельзя размер по x изменить) при тестировании...

Удаление узла бинарного дерева - C++
всем привет.вот есть у меня бинарное дерево тока фун-ии добавления и обхода.очень нужно удалени помогите плиз. .cpp #include &lt;iostream&gt;...

Удаление Узла Бинарного Дерева. - C++
Добрый День.Возникла проблема с реализацией части функции контейнера для удаления элемента с двумя узлами(по всем правилам бинарных...

Удаление Узла бинарного дерева - C++
Добрый вечер. Имеем Бинарное дерево поиска. При удалении некоторого узла . возникают три случая. Один из случаев , наличие у...

Функция: удаление узла дерева со всеми потомками - C++
подскажите код функции которая удаляет элемент дерева со всеми его потомками NODE *SEARCH(char *key, NODE *root) { NODE...

Удаление узла бинарного дерева, проблема с функциями, адресацией - C++
код: #include &lt;cstdlib&gt; #include &lt;iostream&gt; typedef struct tree{ // обьявляем тип char data; //дата изьятия в формате xx.xx.xxxx ...

4
kristi1
10 / 10 / 1
Регистрация: 07.03.2010
Сообщений: 465
03.05.2013, 22:44 #2
Не особо вникал в код, но когда вы посередине удаляете звено - что происходит с тем, что ниже идет? Отваливается? Цепляется? Скорее проблема в переобозначении указателей
1
Ded_Vasilij
231 / 213 / 15
Регистрация: 01.09.2012
Сообщений: 2,103
03.05.2013, 23:28  [ТС] #3
смысл такой - если у узла два потомка, то идем в левое поддерево, ищем там наибольший элемент, и ставим его на место удаляемого, а в левом поддереве происходит переопределение указателей - чтобы дерево осталось упорядоченным - на бумаге сделать могу, не проблема, а вот в коде запутался

Добавлено через 26 минут
Все, разобрался, тема закрыта
0
kristi1
10 / 10 / 1
Регистрация: 07.03.2010
Сообщений: 465
03.05.2013, 23:28 #4
В чем была проблема?
0
Ded_Vasilij
231 / 213 / 15
Регистрация: 01.09.2012
Сообщений: 2,103
03.05.2013, 23:46  [ТС] #5
как Вы и сказали, в переопределении указателей - конкретно - в Delete нужно было указателю pDel изначально присвоить rt. Короче Delete теперь выглядит так
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
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;
            }
    }
1
03.05.2013, 23:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.05.2013, 23:46
Привет! Вот еще темы с ответами:

Удаления узла из бинарного дерева поиска - C++
Уже довольно много времени убил на эту задачу, теорию понимаю, на практике реализовать никак не получается. Помогите пожалуйста написать...

Как сгенерировать ключ для узла дерева? - C++
В C# для создания сквозной нумерации текстовых заметок можно было просто объявить целую static-переменную в описании класса заметки,...

Определение глубины (числа ветвей) непустого дерева от вершины до заданного узла - C++
Подскажите пожалуйста. Никак не могу найти код нахождения глубины бинарного дерева от вершины до заданного узла. тут весь форум перерыл...

RB tree удаление узла - C++
Народ, подсткажите рекурсивный алгоритм удаления узла RB tree, или где найти можно... второй день в гугле сижу, видимо руки не от туда...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru