Информатика_Гуда

Глава 6. Алгоритмизация и программирование

Begin {основная программа}

Readln(k);

{создадим первый (он же последний) элемент очереди} New(p); readln(n); p^.m:=n; p^.next:=nil;

no:=p; ko:= p; For i:=2 to k do

Begin

Readln(n); Putoch(n);

End;

While ko <> nil do Begin

Getoch(n);

Writeln(n)

End;

End.

6.14.4. Деревья

KДеревья — динамические данные иерархической структуры произвольной конфигурации, состоящие из графов. Граф — это структура, состоящая из узлов (или вершин) и соединяющих их дуг. Графы бывают двух видов: ориентированные и неориентированные (если дуги не имеют стрелок).

Специального вида граф, в котором в каждую вершину может входить только 1 стрелка, а выходить несколько, называется деревом (рис. 6.6).

1

2

3

4

à)	á)

Рис. 6.6. а) изображение дерева; б) структура, не являющаяся деревом

301

Информатика

Начальная вершина (в которую не входит стрелка) называется корнем. Вершины, из которых не выходят стрелки, — терминальные (листья) (помечены кружками). Структура, выходящая из одного узла —

поддерево.

KДерево, у которого из каждой вершины выходит не более 2-х стрелок, называется бинарным или двоичным деревом.

Уровень — количество стрелок, которые нужно пройти, чтобы добраться от нулевого уровня к данной вершине (см. рис. 6.6).

Âдереве может быть только один путь от корня к узлу; дерево не содержит петель и циклов, что следует из определения.

Âвиде деревьев можно изобразить отношения между субъектами из различных предметных областей.

Примеры деревьев:

Факультет: 5 курсов, на каждом курсе — определенное число групп; в каждой группе — n человек.

Программа на ПК. Ее блоки составляют дерево, дуги которого означают вложенность структур.

Арифметическое выражение можно представить в виде деревьев, в узлах которых находятся операции, за исключением терминальных вершин. В них находятся переменные или числа (рис. 6.7).

/

*

+

-

+

Терминальные вершины — цифры или переменные, остальные узлы – знаки операции

(À+Â) * (À-Â) * (À+Â)

Рис. 6.7

Для хранения и поиска информации наиболее часто применяют дво- ичные деревья.

302

Глава 6. Алгоритмизация и программирование

Организация деревьев в динамической памяти

Определить (построить) дерево — значит определить узлы и связи между ними. Применительно к динамической памяти — это элементы комбинированного типа, в которых динамическая переменная может иметь одно и более информационных полей для хранения данных и столько указательных полей, сколько стрелок (максимально) может выходить из вершины.

Для двоичного дерева достаточно двух указательных полей — на левую и правую «ветви»:

Type ptree=^ttree; ttree = record

… {инфомационные поля}

l,r:ptree {указатели на левую и правую ветвь}

End;

Построение полного двоичного дерева

K Дерево называется полным, если все вершины, уровень которых меньше некоторого заданного n, не являются терминальными, а все вершины, кроме терминальных, имеют одинаковое количество выходящих стрелок (рис. 6.8).

Построение полного двоичного дерева состоит из нескольких этапов. Проходя к какой-либо вершине, мы должны запоминать указатель пути. Для этой цели удобно использовать стек. Остановка алгоритма — создание самого правого пути.

à)		б) неполное бинарное
а) полноебинарноедерево
èç 4-õ	уровней	дерево из 4-х уровней
èç 4-õ

Рис. 6.8

303

Информатика

Построение полного двоичного дерева состоит из нескольких этапов. Проходя к какой-либо вершине, мы должны запоминать указатель пути. Для этой цели удобно использовать стек. Остановка алгоритма — создание самого правого пути.

Пример. Написать программу построения полного двоичного дерева в динамической памяти из 4-х уровней (рис. 6.9).

				0
		1				8
	2		5		9	12
3	4	6	7	10	11	13	14

Рис. 6.9

{Построение полного двоичного дерева} Const n=4; {сколько уровней}

Type ptree=^ttree;

Ttree=record {опишем запись для создания дерева} dat:integer;

l,r:ptree

End;

Var kor,v,t:ptree; i,j:Integer;

{kor —корень, v,t — вспомогательные, i — значение информационного поля очередной вершины, j — ¹ уровня}

Type pstack=^element;

{Опишем запись для стека. Информационные поля имеют тип ptree — дерева}

element = record m:ptree; next:pstack End;

304

Глава 6. Алгоритмизация и программирование

Var p,h:pstack;

Procedure putstack (n:ptree); Begin

New(p); p^.m:=n; p^.next:=h; h:=p End;

Procedure getstack(var n:ptree); Begin

p:=h; n:=p^.m; h:=p^. next; dispose (p) End;

Begin

h:=nil; {стек в начале пуст} j:=0; i:=0; new(kor); {0 — уровень}

t:=kor; t^.dat:=i; t^.r:=nil; t^.l:=nil; inc(i); Repeat

While j<n do {спуск} Begin

New(v); v^.dat:=i; v^.l:=nil; v^.l:=nil; v^.r:=nil;

Inc(i);

{создаем новый узел — вершину}

If t^.l=nil then t^.l:=v else t^.r:=v;

{связывает его с левой или правой ветвью узла

предыдущего уровня}

Putstack(t); {запомним: пока в стеке!} t:=v; {write (t^.dat);} inc(j);

{переместим указатель t и переход на следующий уровень}

End;

Repeat {подъем}

Getstack(t); dec(j) {взять из стека} Until (j=0) or (t^.r=nil);

{либо дошли до корня, либо не заполнена правая ветвь}

Until (t=kor) and (t^.r<>nil);

{дошли до корня, и правая ветвь не пуста}

End.

305

Информатика

Алгоритмы работы с двоичными упорядоченными деревьями (деревьями поиска)

K Двоичное дерево упорядочено (является деревом поиска), если в н¸м все ключи левого поддерева каждого узла меньше, чем ключ узла, а ключи правого поддерева — больше.

KКлюч — признак, по которому вед¸тся поиск — значение одного из информационных полей дерева.

Пример. Необходимо создать базу данных «Рейтинг» для хранения сведений о студентах и их успеваемости. При этом программа должна обеспечивать: 1) добавление новых записей, 2) вывод отсортированной по какому-либо признаку информации (например, по алфавиту, по среднему баллу успеваемости), 3) быстрый поиск нужной записи (например, по фамилиям студентов, по номеру группы), 4) удаление записи.

Type preit = ^ treit; Treit = record

fam: string [20]; {фамилия}; Ngr: integer; {¹ группы}; srb: real {ср. балл}

…

l, r: preit; End;

Длявыполненияуказанныхзадачудобнохранитьинформациюввиде упорядоченного двоичного дерева. При этом выбор ключа зависит от поставленной задачи. Если необходимо хранить и выводить информацию по алфавиту, а также вставлять элементы, не нарушая алфавитного порядка, то ключом будет поле fam типа string. Если информация дерева была отсортирована по среднему баллу — соответственно клю- чом будет поле srb типа real и т. д.

Почему в виде двоичного дерева удобнее хранить подобную информацию, чем в виде, например, связанных списков? Рассмотрим п р и м е р. Пусть необходимо построить связанный список, в котором фамилии распределены по алфавиту, при этом на вход данные поступают случайным образом. В этом случае иногда запись будет вставлена в начало списка, иногда — в конец, иногда — в середину. В среднем, до определения положения вставки новой записи прид¸тся просматривать половину списка. Процесс поиска можно было бы ускорить, если бы вместо такого последовательного просмотра можно было сравнить новую за-

306

Глава 6. Алгоритмизация и программирование

пись с записью из середины списка. Врезультате такого сравнения можно решить: помещать новую запись после средней или до не¸. И далее половину списка игнорировать. Этот процесс повторять до тех пор, пока не найд¸мискомуюзапись(припоиске)илиподходящееместо(привставке).

Например, если в списке 64 записи, то такой метод потребует максимум 7 сравнений, а обычный поиск, в среднем, 32 сравнения. В идеальном случае описанную структуру можно представить в виде двоичного дерева.

Таким образом, в упорядоченных массивах можно быстро найти нужную информацию. Динамические списки можно быстро пополнять новыми элементами, используя память из кучи. Двоичные упорядоченные деревья соединяют оба этих качества и позволяют быстро осуществлять двоичный поиск информации.

Пусть записи поступали в следующем порядке: L, E, R, A, W, H, P, а необходимо запомнить их в алфавитном порядке. Для простоты положим, что каждая запись содержит поле-букву, которое и является клю- чом. Тогда: отсортированный список и упорядоченное двоичное дерево будут выглядеть соответственно рис. 6.10 и рис. 6.11.

`A`

`E`

`H`

`L`

`P`

`R`

`W`

Рис. 6.10

`L`

`E`

`R`

`A`

`H`

`P`

`W`

Рис. 6.11

Алгоритм построения двоичного дерева, а также включение новых элементов (процедура bild) будет выглядеть следующим образом:

1. Первая поступившая запись выбирается «корнем» дерева.

307

Информатика

2.При поступлении каждая следующая запись сравнивается с корневой.

2.1.Если поступившая запись предшествует корневой, идти в левое поддерево.

2.2.Иначе — в правое поддерево.

3.Если того поддерева, в которое можно вставить новую запись не существует (на что указывает значение nil левой или правой связи), то новую запись надо вставить в этом месте (тем самым формируя новое поддерево, состоящее из единственной записи).

При этом для вставки новой записи нет необходимости изменять связи, указывающие на другие записи как для связывания списка.

Алгоритм просмотра входящих в упорядоченное дерево записей и изображения записей, отсортированных по выбранному ключу (prozm (kor)):

1.Изобразить записи левого поддерева и т. д., пока не будет встре- чено пустое поддерево — тогда никаких действий не предпринимать.

2.Изобразить корневую запись.

3.Напечатать записи правого поддерева, пока не будет встречено пустое поддерево.

Алгоритм двоичного поиска в упорядоченном дереве:

1.Если дерево не пусто, сравнить искомый ключ с тем, что в корне дерева.

2.Если ключи совпадают, поиск заверш¸н.

3.Если ключ в корне больше искомого, выполнить поиск в левом поддереве.

4.Если ключ в корне меньше искомого, выполнить поиск в правом поддереве.

5.Если дерево пусто (пройдены все элементы), поиск неудачен.

Рекурсивные алгоритмы работы с двоичными деревьями

Дадим рекурсивное определение дерева. Представим, что отдельные дуги дерева ведут к частям дерева, которые сами являются деревьями. Такая точка зрения приводит к рекурсивному определению дерева. Дерево — это пустая структура или узел, связанный дугами с конечным числом деревьев. Прохождение дерева заключается в обходе всех его

узлов. Рекурсивный алгоритм прохождения двоичного дерева будет таким:

1.Посетить корень.

2.Посетить левое поддерево.

3.Посетить правое поддерево.

308

Глава 6. Алгоритмизация и программирование

Обходя дерево по этому алгоритму, мы посетим узлы в следующем порядке (по алфавиту) (рис. 6.12):

A

B E

|C D F G

Рис. 6.12

Проходя дерево по данному алгоритму, мы посетим вершины дерева в следующем порядке: A, B, C, D, E, F, G. Как изменить порядок пунктов алгоритма, чтобы пройти узлы в последовательности:

à) A, E, G, F, B, D, C á) C, D, B, F, G, E, A â) C, B, D, A, F, E, G?

Примеры использования рекурсивных алгоритмов для работы с дво- ичными деревьями.

Const k = 13;

Const a:array[1..k] of integer= (2,4,6,1,3,5,7,10,12,14,11,13,15);

Type ptree=^ttree; ttree = record dat:integer;

l,r:ptree

End;

Var kor,t:ptree; i,x:integer;

fl:boolean; {v — новый элемент}

Procedure bild (v: ptree; var kor:ptree);

{построение}

Begin

If kor = nil

Then begin kor := v; v^.l:=nil; v^.r:=nil end Else if v^.dat < kor^.dat

Then bild(v,kor^.l)

309

Информатика

{заполнение левой ветви}

Else bild(v,kor^.r)

{заполнение правой ветви}

End;

Procedure prosm(t:ptree);

{просмотр в порядке возрастания}

Begin

If t^.l <> nil then prosm(t^.l); Writeln(t^.dat);

If t^.r<> nil then prosm(t^.r); End;

Procedure poisk(t:ptree);

{линейный поиск в неупорядоченном дереве}

Begin

Writeln(' ',t^.dat); If t^.dat=x

Then writeln ('Нужный элемент найден !',t^.dat) Else

Begin

If t^.l <> nil then poisk (t^.l); If t^.r <> nil then poisk (t^.r);

End;

End;

Procedure dv_poisk(t:ptree);

{двоичный поиск в упорядоченном дереве}

Begin

Write(' ',t^.dat); If t^.dat = x

Then Begin

fl := true; writeln;

Writeln ('Нужный элемент найден!',t^.dat) End

Else

If (x<t^.dat) and (t^.l<>nil) then dv_poisk(t^.l) Else if t^.r<>nil then dv_poisk(t^.r)

End;

310