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
| struct Node {
int *d;
int size;
int extendSize(int x);
Node(int size) {
this->size = extendSize(size);
this->d = new int[this->size];
for (int i = 0; i < this->size; i++) {
d[i] = 0;
}
}
};
int Node::extendSize(int x)
{
int value = 0;
for (int y = 0; y < x + 1; y++) {
value = (2 * value) + 2;
}
return value;
}
void Tree_Insert(Node *&p, int d)
{
int index = 0;
while (true) {
if (p->d[index] == NULL) {
p->d[index] = d;
break;
}
else if (p->d[index] <= d) {
if (p->d[index] == d)
break;
else
index = (2 * index + 2);
}
else if (p->d[index] >= d) {
if (p->d[index] == d)
break;
else
index = (2 * index + 1);
}
}
}
void inorder_Tree(Node * p, int index)
{
if (p->d[index] != NULL) {
inorder_Tree(p, 2 * index + 1);
cout << p->d[index] << " ";
inorder_Tree(p, 2 * index + 2);
}
}
int Tree_Search(Node * p, int d, int index)
{
if (p == 0 || p->d[index] == d)
return p->d[index];
if (d < p->d[index])
Tree_Search(p, d, 2 * index + 1);
else
Tree_Search(p, d, 2 * index + 2);
}
int main()
{
setlocale(0, "");
int size = 0;
cout << "Введите размер дерева: ";
cin >> size;
Node *root= new Node(size);
int x, el = 0;
cout << "Введите ";
for (int i = 0; i < size; i++)
{
cin >> x;
Tree_Insert(root, x);
}
cout << "Симметричный обход дерева ";
inorder_Tree(root, 0); cout << endl;
cout << "Искомый элемент: " << Tree_Search(root, el, 0) << endl;
system("pause");
return 0;
} |
(
