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
| type
PNode = ^TNode;
TNode = record
Data: integer;
Left: PNode;
Right: PNode;
end;
// Создание нового узла
function NewNode(Value: integer): PNode;
var
Node: PNode;
begin
New(Node);
Node^.Data := Value;
Node^.Left := nil;
Node^.Right := nil;
NewNode := Node;
end;
// Добавление элемента в дерево
procedure Insert(var Root: PNode; Value: integer);
begin
if Root = nil then
Root := NewNode(Value)
else if Value < Root^.Data then
Insert(Root^.Left, Value)
else
Insert(Root^.Right, Value);
end;
// Удаление элемента из дерева
function Delete(var Root: PNode; Value: integer): boolean;
var
Temp: PNode;
begin
if Root = nil then
Delete := false
else if Value < Root^.Data then
Delete := Delete(Root^.Left, Value)
else if Value > Root^.Data then
Delete := Delete(Root^.Right, Value)
else
begin
if (Root^.Left = nil) and (Root^.Right = nil) then
begin
Dispose(Root);
Root := nil;
end
else if Root^.Left = nil then
begin
Temp := Root;
Root := Root^.Right;
Dispose(Temp);
end
else if Root^.Right = nil then
begin
Temp := Root;
Root := Root^.Left;
Dispose(Temp);
end
else
begin
Temp := Root^.Right;
while Temp^.Left <> nil do
Temp := Temp^.Left;
Root^.Data := Temp^.Data;
Delete(Root^.Right, Temp^.Data);
end;
Delete := true;
end;
end;
// Обход дерева симметрично позволяет вывести все значения в дереве в порядке возрастания.
procedure InorderTraversal(Root: PNode);
begin
if Root <> nil then
begin
InorderTraversal(Root^.Left);
Write(Root^.Data, ' ');
InorderTraversal(Root^.Right);
end;
end;
// Обход дерева прямым способом позволяет вывести значения в дереве в порядке, в котором они были добавлены.
procedure PreorderTraversal(Root: PNode);
begin
if Root <> nil then
begin
Write(Root^.Data, ' ');
PreorderTraversal(Root^.Left);
PreorderTraversal(Root^.Right);
end;
end;
// Обход дерева обратным способом позволяет вывести значения в дереве в порядке, обратном порядку, в котором они были добавлены.
procedure PostorderTraversal(Root: PNode);
begin
if Root <> nil then
begin
PostorderTraversal(Root^.Left);
PostorderTraversal(Root^.Right);
Write(Root^.Data, ' ');
end;
end;
// Поиск элемента в дереве
function Search(Root: PNode; Value: integer): boolean;
begin
if Root = nil then
Search := false
else if Root^.Data = Value then
Search := true
else if Value < Root^.Data then
Search := Search(Root^.Left, Value)
else
Search := Search(Root^.Right, Value);
end;
var
Root: PNode;
Choice, Value: integer;
begin
Root := nil;
repeat
WriteLn('1. Dobavit element');
WriteLn('2. Udalit element');
WriteLn('3. Obhod dereva semetri4no');
WriteLn('4. Obhod dereva pryamim sposobom');
WriteLn('5. Obhod dereva obratnim sposobom');
WriteLn('6. Poisk elementa');
WriteLn('7. Vihod');
Write('Vibirite deystvie: ');
ReadLn(Choice);
case Choice of
1:
begin
Write('Vvedite zna4enie: ');
ReadLn(Value);
Insert(Root, Value);
end;
2:
begin
Write('Vvedite zna4enie: ');
ReadLn(Value);
if Delete(Root, Value) then
WriteLn('Element udalen ')
else
WriteLn('Element ne nayden');
end;
3:
begin
Write('Simmetri4niy obhod: ');
InorderTraversal(Root);
WriteLn;
end;
4:
begin
Write('Pryamoy obhod: ');
PreorderTraversal(Root);
WriteLn;
end;
5:
begin
Write('Obratniy obhod: ');
PostorderTraversal(Root);
WriteLn;
end;
6:
begin
Write('Vvedite zna4enie: ');
ReadLn(Value);
if Search(Root, Value) then
WriteLn('Element nayden')
else
WriteLn('Element ne nayden');
end;
end;
until Choice = 7;
end. |
(
Сообщение от raiinc
