Данная статья была написана с целью изложения некоторых принципов работы с древовидными структурами данных. В частности, для работы с бинарными деревьями поиска посредством совершения над ними операций. Сразу оговорюсь, что это моя первая статья, и что она подразумевает наличие у читающих некоторых знаний из теории деревьев. В основном, это понятие самого дерева, корня, листов, предков, потомков, сыновей и так далее. Но кое-что стоит все же вспомнить.
Немного из теории:
Как уже многие знают, бинарное (двоичное) дерево поиска – это связный (есть путь между любой парой вершин) ациклический (отсутствие замкнутости) граф, который обладает следующими свойствами:
- У любого дерева обязательно есть корень – такая вершина, на которую не ссылается ни одна другая. Это как бы начало, основа - корень, одним словом.
- От корня, так же, как и от любой другой вершины, должно исходить не более двух ветвей к другим вершинам (сыновьям). На каждый элемент, кроме корня, имеется один указатель.
- Бинарное дерево поиска заранее должно быть упорядочено.
Названо оно так потому, что схоже с обычным деревом, правда растет почему-то вниз.
Соответственно, несколько деревьев уже образуют лес.
Конечно же, есть разные формы его изображения (например, метод вложенных скобок, оглавление книги или вовсе диаграмма), т.к. все-таки это абстрактная структура данных. Наиболее распространенная из них и, на мой взгляд, наиболее удобная для восприятия изображена на рисунке. Это касаемо любых видов структуры, будь то бинарные или Б-деревья и т.д.
Итак, какие же основные операции определены над деревом? Их несколько: - Поиск узла с заданным ключом.
- Добавление нового узла.
- Удаление узла (поддерева).
- Обход дерева в определенном порядке:
- Нисходящий обход.
- Восходящий обход.
- Смешанный обход.
- Поиск глубины.
Не будем углубляться во все операции, такие как, поиск отца или сына, включение узла в дерево слева от данного и т.д. В данной статье они рассматриваться не будут, так же, как и некоторые пункты со списка выше 
А теперь определимся, что же будет включено в статью или, иными словами, какова ее истинная цель.
Во-первых, дерево будет организовано массивом. Процедуры только нерекурсивные. Почему? Поясню: организация с помощью указателей – способ хоть и не из легких (для начинающих или непонимающих, у кого что), однако гугл с первой же по списку ссылки попадает в цель, отсюда интерес к такому методу реализации уже не так велик. А массивы – другое дело: ни информации тебе, ни кода, а люди-то просят. Почему не рекурсия: для деревьев рекурсия очень приемлема и существенно облегчает написание кода, однако «подобное» в любом учебном заведении при сдаче (будь то лабораторная, контрольная, зачет, курсовая, экзамен, не важно) не прокатит. Рекурсия – как вариант, но не основа. К тому же более углубленное знание структуры записи и самого алгоритма не повредит.
Во-вторых, процедур будет несколько, но они не должны затруднить восприятие из-за своего количества, т.к. схожи между собой по основной идее написания.
В-третьих, я постарался прокомментировать каждую строчку, а для отдельных блоков кода комментарии будут в несколько предложений для более полного пояснения.
Не по теме:
Вообще, на написание статьи меня вдохновило именно отсутствие информации или хоть какого-нибудь кусочка кода в сети. Гугл молчал, я был в отчаянии: сдавать-то надо, а сроки подходят. Пришлось, как в таких случаях некоторые поступают, писать самому. Правда, тогдашний мой код был не особо оптимизированным, поэтому на момент написания статьи его пришлось править почти полностью.
После небольшого отступления перейдем к теме статьи.
Итак, полное задание: реализовать дерево массивом и составить списки узлов дерева при обходе этого дерева в прямом порядке (процедура обхода должна быть нерекурсивной). Найти глубину дерева.
Процедур будет в количестве 4 штук:- Добавление узла (procedure FormTree(var n: integer; var a: artree));
- Просмотр дерева (таблично) (procedure PrintTree(i: integer));
- Список узлов при прямом обходе (procedure List(n: integer; a: artree));
- Глубина дерева (procedure Depth(n: integer; a: artree)).
Вот такой скромный список.
Начнем с формирования самого дерева и посмотрим, как же добавлять узлы.
Начальное формирование дерева происходит так:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
| {Узел = вершина}
const
N = 500; { количество элементов в дереве }
{ Инициализация дерева }
{ val - текущая вершина, left, right - левый и правый сыновья соответственно }
type
tree = record
val, left, right: integer;
flagL, flagR: boolean; { флаги для метки просмотренных вершин }
end;
{ массив + вершина со ссылками на двух сыновей = дерево }
artree = array [1..N] of tree; |
|
Процедура добавления узла в дерево:
| 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
| procedure FormTree(var i: integer; var a: artree);
{
Формирует дерево при помощи массива записей
i - счетчик узлов в дереве;
a - само дерево
}
var
j: integer;
begin
{
Добавление узла в дерево.
Вначале значение узла записывает в ячейку массива,
далее определятся, к какому узлу (вернее к какому сыну (левому или
правому)) оно должно принадлежать
(его индекс записывается в одну из двух (левого или правого)
ячеек элемента, к которому он будет привязан)
}
if a[1].val = 0 then
begin
write('Корень: ');
readln(a[1].val); { ввод корня дерева }
i := 1;
end
else
begin
inc(i); { переходим к следующей ячейке массива для ее заполнения }
j := 1; { индекс добавляющего узла }
write('Узел #', i, ': ');
readln(a[i].val); { ввод последующих узлов }
while true do
begin
{---Добавление узла к вершине "справа"---}
{ сравнение текущего узла с добавляемым }
if a[i].val >= a[j].val then
begin
if a[j].right = 0 then { у этого узла нет сына }
begin
a[j].right := i; { добавляем индекс добавляемого узла }
break; { выходим из цикла для последующего добавления }
end
else { иначе }
if a[j].right <> 0 then
begin
{
узнаем индекс элемента,
стоящего на месте занятой вершины.
Этот элемент станет текущим.
Продолжаем поиск
}
j := a[j].right;
continue;
end;
end;
{---Добавление узла к вершине "слева"---}
{ сравнение текущего узла с добавляемым }
if a[i].val < a[j].val then
begin
if a[j].left = 0 then { у этого узла нет сына }
begin
a[j].left := i; { добавляем индекс добавляемого узла }
break;
end
else { иначе }
if a[j].left <> 0 then
begin
{
узнаем индекс элемента,
стоящего на месте занятой вершины.
Этот элемент станет текущим.
Продолжаем поиск
}
j := a[j].left;
continue;
end;
end;
end;
end;
end; |
|
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| .........................
if a[i].val < a[j].val then
begin
if a[j].left = 0 then { у этого узла нет сына }
begin
a[j].left := i; { добавляем индекс добавляемого узла }
break;
end
else { иначе }
if a[j].left <> 0 then
begin
{
узнаем индекс элемента,
стоящего на месте занятой вершины.
Этот элемент станет текущим.
Продолжаем поиск
}
j := a[j].left;
continue;
end;
end;
end;
......................... |
|
| Так вводятся узлы: | Так мы представляем себе дерево: | Так оно выглядит на самом деле в Паскале: | | | | | | | | //Массив записей типа tree |
Можно продвинуться дальше по примеру и увидеть абсолютно схожие действия:
Стоит еще раз отметить, что поля left и right массива хранят индексы элементов, а не их значения. Так намного удобней перемещаться по дереву. Булевы флаги FlagL и FlagR в этой процедуре не используются, они нужны только для отметки просмотренных вершин и, в данном случае, имеют стандартное значение false, об этом далее. На этом по процедуре добавления все.
Процедура вывода дерева на экран в табличном виде:
| 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
| procedure PrintTree(i: integer);
{ Вывод дерева в табличном виде }
var
k, x, y: integer;
begin
x := 13; { кооординаты курсора по оси x }
y := 1;
if a[1].val = 0 then { проверяем наличие корня }
writeln('Дерево пусто')
else
begin
clrscr; { очищаем экран, чтоб корректно работала gotoxy }
writeln('Вершина: ');
writeln('Левый сын: ');
writeln('Правый сын: ');
for k := 1 to i do
begin
gotoxy(x, y); { переходим к нужной позиции }
{ выводим вершины }
write(a[k].val:3, ' |');
{ выводим их левых сыновей }
gotoxy(x, y + 1); { переходим к нужной позиции }
if a[k].left <> 0 then
write(a[a[k].left].val:3, ' |')
else
write('nil |');
gotoxy(x, y + 2); { переходим к нужной позиции }
{ выводим их правых сыновей }
if a[k].right <> 0 then
write(a[a[k].right].val:3, ' |')
else
write('nil |');
{ когда элемент = 0 - это все равно, что он
отсутствует (поэтому выводится на экран как значение nil)
}
x := x + 5; { добавляем отступ от предыдущих выведеных значений }
if x >= 70 then { если элементам не хватает места на
одной строке - переносим на другую }
begin
gotoxy(x, y + 1);
write(' --->');
gotoxy(1, 5);
writeln('Вершина: ');
writeln('Левый сын: ');
writeln('Правый сын: ');
y := y + 4;
x := 13;
end;
end;
end;
readln;
clrscr; { очищаем экран }
end; |
|
a[k].left
а так выглядит сама вершина:
a[a[k].left].val
Думаю, здесь все ясно и прозрачно, хоть и с корявым объяснением.
Идем далее. Процедура прямого обхода дерева:
| 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
| procedure List(n: integer; a: artree);
{
Формирует список узлов при прямом обходе
n - количество узлов в дереве;
a - само дерево
}
var
i, j, k: integer;
{
bufInd содержит адреса (индексы) узлов с
не полностью просмотренными сыновьями
}
bufInd: array [0..1000] of integer;
begin
writeln('Список узлов при прямом обходе: ');
i := 0; { массив индексов начинается с 0, обнуляем }
j := 0; { счетчик просмотренных узлов в дереве }
k := 1; { массив узлов начинается с 1 }
write(a[k].val:3); { выводим на экран первый элемент, он же корень дерева }
while j <> n do { пока не будут просмотрены все вершины }
begin
if (a[k].flagl = false) or (a[k].flagr = false) then
{ левый сын текущей вершины существует и еще не просмотрен }
if (a[k].left <> 0) and (a[k].flagl = false) then
begin
a[k].flagl := true; { отмечаем просмотренный узел }
if a[k].right = 0 then { заодно проверяем, отсутствует
ли левый сын, если да, то: }
begin
a[k].flagr := true; { отмечаем просмотренный узел }
inc(j); { узел просмотрен, прибавляем }
end
else { иначе }
begin
bufind[i] := k; { запоминаем его индекс, чтоб впоследствии вернуться }
inc(i); { счетчик для массива индексов }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].left; { переходим на левого сына текущего узла }
write(a[k].val:3); { выводим на экран вершину }
end
else { иначе }
{ левый сын текущей вершины существует и еще не просмотрен }
if (a[k].right <> 0) and (a[k].flagr = false) then
begin
a[k].flagr := true; { отмечаем просмотренный узел }
if a[k].left = 0 then { заодно проверяем, отсутствует
ли левый сын, если да, то: }
begin
a[k].flagl := true; { отмечаем просмотренный узел }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].right; { переходим на правого сына текущего узла }
write(a[k].val:3); { выводим на экран вершину }
end
else { иначе }
{ когда текущая вершина не имеет сыновей) }
begin
dec(i); { в "массиве индексов" переходим на элемент,
который является индексом одной из вершин,
у которой не просмотрен один из сыновей
}
if i >= 0 then { предотвращение выхода за границы диапазона }
k := bufind[i]; { переходим на элемент с одним из не просмотренных сыновей }
inc(j); { узел просмотрен, прибавляем }
end;
end;
writeln;
end; |
|
Вообще, стоит заранее пояснить, что за прямой (нисходящий, префиксный) обход. Прямой обход, а, точнее изъясняясь, составление списка узлов при прямом обходе - так эта операция называется. Алгоритм таков: сначала просматривается и записывается корень дерева, далее просматривается все левое поддерево, а после – все правое. Поддеревья тоже просматриваются по этому же принципу: сначала записывается все, что находится слева от текущей вершины, а потом, начиная с последней записанной вершины, т.е. с самого низу смотрятся все правые вершины. С ними то же самое: у правой вершины есть левое поддерево: смотрим сначала его, а потом уже все остальное. Здесь порядок обхода вершин пронумерован.
Чтобы реализовать это программно, нужно как-то запоминать вершины, которые уже посетил и не возвращаться к ним более. Тут-то как раз и приходят на помощь булевы флаги (в моем случае это FlagL для левый сыновей и FlagR для правых). На деле выходит так: просмотрел вершину – поставил флажок для нее в значение true, перешел к следующей. Кстати, переходим к следующим вершинам мы по тем самым индексам полей left и right.
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
| ……………
if (a[k].flagl = false) or (a[k].flagr = false) then
{ левый сын текущей вершины существует и еще не просмотрен }
if (a[k].left <> 0) and (a[k].flagl = false) then
begin
a[k].flagl := true; { отмечаем просмотренный узел }
if a[k].right = 0 then { заодно проверяем, отсутствует
ли левый сын, если да, то: }
begin
a[k].flagr := true; { отмечаем просмотренный узел }
inc(j); { узел просмотрен, прибавляем }
end
…………….. |
|
И если у текущей вершины нет левого сына, но есть правый – спускаемся по нему, далее аналогично по алгоритму смотрим на левого.
Вроде бы по коду просто, но объяснять мне, как не писателю, непросто. Оно и понятно.
Итак, допустим, просмотрели мы всех левых сыновей левого поддерева:
Процедура PrintTree вывела следующее:
Получилась такая последовательность: 10, 9, 6, 7.
Левое поддерево полностью просмотрено, по алгоритму теперь нужно начинать с правого. Сделал следующим образом: есть дополнительный массив, который будет запоминать индексы тех вершин, у которых есть правые сыновья, но по понятному стечению обстоятельств мы сначала смотрели все левые, и заглянуть в правые не представлялось возможным:
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
| ……………….
else { иначе }
begin
bufind[i] := k; { запоминаем его индекс, чтоб впоследствии вернуться }
inc(i); { счетчик для массива индексов }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].left; { переходим на левого сына текущего узла }
write(a[k].val:3); { выводим на экран вершину }
end
………………… |
|
| Pascal | 1
2
3
4
5
6
7
8
9
10
11
12
13
| ……………
else { иначе }
{ когда текущая вершина не имеет сыновей) }
begin
dec(i); { в "массиве индексов" переходим на элемент,
который является индексом одной из вершин,
у которой не просмотрен один из сыновей
}
if i >= 0 then { предотвращение выхода за границы диапазона }
k := bufind[i]; { переходим на элемент с одним из не просмотренных сыновей }
inc(j); { узел просмотрен, прибавляем }
end;
…………… |
|
По аналогии просматриваем сначала все левые, а потом правые вершины.
В итоге обхода получен следующий список узлов: 10, 9, 6, 7, 12, 11.
Вообще, все дерево состоит из таких вот частей, которые повторяют его в целом:
Поэтому рекурсия тут в самый раз. Фрактал, фактически.
Переходим к следующей процедуре – процедуре поиска глубины:
| 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
| procedure depth(n: integer; a: artree);
{
Выводит все возможные пути от корня к листам,
а также указывает глубину - самый длинный путь
}
var
i, j, j1, k, kol: integer;
p: boolean; { нужен для сообщения направления из вершины }
{
bufInd содержит адреса (индексы) узлов с
не полностью просмотренными сыновьями
}
bufInd: array [0..1000] of integer;
begin
writeln('Все возможные пути:');
{ узнаем количество путей в дереве}
kol := 0; { обнуляем счетчик }
for i := 1 to n do
if (a[i].left = 0) and (a[i].right = 0) then
inc(kol);
j1 := 0; { нужна для сравнения путей }
i := 0; { массив индексов начинается с 0}
j := 0; { счетчик просмотренных узлов в дереве }
k := 1; { массив узлов начинается с 1 }
while kol <> 0 do { пока не будут пройдены все пути }
begin
{
левый сын текущей вершины существует,
а также через него существует непросмотренный путь
}
if (a[k].left <> 0) and (a[k].flagl = false) then
begin
if a[k].right = 0 then { заодно проверяем, отсутствует ли правый сын }
inc(j) { если да, то добавляем в счетчик }
else { иначе }
begin
bufind[i] := k; { запоминаем его индекс, чтоб впоследствии вернуться }
p := true; { и пойти именно по этому пути }
inc(i); { счетчик для массива индексов }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].left; { переходим на левого сына текущего узла }
end
else { иначе }
{
правый сын текущей вершины существует,
а также через него существует непросмотренный путь
}
if (a[k].right <> 0) and (a[k].flagr = false) then
begin
inc(j); { узел просмотрен, прибавляем }
k := a[k].right; { переходим на правого сына текущего узла }
end
else { когда текущая вершина не имеет сыновей) }
begin
dec(i); { в "массиве индексов" переходим на элемент,
который является индексом одной из вершин,
у которой не просмотрен один из сыновей
}
if i >= 0 then { предотвращение выхода за границы диапазона }
if p = true then {влево уже ходили}
a[bufind[i]].flagl := true { больше не пойдем }
else {вправо уже ходили}
a[bufind[i]].flagr := true; { больше не пойдем }
write(j, ' '); { выводим на экран длину пути }
if j > j1 then { ищем наибольший из путей }
j1 := j;
j := 0; { обнуляем счетчик просмотренных вершин }
k := 1; { переходим к корню дерева }
p := false; { возвращаем флаг в исходное состояние }
dec(kol); { путь просмотрен, вычитаем из общего количества}
end;
end;
writeln;
writeln('Глубина = ', j1); { выводим глубину дерева }
end; |
|
Глубина этого дерева = 6. Это путь от 1 (корень) до 34 (лист).
Процедура поиска глубины очень схожа с процедурой обхода, т.к. в ней также нужно просмотреть по пути все вершины, прежде чем прийти к листу.
Основная идея такова:- Изначально узнаем количество таких вершин с помощью нехитрого цикла:
| Pascal | 1
2
3
4
5
| ………………..
for i := 1 to n do
if (a[i].left = 0) and (a[i].right = 0) then
inc(kol);
……………….. |
|
- Обходим и добавляем в просмотренные вершины аналогично с процедурой прямого обхода, при этом просто записывая в счетчик просмотренные вершины.
- Дошли до листа - выводим на экран путь (совсем не обязательно выводить все возможные пути, но я и это предусмотрел в программе), обнуляем все счетчики, помечаем просмотренные пути и начинаем просмотр с корня.
- После вывода каждого пути дополнительная переменная будет сравниваться со значением текущего пути и, таким образом, мы узнаем наибольший из существующих.
Вот как-то так.
После описания каждой процедуры, думаю, будет целесообразным выложить полностью весь код для взаимодействиями с процедурами:
| 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
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
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
| uses
crt;
{Узел = вершина}
const
N = 500; { количество элементов в дереве }
{ Инициализация дерева }
{ val - текущая вершина, left, right - левый и правый сыновья соответственно }
type
tree = record
val, left, right: integer;
flagL, flagR: boolean; { флаги для метки просмотренных вершин }
end;
{ массив + вершина со ссылками на двух сыновей = дерево }
artree = array [1..N] of tree;
var
i: integer;
a: artree;
q: char;
procedure FormTree(var i: integer; var a: artree);
{
Формирует дерево при помощи массива записей
i - счетчик узлов в дереве;
a - само дерево
}
var
j: integer;
begin
{
Добавление узла в дерево.
Вначале значение узла записывает в ячейку массива,
далее определятся, к какому узлу (вернее к какому сыну (левому или
правому)) оно должно принадлежать
(его индекс записывается в одну из двух (левого или правого)
ячеек элемента, к которому он будет привязан)
}
if a[1].val = 0 then
begin
write('Корень: ');
readln(a[1].val); { ввод корня дерева }
i := 1;
end
else
begin
inc(i); { переходим к следующей ячейке массива для ее заполнения }
j := 1; { индекс добавляющего узла }
write('Узел #', i, ': ');
readln(a[i].val); { ввод последующих узлов }
while true do
begin
{---Добавление узла к вершине "справа"---}
{ сравнение текущего узла с добавляемым }
if a[i].val >= a[j].val then
begin
if a[j].right = 0 then { у этого узла нет сына }
begin
a[j].right := i; { добавляем индекс добавляемого узла }
break; { выходим из цикла для последующего добавления }
end
else { иначе }
if a[j].right <> 0 then
begin
{
узнаем индекс элемента,
стоящего на месте занятой вершины.
Этот элемент станет текущим.
Продолжаем поиск
}
j := a[j].right;
continue;
end;
end;
{---Добавление узла к вершине "слева"---}
{ сравнение текущего узла с добавляемым }
if a[i].val < a[j].val then
begin
if a[j].left = 0 then { у этого узла нет сына }
begin
a[j].left := i; { добавляем индекс добавляемого узла }
break;
end
else { иначе }
if a[j].left <> 0 then
begin
{
узнаем индекс элемента,
стоящего на месте занятой вершины.
Этот элемент станет текущим.
Продолжаем поиск
}
j := a[j].left;
continue;
end;
end;
end;
end;
end;
procedure PrintTree(i: integer);
{ Вывод дерева в табличном виде }
var
k, x, y: integer;
begin
x := 13; { кооординаты курсора по оси x }
y := 1;
if a[1].val = 0 then { проверяем наличие корня }
writeln('Дерево пусто')
else
begin
clrscr; { очищаем экран, чтоб корректно работала gotoxy }
writeln('Вершина: ');
writeln('Левый сын: ');
writeln('Правый сын: ');
for k := 1 to i do
begin
gotoxy(x, y); { переходим к нужной позиции }
{ выводим вершины }
write(a[k].val:3, ' |');
{ выводим их левых сыновей }
gotoxy(x, y + 1); { переходим к нужной позиции }
if a[k].left <> 0 then
write(a[a[k].left].val:3, ' |')
else
write('nil |');
gotoxy(x, y + 2); { переходим к нужной позиции }
{ выводим их правых сыновей }
if a[k].right <> 0 then
write(a[a[k].right].val:3, ' |')
else
write('nil |');
{ когда элемент = 0 - это все равно, что он
отсутствует (поэтому выводится на экран как значение nil)
}
x := x + 5; { добавляем отступ от предыдущих выведеных значений }
if x >= 70 then { если элементам не хватает места на
одной строке - переносим на другую }
begin
gotoxy(x, y + 1);
write(' --->');
gotoxy(1, 5);
writeln('Вершина: ');
writeln('Левый сын: ');
writeln('Правый сын: ');
y := y + 4;
x := 13;
end;
end;
end;
readln;
clrscr; { очищаем экран }
end;
procedure List(n: integer; a: artree);
{
Формирует список узлов при прямом обходе
n - количество узлов в дереве;
a - само дерево
}
var
i, j, k: integer;
{
bufInd содержит адреса (индексы) узлов с
не полностью просмотренными сыновьями
}
bufInd: array [0..1000] of integer;
begin
writeln('Список узлов при прямом обходе: ');
i := 0; { массив индексов начинается с 0, обнуляем }
j := 0; { счетчик просмотренных узлов в дереве }
k := 1; { массив узлов начинается с 1 }
write(a[k].val:3); { выводим на экран первый элемент, он же корень дерева }
while j <> n do { пока не будут просмотрены все вершины }
begin
if (a[k].flagl = false) or (a[k].flagr = false) then
{ левый сын текущей вершины существует и еще не просмотрен }
if (a[k].left <> 0) and (a[k].flagl = false) then
begin
a[k].flagl := true; { отмечаем просмотренный узел }
if a[k].right = 0 then { заодно проверяем, отсутствует
ли левый сын, если да, то: }
begin
a[k].flagr := true; { отмечаем просмотренный узел }
inc(j); { узел просмотрен, прибавляем }
end
else { иначе }
begin
bufind[i] := k; { запоминаем его индекс, чтоб впоследствии вернуться }
inc(i); { счетчик для массива индексов }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].left; { переходим на левого сына текущего узла }
write(a[k].val:3); { выводим на экран вершину }
end
else { иначе }
{ левый сын текущей вершины существует и еще не просмотрен }
if (a[k].right <> 0) and (a[k].flagr = false) then
begin
a[k].flagr := true; { отмечаем просмотренный узел }
if a[k].left = 0 then { заодно проверяем, отсутствует
ли левый сын, если да, то: }
begin
a[k].flagl := true; { отмечаем просмотренный узел }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].right; { переходим на правого сына текущего узла }
write(a[k].val:3); { выводим на экран вершину }
end
else { иначе }
{ когда текущая вершина не имеет сыновей) }
begin
dec(i); { в "массиве индексов" переходим на элемент,
который является индексом одной из вершин,
у которой не просмотрен один из сыновей
}
if i >= 0 then { предотвращение выхода за границы диапазона }
k := bufind[i]; { переходим на элемент с одним из не просмотренных сыновей }
inc(j); { узел просмотрен, прибавляем }
end;
end;
writeln;
end;
procedure depth(n: integer; a: artree);
{
Выводит все возможные пути от корня к листам,
а также указывает глубину - самый длинный путь
}
var
i, j, j1, k, kol: integer;
p: boolean; { нужен для сообщения направления из вершины }
{
bufInd содержит адреса (индексы) узлов с
не полностью просмотренными сыновьями
}
bufInd: array [0..1000] of integer;
begin
writeln('Все возможные пути:');
{ узнаем количество путей в дереве}
kol := 0; { обнуляем счетчик }
for i := 1 to n do
if (a[i].left = 0) and (a[i].right = 0) then
inc(kol);
j1 := 0; { нужна для сравнения путей }
i := 0; { массив индексов начинается с 0}
j := 0; { счетчик просмотренных узлов в дереве }
k := 1; { массив узлов начинается с 1 }
while kol <> 0 do { пока не будут пройдены все пути }
begin
{
левый сын текущей вершины существует,
а также через него существует непросмотренный путь
}
if (a[k].left <> 0) and (a[k].flagl = false) then
begin
if a[k].right = 0 then { заодно проверяем, отсутствует ли правый сын }
inc(j) { если да, то добавляем в счетчик }
else { иначе }
begin
bufind[i] := k; { запоминаем его индекс, чтоб впоследствии вернуться }
p := true; { и пойти именно по этому пути }
inc(i); { счетчик для массива индексов }
inc(j); { узел просмотрен, прибавляем }
end;
k := a[k].left; { переходим на левого сына текущего узла }
end
else { иначе }
{
правый сын текущей вершины существует,
а также через него существует непросмотренный путь
}
if (a[k].right <> 0) and (a[k].flagr = false) then
begin
inc(j); { узел просмотрен, прибавляем }
k := a[k].right; { переходим на правого сына текущего узла }
end
else { когда текущая вершина не имеет сыновей) }
begin
dec(i); { в "массиве индексов" переходим на элемент,
который является индексом одной из вершин,
у которой не просмотрен один из сыновей
}
if i >= 0 then { предотвращение выхода за границы диапазона }
if p = true then {влево уже ходили}
a[bufind[i]].flagl := true { больше не пойдем }
else {вправо уже ходили}
a[bufind[i]].flagr := true; { больше не пойдем }
write(j, ' '); { выводим на экран длину пути }
if j > j1 then { ищем наибольший из путей }
j1 := j;
j := 0; { обнуляем счетчик просмотренных вершин }
k := 1; { переходим к корню дерева }
p := false; { возвращаем флаг в исходное состояние }
dec(kol); { путь просмотрен, вычитаем из общего количества}
end;
end;
writeln;
writeln('Глубина = ', j1); { выводим глубину дерева }
end;
begin
while true do
begin
writeln('-----------------------------------------------------------------------');
writeln('1-Добавить узел; 2-Просмотр дерева; 3-Список узлов; 4-Глубина; 5-Выход;');
writeln('-----------------------------------------------------------------------');
readln(q);
case q of
'1': FormTree(i, a);
'2': PrintTree(i);
'3': List(i, a);
'4': Depth(i, a);
'5': break;
end;
end;
end. |
|
|
полезно спасиба за текс
