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
| #pragma once
template<class T>
class set
{
public:
//открытый интерфейс класса set
set() //деструктор создает пустое множество
{
root = 0;
}
void erase(const T& val)
{
if (find(val) == false) return;
node_ptr& ref = insert_find(root, val);
if (ref->left == 0)
{
node * temp = ref->right;
delete ref;
ref = temp;
}
else if (ref->right == 0)
{
node * temp = ref->left;
delete ref;
ref = temp;
}
else
{
node * t;
t = ref->right;
while (t->left != 0) t = t->left;
t->left = ref->left;
node * temp = ref->right;
delete ref;
ref = temp;
}
}
void insert(const T& val)
{
if (find(val) == true) return;
if (root == 0)
{
root = new node(val, 0, 0);
return;
}
insert_find(root, val) = new node(val, 0, 0);
}
bool find(const T& val)
{
node * temp = find(root, val);
if (temp != 0) return true; else return false;
}
~set()//удаляет все узлы двоичного дерева
{
destructor(root);
}
private:
struct node
{
T data;
node *left;
node *right;
node(const T& val, node* l, node * r) :data(val), left(l), right(r) {}
};
typedef node* node_ptr;
node* find(node * root_subtree, const T& val) //рекурсивный поиск
//узла, содержащего значение val, в поддереве, на корень которого
// указывает root_subtree
{
if (root_subtree == 0) return 0;
node * cur = root_subtree;
if (!(val < cur->data) && !(cur->data < val)) return cur;
if (val < cur->data) return find(cur->left, val);
else return find(cur->right, val);
}
node_ptr& insert_find(node_ptr& root_subtree, const T& val) //
{
if (val < root_subtree->data)
{
if (root_subtree->left == 0) return root_subtree->left;
else return insert_find(root_subtree->left, val);
}
else if (root_subtree->data < val)
{
if (root_subtree->right == 0) return root_subtree->right;
else return insert_find(root_subtree->right, val);
}
return root_subtree;
}
void destructor(node * root_subtree) //рекурсивная процедура удаляющая все узлы
//из поддерева, на корень которого указывает root_subtree
{
if (root_subtree == 0) return;
destructor(root_subtree->left);
destructor(root_subtree->right);
delete root_subtree;
}
node * root; //указатель на корень дерева поиска
}; |
(
