Базовые операции с бинарным деревом
30.09.2018, 16:27. Показов 2843. Ответов 0
Добрый день! Прошу помощи в выполнении задания. Задача стоит следующая: создать бинарное дерево с функциями добавления удаления и сортировки элементов. Язык - с++.
Сложности возникают с сортировкой.
Самому толком найти ни чего не удалось. В ходе изучения темы наковырял вот такой код:
| 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
| #include <iostream> // for cin cout
using namespace std;
struct TREE
{
int d; // число
TREE *left; //указатель на левое поддерево
TREE *rigth; //указатель на правое поддерево
};
void first (TREE *&,int );
TREE* search (TREE *, int );
void find (TREE *, TREE *&, int );
void add (TREE *, int );
void print_tree (TREE * );
void print_tree_level (TREE *, int );
void del_tree (TREE *&top);
int main( void )
{
int b[ ] = {20, 10, 8, 12, 30, 25, 34, 22};
TREE *top;
first(top, b[0]); //формирование первого узла дерева
for (int i = 1; i < 8; i++)
add (top, b[i]); // добавление узлов дерева
cout<<" tree1";
print_tree (top); // вывод элементов дерева на экран
cout<< endl;
cout<<" tree2";
print_tree_level(top,0);
// вывод элементов дерева на экран по уровням
del_tree(top) ; // удаление дерева
cout<<" tree3";
print_tree (top); // проверка того, что дерево пусто
cout<< endl;
}
// формирование первого узла дерева
void first (TREE *&top, int d)
{
top = new TREE;
top -> d = d;
top -> left = top -> rigth = NULL;
}
// поиск места для нового узла
// возвращаем адрес узла, после которого нужно добавить
// новый элемент
TREE* search(TREE *top, int d)
{
TREE *pv = top, *ppv;
while (pv)
{ ppv = pv;
if (d < pv -> d)
pv = pv -> left;
else
pv = pv -> rigth;
}
return ppv;
}
// поиск места для нового узла рекурсивный вариант
// возвращаем адрес узла, после которого нужно добавить новый элемент
void find(TREE *top, TREE *&p, int d)
{
if (top)
{
p = top;
if (d < top -> d )
find(top -> left, p, d);
else
find(top -> rigth, p, d);
}
else
p = NULL;
}
// включение нового узла
void add (TREE *top, int d)
{
TREE *ppv,*pnew = new TREE; // создаем новый узел
pnew -> d = d;
pnew -> left= NULL;
pnew -> rigth = NULL;
ppv = search(top, d); // поиск места для нового узла
// find(top, ppv,d); // или так
if (d < ppv -> d)
ppv -> left = pnew;
//присоединение к левому поддереву предка
else
ppv -> rigth = pnew;
//присоединение к правому поддереву предка
}
// обход дерева и вывод значений в отсортированном порядке
void print_tree (TREE * top)
{
if (top)
{
print_tree (top -> left); //обход левого поддерева
cout << top -> d << " ";
print_tree(top -> rigth);//обход правого поддерева
}
}
// обход дерева и вывод значений по уровням
void print_tree_level(TREE * top, int level)
{
if (top)
{
print_tree_level (top -> left, level + 1);
//обход левого поддерева
for (int i = 0; i < level; i++)
cout <<" ";
cout << top ->d <<endl;
print_tree_level(top -> rigth, level + 1);
//обход правого поддерева
}
}
// удаление дерева
void del_tree (TREE *&top)
{
if (top)
{
del_tree (top -> left); //обход левого поддерева
del_tree(top -> rigth);//обход правого поддерева
delete top; // освобождение памяти
top = NULL;
}
} |
|
И вот еще ( то что надо мне но с поиском) :
| 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
| #include<iostream>
#include<locale.h>
using namespace std;
#define TRUE 1
#define FALSE 0
struct node
{
int Key;
int Count;
node *Left;
node *Right;
};
class TREE
{
private:
node *Tree;//Указатель на корень дерева.
node *Res;//Указатель на найденную вершину.
int B; //Признак нахождения вершины в дереве.
//Поиск вершины в дереве (рекурсивный алгоритм).
void Search (int, node**);
void Delete_1 (node**,node**);
public:
TREE() { Tree = NULL;}
node** GetTree() {return &Tree;}
void BuildTree ();//Построение бинарного дерева.
//Вывод дерева на экран (рекурсивный алгоритм).
void Vyvod (node**,int);
//Поиск вершины в дереве (нерекурсивный алгоритм).
int Poisk (int);
// Удаление вершины из дерева.
void Delete (node**, int);
};
int main ()
{
TREE A;
int el;
A.BuildTree (); A.Vyvod (A.GetTree(),0);
setlocale(LC_ALL, "Rus");
cout<<"Введите ключ вершины, которую нужно найти в дереве: ";
cin>>el;
if (A.Poisk (el)) cout<<"В дереве есть такая вершина!\n";
else cout<<"В дереве нет такой вершины!\n";
cout<<"Введите ключ удаляемой вершины: "; cin>>el;
A.Delete (A.GetTree(),el); A.Vyvod (A.GetTree(),0);
}
void TREE::BuildTree ()
//Построение бинарного дерева.
//Tree - указатель на вершину дерева.
{
int el;
setlocale(LC_ALL, "Rus");
cout<<"Вводите ключи вершин дерева: \n";
cin>>el;
while (el!=0)
{ Search (el,&Tree);cin>>el; }
}
void TREE::Vyvod (node **w,int l)
//Изображение дерева w на экране дисплея
// (рекурсивный алгоритм).
//*w - указатель на корень дерева.
{
int i;
if (*w!=NULL)
{
Vyvod (&((**w).Right),l+1);
for (i=1; i<=l; i++) cout<<" ";
cout<<(**w).Key<<endl;
Vyvod (&((**w).Left),l+1);
}
}
void TREE::Search (int x,node **p)
//Поиск звена x в бинарном дереве со вставкой
// (рекурсивный алгоритм).
//*p - указатель на вершину дерева.
{
if (*p==NULL)
{ // Вершины в дереве нет; включить ее.
*p = new(node);
(**p).Key = x; (**p).Count = 1;
(**p).Left = (**p).Right = NULL;
}
else
if (x<(**p).Key) Search (x,&((**p).Left));
else
if (x>(**p).Key) Search (x,&((**p).Right));
else (**p).Count += 1;
}
int TREE::Poisk (int k)
// Поиск вершины с ключом k в дереве
// (нерекурсивный алгоритм).
// Tree - указатель на бинарное дерево.
// Res - указатель на найденную вершину
// или на лист, к которому можно присоединить новую вершину.
{
node *p,*q;
B = FALSE; p = Tree;
if (Tree!=NULL)
do
{
q = p;
if ((*p).Key==k) B = TRUE;
else
{
q = p;
if (k<(*p).Key) p = (*p).Left;
else p = (*p).Right;
}
} while (!B && p!=NULL);
Res = q;
return B;
}
void TREE::Delete (node **p,int k)
// Удаление вершины k из бинарного дерева.
// *p - указатель на корень дерева.
{
node *q;
if (*p==NULL) cout<<"Вершина с заданным ключом не найдена!\n";
else
if (k<(**p).Key) Delete (&((**p).Left),k);
else
if (k>(**p).Key) Delete (&((**p).Right),k);
else
{
q = *p;
if ((*q).Right==NULL) {*p = (*q).Left; delete q;}
else
if ((*q).Left==NULL) { *p = (*q).Right; delete q; }
else Delete_1 (&((*q).Left),&q);
}
}
void TREE::Delete_1 (node **r,node **q)
{
node *s;
if ((**r).Right==NULL)
{
(**q).Key = (**r).Key; (**q).Count = (**r).Count;
*q = *r;
s = *r; *r = (**r).Left; delete s;
}
else Delete_1 (&((**r).Right), q);
} |
|
0
|
(
