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
204
205
206
207
208
209
210
211
212
| #include <iostream>
using namespace std;
typedef struct Node
{
int data;
Node* left;
Node* right;
}Node, *PNode, **PPNode;
PNode Tree; //адрес корня дерева
PNode p1; //вспомогательная переменная
PNode Ovn; //Владелец найденного элемента после поиска
int n, x, i;
char ch; //для работы менюшки
//Процедура добавления элемента
void AddToTree (PPNode Tree, int x) //Входные параметры - адрес адреса корня дерева и добавл элемент
{
if (*Tree == NULL) //Если дерево пустое то создаём его корень
{
*Tree = new(Node); //Выделяем память
(*Tree)->data = x; //Добавляем данные
(*Tree)->left = NULL; //Зануляем указатели на левого
(*Tree)->right = NULL; // и правого сыновей
}
else
{
if (x < (*Tree)->data) //Доб к левому или правому поддереву это завсит от вводимого элемента
AddToTree(&((*Tree)->left), x); // если меньше корня то в левое поддерево
else
AddToTree(&((*Tree)->right), x); // если больше то в правое
}
}
//Функция поиска по дереву
PNode Search(PNode Tree, int x) //Возвращает адрес искомого элемента, NULL если не найден
{
PNode p; //вспомог переменнная
if (Tree == NULL) //если дерево пустое то
return NULL; //результат NULL и выходим
if (x == Tree->data) //если искомый элемент равен корню дерева то
p = Tree; // запоминаем его адрес
else
{ //иначе
Ovn = Tree; //сохраняем в глоб.перем адрес отца сыновей
if (x < Tree->data) //если вводимый элемент менньше корня то
p = Search(Tree->left, x); //то ищем его в левом поддереве
else // иначе
p = Search(Tree->right, x); // ищем в правом поддереве
}
return p; //возвращаем адрес искомого элемента
}
//Обход дерева по принципу Левый - корень - правый
void Lkp(PNode Tree)
{
if (Tree == NULL) //Если дерево пустое
return; //то выход
Lkp(Tree->left); //иначе начинаем обход с левого подднрева
cout << " " << Tree->data; //выводим данные
Lkp(Tree->right); //обходим правое поддерево
}
//Вставить уже существующее дерево / элемент в структуру дерева
void InsertNode(PPNode Tree, PNode Ins)
{
if (*Tree == NULL) //Если дерево пустое то вставляемый будет корнем
{
*Tree = Ins;
return;
}
if (Ins->data < (*Tree)->data) //Доб к левому или правому поддереву это завсит от вводимого элемента
InsertNode(&((*Tree)->left), Ins); // если меньше корня то в левое поддерево
else
InsertNode(&((*Tree)->right), Ins); // если больше то в правое
}
//Удаление елемента в дереве. true, если елемент был удален
bool DeleteNode(PPNode Tree, int x)
{
PNode ToIns, ToDel;
bool ret;
Ovn = NULL; //глоб.перем для определения владельца удаляемого
ToDel = Search(*Tree, x);
if (ToDel == NULL)
return false;
if (ToDel == *Tree) //найденный элемент является корнем
{
if (ToDel->left != NULL)
{
*Tree = ToDel->left; //корнем становится левый сучок
ToIns = ToDel->right; //а правый потом вставим
}
else
{
//если и правый окажется nil, то все дерево пустое
*Tree = ToDel->right; //корнем становится правый
ToIns = ToDel->left; //левый вставим позже
}
}
else
{
if (Ovn->right == ToDel) // если найденный под удаление правый, то
{
Ovn->right = ToDel->right; //правый сын предка теперь его внук
ToIns = ToDel->left; //оставшийся сучок, который нужно вставить
}
else
{
Ovn->left = ToDel->left; //иначе левый внук становится сыном
ToIns = ToDel->right; //оставшийся не у дел
}
}
delete(ToDel); //Удаление найденного элемента
InsertNode(Tree, ToIns); //Вставляем оставшийся сучок в структуру дерева
}
//Процедура удаления дерева}
void DeleteTree(PNode Tree1)
{
if (Tree1 != NULL)
{
DeleteTree (Tree1->left);
DeleteTree (Tree1->right);
delete(Tree1);
}
}
//основная пограмма
int main()
{
setlocale(LC_ALL, "RUS");
Tree = NULL;
Ovn = NULL;
while (true) //цикл для нашего меню
{
cout << "Выберете действие" << endl;
cout << "Доступны следующие пункты:" << endl;
cout << "1) Создание дерева поиска" << endl;
cout << "2) Поиск элемента в дереве" << endl;
cout << "3) Вывод дерева" << endl;
cout << "4) Удаление элемента" << endl;
cout << "5) Выход" << endl << endl;
cin >> ch; //ожидаем нажатия клавиши
switch (ch) //выбираем клавишу
{
case '1':
cout << "Количество элементов: ";
cin >> n;
for (i = 0; i < n; i++)
{
cout << "Введите число: ";
cin >> x;
AddToTree(&Tree, x);
}
cout << endl;
break;
case '2':
if (Tree != NULL)
{
cout << "Елемент для поиска: ";
cin >> x;
p1 = Search(Tree, x);
if (p1 != NULL)
cout << "Найден";
else
cout << "Такого элемента нет!";
}
else
cout << "Дерево пустое";
cout << endl << endl;
break;
case '3':
if (Tree != NULL)
{
cout << "Само дерево" << endl;
Lkp(Tree);
}
else
cout << "Дерево пустое";
cout << endl << endl;
break;
case '4':
if (Tree != NULL)
{
cout << "Элемент для удаления: ";
cin >> x;
if (DeleteNode(&Tree, x))
cout << "Удален";
else
cout << "Такого элемента нет!";
}
else
cout << "Дерево пустое";
cout << endl << endl;
break;
case '5':
DeleteTree(Tree);
return 0;
default:
cout << "Введите 1-5" << endl << endl;
}
}
} |
(
