17 / 17 / 0
Регистрация: 18.05.2011
Сообщений: 33
|
|
|
1
|
Найти глубину дерева, представляемую как наибольшая длина пути от корня к листьям.
06.12.2011, 00:03. Показов 2742. Ответов 1
В общем дано двоичное дерево надо была найти глубину дерева, представляемую как наибольшая длина пути от корня к листьям. Правильно ли прога это делает?
| Pascal | 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
| uses
crt;
type
PNode = ^Node; {Указатель на узел}
Node = record {Тип запись в котором будет храниться информация}
data: integer;
left, right: PNode; {Ссылки на левого и правого сыновей}
end;
var
Tree, p1: PNode; {Tree адрес корня дерева, p1-вспомогательная переменная}
n, x, i, max: integer;
ch: char; {для работы менюшки}
{Процедура добавления элемента }
procedure AddToTree(var Tree: PNode; x: integer);{Входные параметры - адрес корня дерева и добавл элемент }
begin
if Tree = nil then {Если дерево пустое то создаём его корень}
begin
New(Tree); {Выделяем память }
Tree^.data := x; {Добавляем данные }
Tree^.left := nil; {Зануляем указатели на левого }
Tree^.right := nil; {и правого сыновей }
exit;
end;
if x < Tree^.data then {Доб к левому или правому поддереву это завсит от вводимого элемента}
AddToTree(Tree^.left, x) {если меньше корня то в левое поддерево }
else
AddToTree(Tree^.right, x); {если больше то в правое}
end;
procedure node_length(var Tree: PNode);
var
l, r: PNode;
begin
if (Tree^.left <> nil) and (Tree^.right <> nil) then
begin
l := Tree^.left;
r := Tree^.right;
node_length(l);
node_length(r);
writeln(max);
inc(max);
end;
if (Tree^.left <> nil) and (Tree^.right <> nil) then max := max - 1;
if (Tree^.left <> nil) or (Tree^.right <> nil) then max := max + 1;
end;
{Функция поиска по дереву}
function Search(Tree: PNode): PNode;{Возвращает адрес искомого элемента, nil если не найден}
var
p: PNode; {вспомог переменнная }
begin
if (Tree^.left <> nil) and (Tree^.right <> nil) then
begin
if Tree^.left = nil then p := Search(Tree^.right);
if Tree^.right = nil then p := Search(Tree^.left);
p := Search(Tree^.right);
p := Search(Tree^.left);
end;
Search := p;
end;
{Обход дерева по принципу Левый-корень-правый }
procedure Lkp(Tree: PNode);
begin
if Tree = nil then {Если дерево пустое }
exit; {то выход }
Lkp(Tree^.left); {иначе начинаем обход с левого подднрева}
write(' ', Tree^.data); {выводим данные }
Lkp(Tree^.right); {обходим правое поддерево}
end;
{Процедура удаления дерева}
procedure DeleteTree(var Tree1: PNode );
begin
if Tree1 <> nil then
begin
DeleteTree(Tree1^.LEFT);
DeleteTree(Tree1^.RIGHT);
Dispose(Tree1);
end;
end;
{основная пограмма}
begin
Tree := nil;
repeat {цикл для нашего меню}
Writeln('Выберете действие ');
Textcolor(3);
Writeln('______________________');
Writeln('1) Создание дерева ');
Writeln('2) Глубина дерева');
Writeln('3) Вывод дерева');
Writeln('4) Выход');
writeln;
readln(ch); {ожидаем нажатия клавиши}
case ch of {выбираем клавишу}
'1':
begin
writeln(' Введите количество элементов дерева :');
readln(n);
for i := 1 to n do
begin
writeln('Введите элемент');
readln(x);
clrscr;
AddToTree(Tree, x);
end;
end;
'2':
begin
max := 1;
node_length(Tree);
writeln('Глубина дерева ', max);
end;
'3':
begin
writeln(' Дерево');
Lkp(Tree);
writeln;
end;
end;
until ch = '4';
DeleteTree(Tree);
end. |
|
1
|
(
