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

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

Войти
Регистрация
Восстановить пароль
 
byhukutka
0 / 0 / 0
Регистрация: 12.07.2013
Сообщений: 47
#1

Рекурсивные Деревья - C++

10.12.2014, 20:52. Просмотров 469. Ответов 1
Метки нет (Все метки)

Прошу помощи. Написал код для бинарных деревьев, тут же всунул дерево минимальной высоты. Но при компиляции выдает ошибки в строке 6 и 8. Я не понимаю в чем проблема.
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
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
#include <iostream>
#include <conio.h>
 
using namespace std;
 
struct Node{ //объявление класса (структура узла)
int key;
Node *left, *right; //указатель на левый/правый узел
};
typedef Node *PNode;
/*
PNode MakeTree(int *data, int &from, int n){ //Создание дерева минимальной высоты //указатель на массив из которого дерево
//from - счетчик
//n - размер массива
PNode Tree;
int n1, n2;
 
if(n == 0)return NULL; //Ограничение рекурсии
Tree = new Node;
Tree->key = data[from++];
n1 = n/2;
n2 = n - n1 - 1;
 
Tree->left = MakeTree(data, from, n1);
Tree->right = MakeTree(data, from, n2);
 
return Tree;
}
*/
 
void PrintLKP(PNode Tree){ //Обход ЛКП
if (!Tree) return; // пустое дерево – окончание рекурсии
PrintLKP(Tree->left); // обход левого поддерева
cout<<Tree->key<<" "; // вывод информации о корне
PrintLKP(Tree->right); // обход правого поддерева
}
void PrintKLP(PNode Tree){ //Обход КЛП
if (!Tree) return; // пустое дерево – окончание рекурсии
cout<<Tree->key<<" "; // вывод информации о корне
PrintKLP(Tree->left); // обход левого поддерева
PrintKLP(Tree->right); // обход правого поддерева
}
void PrintLPK(PNode Tree){ //Обход ЛПК
if (!Tree) return; // пустое дерево – окончание рекурсии
PrintLPK(Tree->left); // обход левого поддерева
PrintLPK(Tree->right); // обход правого поддерева
cout<<Tree->key<<" "; // вывод информации о корне
}
 
/*
int main(){ //Вывод дерева минимальной высоты
int data[] = {21, 8, 9, 11, 15, 19, 20, 21, 7};
PNode Tree;
int k = 0;
int n = sizeof(data)/sizeof(int);
Tree = MakeTree(data, k, n);
PrintLKP(Tree); //печать дерева
cout<<endl;
getch();
//system("pause");
return 0;
}
*/
 
 
//-------типовые функции для дерева
 
PNode SMin(PNode Tree){ //Поиск минимального элемента
if(!Tree) return NULL;//проверяем, что получаем на входе, если получаем указатель на пустое дерево-выход, возврат 0
if(!Tree->left) return Tree;//если нет потомка слева, нашли минимальный элемент
return SMin(Tree->left);//рекурсивно вызываем эту функцию но уже у левого потомка
}
 
PNode SMax(PNode Tree){ //Поиск максимального элемента
if(!Tree) return NULL; //проверяем, что получаем на входе, если получаем указатель на пустое дерево-выход, возврат 0 (уже справа)
if(!Tree->right) return Tree;//если нет потомка справа, нашли минимальный элемент
return SMax(Tree->right);//рекурсивно вызываем эту функцию но уже у правого потомка
}
 
PNode NextOf(PNode Tree){ //Определение следующего элемента
if(!Tree) return NULL;//если дерево пусто-возвращаем нулвой указатель
if(!(!Tree->right))//если существует правй потомок, ищем минимальный элемент в правом поддереве
return SMin(Tree->right); //Ищем минимальный элемент правого поддерева
cout<<endl<<"Element posledniy"<<endl;
return NULL;
}
 
PNode PrevOf(PNode Tree){ //Определение предыдущего элемента
if(!Tree) return NULL;//если дерево пусто-возвращаем нулвой указатель
if(!(!Tree->left))//если существует левый потомок, ищем максимальный элемент в левом поддереве
return SMax(Tree->left); //Ищем максимальный элемент левого поддерева
cout<<endl<<"Element pervij"<<endl;
return NULL;
}
 
int *PrLKP(PNode Tree, int *data, int &iter){ //Вспомогательная функция для создания массива заполненного выводом в стиле ЛКП
if (!Tree) return NULL; // пустое дерево – окончание рекурсии
PrLKP(Tree->left, data, iter); // обход левого поддерева
data[++iter] = Tree->key; //заполнение возвращаемого массива
PrLKP(Tree->right, data, iter); // обход правого поддерева
return data;
}
bool CheckTree(PNode &Tree, int n){ //Функция, определяющая является ли двоичное дерево деревом поиска (элементы дложны возрастать)
if(!Tree) return true;
if(!Tree->left & !Tree->right) return true;
int *data = new int[n];
int iter = -1;
int k = 0;
data = PrLKP(Tree, data, iter);
cout<<endl;
for(int j = 0; j<n-1; ++j){
if(data[j] <= data[j+1])
++k;
}
if(k == n-1)
return true;
else
return false;
}
 
void AddToTree(PNode &Tree, int data){ //Добавление узла дерева поиска
if(!Tree){ //если дерево пустое, то создаем узел
Tree = new Node;
Tree->key = data;
Tree->left = NULL;
Tree->right = NULL;
return;
}
if(data < Tree->key) //если узел создан, то мы добавляем его в дерево на опред. позицию
AddToTree(Tree->left, data);
else
AddToTree(Tree->right, data);
}
 
PNode CreateSearchTree(int *data, int n){ //Создание дерева поиска
PNode Tree = 0;
for(int i = 0; i<n; ++i)
AddToTree(Tree, data[i]);
return Tree;
}
 
PNode FatherOf(PNode &Tree, PNode Son){ //Поиск "отца" указанного "сына"
if(!Tree) return NULL;
if((Tree->left == Son) | (Tree->right == Son))
return Tree;
if(!FatherOf(Tree->left, Son)) //Если "Отец" не найден в левом поддереве ищем в правом
FatherOf(Tree->right, Son);
}
 
void DeleteNode(PNode &Tree, PNode DelNode){ //Удаление узла дерева поиска
if(!DelNode){
cout<<"Udalyaemogo uzla net";
return;
}
else{
if(!Tree) return; //Дерево пустое
if((!Tree->left) & (!Tree->right)){ //Дерево состоит из корня
if(DelNode == Tree)
delete Tree;
return;
}
if((!DelNode->left) & (!DelNode->right)){ //1
if(FatherOf(Tree, DelNode)->left == DelNode)
FatherOf(Tree, DelNode)->left = 0;
else
FatherOf(Tree, DelNode)->right = 0;
delete DelNode;
return;
}
if((!DelNode->left) & !(!DelNode->right)){ //2 случай: у удаляемого узла есть только "правый потомок"
if(DelNode == Tree){ //если узел является корнем
Tree = DelNode->right;
delete DelNode;
return;
}
if(FatherOf(Tree, DelNode)->left == DelNode) //Смотрим каким "потомком" является удаляемый узел
FatherOf(Tree, DelNode)->left = DelNode->right;
else
FatherOf(Tree, DelNode)->right = DelNode->right;
delete DelNode;
return;
}
if(!(!DelNode->left) & (!DelNode->right)){ //2 случай: у удаляемого узла есть только "левый потомок"
if(DelNode == Tree){ //Проверяем является ли удаляемый узел корнем
Tree = DelNode->left;
delete DelNode;
return;
}
if(FatherOf(Tree, DelNode)->left == DelNode) //Смотрим каким "потомком" является удаляемый узел
FatherOf(Tree, DelNode)->left = DelNode->left;
else
FatherOf(Tree, DelNode)->right = DelNode->left;
delete DelNode;
return;
}
if(!(!DelNode->left) & !(!DelNode->right)){ //3 случай: у удаляемого узла есть оба "потомка"
DelNode->key = SMin(DelNode->right)->key; //Ищем минимальный элемент правого поддерева и записываем его в поле удаляемого узла
DeleteNode(DelNode, SMin(DelNode->right)); //Удаляем минимальный элемент правого поддерева
return;
}
}
}
 
PNode Search(PNode Tree, int what){ //Поиск ключа в дереве поиска
if(!Tree) return NULL;
if(what == Tree->key) return Tree;
if(what < Tree->key)
return Search(Tree->left, what);
else
return Search(Tree->right, what);
}
 
int main(){
//int data[] = {21, 7, 6, 19, 100, 17, 13, 18, 20, 33, 38, 63, 51, 260, 180};
int data[] = { 180,-21, 7, 6, 5, 100, 17, 13, 18, 31, 33, 38, 63, 51, -260};
int n = sizeof(data)/sizeof(int);
cout<<"Ishodniy massiv ";
for(int i=0; i<n; ++i){
cout<<data[i]<<" ";
}
cout<<endl;
PNode Tree = CreateSearchTree(data, n); //Создание дерева поиска
 
PNode ikey = Search(Tree, 50); //Поиск ключа в дереве поиска
if(!ikey)
cout<<"Kluch ne naiden"<<endl;
else
cout<<"Kluch = "<<ikey->key<<endl;
 
PNode imin = SMin(Tree); //Поиск минимального и максимального элемента
PNode imax = SMax(Tree);
if(!imin)
cout<<"Derevo pusto"<<endl;
else
cout<<"min element = "<<imin->key<<endl;
if(!imax)
cout<<"Derevo pusto"<<endl;
else
cout<<"max element = "<<imax->key<<endl;
 
PNode inext = NextOf(Search(Tree, 7)); //поиск следующего элемента
if(!!inext)
cout<<"Next element = "<<inext->key<<endl;
 
PNode iprev = PrevOf(Search(Tree, 63)); //поиск предыдущего элемента
if(!!iprev)
cout<<"Previous element = "<<iprev->key<<endl;
 
cout<<endl<<"Vivod LKP -> -> ->"; //Вывод дерева поиска на печать
PrintLKP(Tree);
cout<<endl<<"Vivod KLP -> ";
PrintKLP(Tree);
cout<<endl<<"Vivod LPK -> ";
PrintLPK(Tree);
 
cout<<endl<<"Proverka na derevo poiska "<<CheckTree(Tree, n)<<endl; //Проверка на дерево поиска
 
DeleteNode(Tree, Search(Tree, 19)); //Удаляем узел с заданным ключом
 
cout<<endl<<endl<<"Novoe derevo poiska:"<<endl; //Вывод нового дерева поиска на печать
cout<<endl<<"Vivod LKP -> ";
PrintLKP(Tree);
cout<<endl<<"Vivod KLP -> ";
PrintKLP(Tree);
cout<<endl<<"Vivod LPK -> ";
PrintLPK(Tree);
cout<<endl;
getch();
//system("pause");
return 0;
}
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.12.2014, 20:52
Я подобрал для вас темы с готовыми решениями и ответами на вопрос Рекурсивные Деревья (C++):

Рекурсивные деревья - C++
День добрый. Очень нужна помощь в решении задачи: Найти все поддеревья, структура которых совпадает с заданной. ...

Рекурсивные и не рекурсивные функции (вычисление суммы всех натуральных чисел от 1 до n) - C++
Всем привет. Заранее извиняюсь за мб глупые вопросы и навязчивость. Но у меня есть одна просьба. Помогите пожалуйста написать...

рекурсивные алгоритмы - C++
помогите с задачкой пожалуйста надо разработать программную рекурсивную функцию, выводящую на пе-чать n символов латинского алфавита в...

рекурсивные классы - C++
Доброго времени суток. Скажите пожалуйста, можно ли при написании класса объявить в нём поле того же типа что и сам класс? Компилятор...

рекурсивные функции - C++
1. Найти НОД (наибольший общий делитель) двух натуральных чисел. 2. В одномерном массиве, состоящем из n целых элементов, вычислить номер...

Рекурсивные алгоритмы - C++
не могу понять как сделать... помогите пожалуйста Написати рекурсивну функцію, що визначає, чи є симетричною частина рядка, ...

1
Людвиг Бодмер
355 / 354 / 137
Регистрация: 29.03.2013
Сообщений: 866
Завершенные тесты: 4
11.12.2014, 13:52 #2
byhukutka, по идее должно всё компилироваться, а какой текст ошибок?
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2014, 13:52
Привет! Вот еще темы с ответами:

Рекурсивные функции - C++
в функции мейн обьявить двумерный массив размером A заполнить случайным образом 1 и 2, вывести масив на экран написать рекурсивную...

РЕКУРСИВНЫЕ АЛГОРИТМЫ - C++
Вывести значение целочисленного выражения, заданного в виде строки S. Выражение определяется следующим образом (функция M воз-вращает...

рекурсивные функции - C++
Дано натуральные числа n,m ; найти НОД(наибольший общий делитель) . Использовать программу, которая содержит рекурсивную процедуру...

Рекурсивные функции - C++
Всем привет. Ребят, помогите. Задание: с помощью рекурсивной функции вычислить сумму элементов одномерного массива. Не спец в этом, задали...


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

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

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