Удаление узла и корня бинарного дерева

@Esso11 · Регистрация: 20.08.2017

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

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
struct Tree
{
int value;
Tree *l, *r;
};
 
 
void add(Tree *&obj, int value) {
if (obj == NULL) {
obj = new Tree;
obj->value = value;
obj->l = obj->r = NULL;
return;
}
if (obj->value < value) {
add(obj->l, value);
}
else {
add(obj->r, value);
}
}
 
void show(Tree *&tree) {
if (tree == NULL)return;
cout << tree->value << endl;
show(tree->r);
show(tree->l);
}
 
int sizeT(Tree *tree, int count = 0) {
if (tree == NULL) return count;
count++;
count = sizeT(tree->l, count);
count = sizeT(tree->r, count);
return count;
}
 
bool search(Tree* tree, int value, bool b = 0) {
if (tree == NULL) return 0;
if (tree->value == value || b == 1) return b = 1;
if (search(tree->l, value) == 1 || search(tree->r, value) == 1) return 1;
}
 
void btDelete(Tree **obj, int value)
{
if (*obj != NULL) {
 
if ((*obj)->value == value)
{
Tree*tmp = (*obj);
if ((*obj)->l == NULL && (*obj)->r == NULL) (*obj) = NULL;
else if ((*obj)->l != NULL && (*obj)->r != NULL)
{
(*obj) = tmp->r;
(*obj)->r = (*obj)->r;
(*obj)->r = (*obj)->l;
/*(*obj) = tmp->r;
(*obj)->l = (*obj)->r;*/
}
 
 
else if ((*obj)->l == NULL) (*obj) = tmp->r;
else if ((*obj)->r == NULL) (*obj) = tmp->l;
else
{
(*obj) = tmp->r;
Tree** tmp1;
tmp1 = obj;
while (*tmp1 != NULL)
{
tmp1 = &((*tmp1)->l);
(*tmp1) = tmp->l;
}
}
delete(tmp);
btDelete(obj, value);
}
else
{
btDelete(&((*obj)->l), value);
btDelete(&((*obj)->r), value);
}
 
 
}
 
}
bool emptyBT(Tree* obj)
{
return (obj == NULL ? true : false);
}
 
 
void print_Tree(Tree * p, int level)
{
if (p)
{
print_Tree(p->l, level + 1);
for (int i = 0; i< level; i++) cout << " ";
cout << p->value << endl;
print_Tree(p->r, level + 1);
}
}
 
 
 
int main()
{
Tree *tree = NULL;
add(tree, 8);
add(tree, 5);
add(tree, 3);
add(tree, 6);
add(tree, 12);
add(tree, 10);
add(tree, 11);
show(tree);
cout << "Size: " << sizeT(tree) << endl;
cout << endl << endl;
btDelete(&tree, 5);
show(tree);
cout << endl << endl;
 
 
//cout << "->" << search(tree, 15) << endl;
//cout << endl;
 
//print_Tree(tree, 0);
system("pause");
return 0;
}

Помогите разобраться как правильно это сделать. Заранее всем спасибо

@igorrr37 · 22.01.2018, 09:20

Максимальным должно быть правое поддерево

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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
#include <iostream>
#include <utility>
using namespace std;
 
struct Tree
{
    Tree() : l(NULL), r(NULL){}
    int value;
    Tree *l, *r;
};
 
 
void add(Tree *&obj, int value) {
    if (obj == NULL) {
        obj = new Tree;
        obj->value = value;
    }
    else if (obj->value < value) {
        add(obj->r, value);
    }
    else if (obj->value > value) {
        add(obj->l, value);
    }
}
 
void show(Tree *&tree) {
    if (tree == NULL)return;
    cout << tree->value << endl;
    show(tree->r);
    show(tree->l);
}
 
int sizeT(Tree *tree, int count = 0) {
    if (tree == NULL) 
        return count;
    count++;
    count = sizeT(tree->l, count);
    count = sizeT(tree->r, count);
    return count;
}
 
bool search(Tree* tree, int value, bool b = 0) {
    if (tree == NULL) return false;
    if (tree->value == value || b == 1) return b = true;
    if (search(tree->l, value) == 1 || search(tree->r, value) == 1) return true;
}
 
bool emptyBT(Tree* obj)
{
    return (obj == NULL ? true : false);
}
 
 
void print_Tree(Tree * p, int level = 0)
{
    if (p)
    {
        print_Tree(p->r, level + 1);
        for (int i = 0; i< level; i++) cout << "|";
        cout << p->value << endl;
        print_Tree(p->l, level + 1);
    }
}
 
// поиск родителя для num
Tree* find_parent(Tree* tree, int const num)
{
    Tree* parent = NULL;
    while (tree)
    {
        if (num < tree->value)
        {
            parent = tree;
            tree = tree->l;
        }
        else if (num > tree->value)
        {
            parent = tree;
            tree = tree->r;
        }
        else
        {
            break;
        }
    }
    if (!tree)
    {
        parent = NULL;
    }
 
    return parent;
}
 
/*ФУНКЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТА ДЕРЕВA*/
void deleteNode(Tree*& t, int num)
{
    if (t)
    {
        Tree* tree = t;
        // ищем родителя для num
        Tree* parent = find_parent(tree, num);
        // если родитель найден то tree выставляем на потомка которого нужно удалить
        if (parent)
        {
            if (parent->l && parent->l->value == num)
            {
                tree = parent->l;
            }
            else
            {
                tree = parent->r;
            }
        }
 
        if (tree->value == num || parent)
        {
            if (NULL == tree->l && NULL == tree->r) // у удаляемого узла нет потомков
            {
                if (parent)
                {
                    parent->l == tree ? parent->l = NULL : parent->r = NULL;
                }
                else // корневой узел без потомков
                {
                    t = NULL;
                }
                delete tree;
                tree = NULL;
            }
            else if (NULL == tree->l) // у удаляемого узла нет l 
            {
                Tree* tmp = tree->r;
                std::iter_swap(tree, tree->r);
                delete tmp;
                tmp = NULL;
            }
            else if (NULL == tree->r) // у удаляемого узла нет r
            {
                Tree* tmp = tree->l;
                std::iter_swap(tree, tree->l);
                delete tmp;
                tmp = NULL;
            }
            else // у удаляемого узла есть l и r
            {
                // заменяем удаляемый узел на минимальный из правого (максимального) поддерева
                if (NULL == tree->r->l)
                {
                    Tree* tmp = tree->r;
                    tree->value = tree->r->value;
                    tree->r = tree->r->r;
                    delete tmp;
                    tmp = NULL;
                }
                else
                {
                    Tree* tmp = tree->r;
                    while (tmp->l->l)
                    {
                        tmp = tmp->l;
                    }
                    tree->value = tmp->l->value;
                    if (NULL == tmp->l->r)
                    {
                        delete tmp->l;
                        tmp->l = NULL;
                    }
                    else
                    {
                        Tree* t1 = tmp->l->r;
                        std::iter_swap(tmp->l, tmp->l->r);
                        delete t1;
                        t1 = NULL;
                    }
                }
            }
        }
    }
}
 
int main()
{
    Tree *tree = NULL;
    add(tree, 8);
    add(tree, 5);
    add(tree, 3);
    add(tree, 6);
    add(tree, 12);
    add(tree, 10);
    add(tree, 11);
    print_Tree(tree);
 
    cout << "\nSize: " << sizeT(tree) << endl;
    cout << endl << endl;
    deleteNode(tree, 8);
    print_Tree(tree);
    cout << endl << endl;
 
 
    //cout << "->" << search(tree, 15) << endl;
    //cout << endl;
    return 0;
}

@Esso11 · 22.01.2018, 21:49 **[ТС]**

igorrr37, у меня просто указатели в ветвлении перепутанные больше меньше потому там непонятка, Спасибо тебе огромное за помощь!!!

Новые блоги и статьи Все статьи Все блоги /
Установка Qt-версии Lazarus IDE в Debian Trixie Xfce volvo 10.02.2026 В общем, достали меня глюки IDE Лазаруса, собранной с использованием набора виджетов Gtk2 (конкретно: если набирать текст в редакторе и вызвать подсказку через Ctrl+Space, то после закрытия окошка. . .	SDL3 для Web (WebAssembly): Работа со звуком через SDL3_mixer 8Observer8 08.02.2026 Содержание блога Пошагово создадим проект для загрузки звукового файла и воспроизведения звука с помощью библиотеки SDL3_mixer. Звук будет воспроизводиться по клику мышки по холсту на Desktop и по. . .	SDL3 для Web (WebAssembly): Основы отладки веб-приложений на SDL3 по USB и Wi-Fi, запущенных в браузере мобильных устройств 8Observer8 07.02.2026 Содержание блога Браузер Chrome имеет средства для отладки мобильных веб-приложений по USB. В этой пошаговой инструкции ограничимся работой с консолью. Вывод в консоль - это часть процесса. . .	SDL3 для Web (WebAssembly): Обработчик клика мыши в браузере ПК и касания экрана в браузере на мобильном устройстве 8Observer8 02.02.2026 Содержание блога Для начала пошагово создадим рабочий пример для подготовки к экспериментам в браузере ПК и в браузере мобильного устройства. Потом напишем обработчик клика мыши и обработчик. . .
Философия технологии iceja 01.02.2026 На мой взгляд у человека в технических проектах остается роль генерального директора. Все остальное нейронки делают уже лучше человека. Они не могут нести предпринимательские риски, не могут. . .	SDL3 для Web (WebAssembly): Вывод текста со шрифтом TTF с помощью SDL3_ttf 8Observer8 01.02.2026 Содержание блога В этой пошаговой инструкции создадим с нуля веб-приложение, которое выводит текст в окне браузера. Запустим на Android на локальном сервере. Загрузим Release на бесплатный. . .	SDL3 для Web (WebAssembly): Сборка C/C++ проекта из консоли 8Observer8 30.01.2026 Содержание блога Если вы откроете примеры для начинающих на официальном репозитории SDL3 в папке: examples, то вы увидите, что все примеры используют следующие четыре обязательные функции, а. . .	SDL3 для Web (WebAssembly): Установка Emscripten SDK (emsdk) и CMake для сборки C и C++ приложений в Wasm 8Observer8 30.01.2026 Содержание блога Для того чтобы скачать Emscripten SDK (emsdk) необходимо сначало скачать и уставить Git: Install for Windows. Следуйте стандартной процедуре установки Git через установщик. . . .

@Esso11 5 / 5 / 0 Регистрация: 20.08.2017 Сообщений: 685
	22.01.2018, 21:49 [ТС]
	igorrr37, у меня просто указатели в ветвлении перепутанные больше меньше потому там непонятка, Спасибо тебе огромное за помощь!!! 0