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
| Program bin_tree;
{
Задача.
Построить двоичное дерево, элементами которого являются
числа.
}
Uses Crt;
Const
A { данный массив-константа }
: array [1..12] of integer
= (70, 60, 85, 87, 90, 45, 30, 88, 35, 20, 86, 82);
Type
zap = ^element;
element = record
n { число из массива }
: integer;
lev, { адрес левой ветки }
prav { адрес правой ветки }
: zap;
end;
Var
i { номер элемента массива }
: integer;
tek_v, { текущая вершина дерева }
lev_v, { левая вершина дерева }
prav_v, { правая вершина дерева }
root_v, { корень дерева }
pred_v, { вершина предыдущая }
new_v { новая, только что порожденная вершина с помощью New }
: zap;
Procedure sozd_dereva (
k { число-ключ - значение
вершины дерева }
: integer
);
{
LEV, 9.06.11, 14:50,
Алгоритм построения дерева
}
var
key { ключ - значение вершины дерева }
: integer;
begin
{
если дерево еще не построено, то создаем корень дерева
}
if tek_v = nil
then
begin
New (tek_v);
tek_v^.n := k;
tek_v^.lev := nil;
tek_v^.prav := nil;
root_v := tek_v;
pred_v := tek_v;
Exit;
end;
{
добавление следующих вершин дерева
}
{
поля новой вершины
}
New (new_v);
new_v^.n := k;
new_v^.lev := nil;
new_v^.prav := nil;
{
будем двигаться вниз по дереву, влево или вправо и сравнивать key с k.
Цикл закончим тогда, когда придем на вершину, значение которой nil.
}
tek_v := root_v;
key := root_v^.n; { значение корня дерева }
while tek_v <> nil do
begin
{I. }
if (k <= key)
then
if (tek_v^.lev = nil)
then
begin
{ записываем адрес новой вершины
в текущую левую ветку }
tek_v^.lev := new_v;
WriteLn ('прошла установка ', k, ' налево, после ', tek_v^.n);
Break;
end
else
begin
tek_v := tek_v^.lev;
key := tek_v^.n;
Continue;
end;
{II. }
if (k > key)
then
if (tek_v^.prav = nil)
then
begin
{ записываем адрес новой вершины
в текущую правую ветку }
tek_v^.prav := new_v;
WriteLn ('прошла установка ', k, ' направо, после ', tek_v^.n);
Break;
end
else
begin
tek_v := tek_v^.prav;
key := tek_v^.n
end;
end; { end while, конец поиска nil }
end; { end sozd_dereva окончание построения дерева }
Procedure del_tree (
p { адрес узла дерева }
: zap
);
{
LEV, 9.06.11, 14:55,
Уничтожение дерева
}
begin
if p <> nil
then
begin
del_tree (p^.lev);
del_tree (p^.prav);
Dispose (p);
end;
end;
Begin
ClrScr;
{
Двоичное дерево еще не построено
}
tek_v := nil;
WriteLn ('Построим двоичное дерево.');
WriteLn;
for i := 1 to 12 do
begin
sozd_dereva (A [i]);
end;
WriteLn;
WriteLn ('Двоичное дерево построено.');
{
Уничтожим дерево (отдадим память назад OS)
}
del_tree (root_v);
WriteLn;
WriteLn ('Двоичное дерево уничтожено.');
ReadLn;
End. |
(
