Лабораторная работа 4.

Бинарные деревья.

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

Исходные теоретические сведения

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

Второй пример - это структура большой организации; использование древообразной структуры для представления ее "иерархической структуры" ныне широко используется во многих компьютерных задачах.

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

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

Самые простые из деревьев считаются бинарные деревья.

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

Эти подмножества называются левым и правым поддеревьями исходного дерева.

Каждый элемент бинарного дерева называется узлом дерева.

На рисунке показан общепринятый способ изображения бинарного дерева. Это дерево состоит из девяти узлов, А - корень дерева. Его левое поддерево имеет корень В, а правое- корень С. Это изображается двумя ветвями, исходящими из А: левым - к В и правым - к С. Отсутствие ветви обозначает пустое поддерево. Например, левое поддерево бинарного дерева с корнем С и правое поддерево бинарного дерева с корнем Е оба пусты. Бинарные деревья с корнями D, G, Н и I имеют пустые левые и правые поддеревья.

На рисунке приведены некоторые структуры, не являющиеся бинарными деревьями.

Если А - корень бинарного дерева и В - корень его левого или правого поддерева, то говорят, что А - отец В, а В - левый или правый сын А.

Узел, не имеющий сыновей (такие как узлы D, G, Н и I), называется листом.

Узел nl -предок узла n2 (а п2-потомок nl), если nl-либо отец n2, либо отец некоторого предка n2. Например, в дереве из рисунке А-предок G и Н-потомок С, но Е не является ни предком, ни потомком С.

Узел n2-левый потомок узла n1, если n2 является либо левым сыном n1, либо потомком левого сына n1. Похожим образом может быть определен правый потомок.

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

Свойство 1. Строго бинарное дерево с n листами всегда содержит 2n-1 узлов.

Уровень узла в бинарном дереве может быть определен следующим образом. Корень дерева имеет уровень 0, и уровень любого другого узла дерева имеет уровень на 1 больше уровня своего отца.

Например, в бинарном дереве на первом рисунке узел Е- узел уровня 2, а узел Н- уровня 3.

Глубина бинарного дерева - это максимальный уровень листа дерева, что равно длине самого длинного пути от корня к листу дерева.

Стало быть, глубина дерева на первом рисунке равна 3.

Полное бинарное дерево уровня n - это дерево, в котором каждый узел уровня n является листом и каждый узел уровня меньше n имеет непустые левое и правое поддеревья. На рисунке приведен пример полного бинарного дерева уровня 3.

Почти полное бинарное дерево - это бинарное дерево, для которого существует неотрицательное

целое k такое, что

1. Каждый лист в дереве имеет уровень k или

k+1.

2. Если узел дерева имеет правого потомка

уровня к+1, тогда все его левые потомки, являющиеся _r -\:j

листами, также имеют уровень к+1.

Строго бинарное дерево из рис. а не является почти полным, поскольку оно содержит листы уровней 1, 2 и 3, нарушая тем самым условие 1.

Строго бинарное дерево на рис. 6 удовлетворяет условию 1, так как каждый лист имеет уровень 2 или 3. Однако при этом нарушается условие 2, поскольку А имеет не только правого потомка уровня 3 (J), но также и левого потомка, являющегося листом уровня 2 (Е).

Строго бинарное дерево на рис. в удовлетворяет обоим условиям и, следовательно, является почти полным бинарным деревом.

Бинарное дерево на рис. Г - также почти полное бинарное дерево, но оно не является строго бинарным, поскольку узел Е имеет лишь левого сына.

Узлы почти полного бинарного дерева могут быть занумерованы так, что корню назначается номер 1, левому сыну - удвоенный номер его отца, а правому - удвоенный номер отца плюс единица (намного проще это понять, если представить эти числа в двоичной системе).

Есть еще одна разновидность бинарных деревьев, которая называется упорядоченные бинарные деревья.

Упорядоченные бинарные деревья - это деревья, в которых для каждого узла Х выполняется правило: в левом поддереве - ключи, меньшие Х, в правом поддереве - большие или равные Х.

Структура бинарного дерева построена из узлов. Узел дерева содержит поле данных и два поля с указателями.

сщда будет включена запись "1£"

Поля указателей называются левым указателем и правым указателем, поскольку они указывают на левое и правое поддерево, соответственно. Значение nil является признаком пустого дерева.

Тогда бинарное дерево можно будет представить в следующем виде.

TretNodE

right

X

Iftft

т

дэныи

Jafc

left

rigflt

left

данные

left

right

left	□	light felt	Е	right left	F	nL^
		-4-

nglrt

right

left

Z

right

s

Itft

Над бинарным деревом есть операция - его прохождение, т.е. нужно обойти все дерево, отметив каждый узел один раз.

Существует 3 способа обхода бинарного дерева.

1. в прямом порядке

2. в симметричном порядке

3. в обратном порядке

В прямом порядке:

1. Попасть в корень

2. Пройти в прямом порядке левое поддерево

3. Пройти в прямом порядке правое поддерево В симметричном порядке:

1. Пройти в симметричном порядке левое поддерево

2. Попасть в корень

3. Пройти в симметричном порядке правое поддерево В обратном порядке:

1. Пройти в обратном порядке левое поддерево

2. Пройти в обратном порядке правое поддерево

3. Попасть в корень

Прямо й по ряд ок: ABD G-CEHIF С имм етр ичный п оря д о к : D GB АНЕ IС F О братный поряд ок: CDBHIЕ FСА

Варианты заданий.

Вариант	Задание
1	Напишите программы вычисления высоты дерева с использованием пред­ставлений деревьев.
2	Написать программу, выводящую списки узлов дерева, при обходе этого дерева в прямом порядке.
3	Напишите программы обхода двоичных деревьев в прямом порядке.
4	При прохождении дерева в порядке уровней, в список узлов сначала заносится корень дерева, затем все узлы глубины 1, далее все узлы глубины 2 и т.д. Узлы одной глубины заносятся в список узлов в порядке слева направо. Напишите программу обхода деревьев в порядке уровней.
5	Напишите программу поиска положительных элементов в бинарном дереве.
6	Напишите программу поиска элементов, кратных 2, в бинарном дереве.
7	Напишите программы обхода двоичных деревьев в обратном порядке.
8	Напишите программы обхода двоичных деревьев в внутреннем порядке.
9	Написать программу, выводящую списки узлов дерева, при обходе этого дерева в обратном порядке.
10	Написать программу, выводящую списки узлов дерева, при обходе этого дерева в внутреннем порядке.

Пример выполнения.

Задание: разработать программу, реализующую прямое прохождение (известное также как прохождение в глубину) бинарного дерева.

Блок-схема алгоритма

^ Начало ^

печать

/ рез-та

~)

t

Конец

Текст программы:

uses

crt;

const

nvertex=100;

nadj=1000;

var

f:text;

n,nt:integer;

adj:array [1..nadj] of integer; fst:array [1..nvertex] of integer; nbr:array [1..nvertex] of integer; vtx:array [1..nvertex] of integer; mark:array [1..nvertex] of integer; t:array [1..nvertex] of integer; b:array [1..nvertex] of integer;

procedure init(var y:boolean); var i,j,m:integer; begin

for i:=1 to n do for j:=1 to nbr[i] do begin y:=false;

for m:=1 to n do if adj[fst[i]+j]=vtx[m] then

begin

y:=true;

adj[fst[i]+j]:=m;

break;

end;

if not y then exit; end;

end;

procedure deep(x,u:integer;var c:integer); var i,v:integer; begin c:=c+1; mark[x]:=c; for i:=1 to nbr[x] do begin

v:=adj[fst[x]+i]; if mark[v]=0 then begin nt:=nt+2; t[nt-1]:=x; t[nt]:=v; b[nt div 2]:=1; deep(v,x,c); end

else if (mark[v]<mark[x]) and (v<>u) then begin nt:=nt+2; t[nt-1]:=x; t[nt]:=v; b[nt div 2]:=0; end;

end;

end;

procedure way; var v,c:integer; begin nt:=0; c:=0;

for v:=1 to n do mark[v]:=0; for v:=1 to n do if mark[v]=0 then deep(v,0,c); end;

procedure main; var i,j:integer; y:boolean;

begin

writeln('Reading...');

assign(f,'in.txt');

reset(f);

read(f,n);

fst[1]:=0;

for i:=1 to n do

begin

read(f,vtx[i]);

read(f,nbr[i]);

for j:=1 to nbr[i] do read(f,adj[fst[i]+j]); fst[i+1]: =fst[i]+nbr[i]; end; close(f);

writeln('Solve...');

assign(f,'out.txt');

rewrite(f);

init(y);

if not y then

begin

writeln(f,'BAD SEED! Hi from hell'); writeln('BAD SEED! Hi from hell'); close(f);

exit;

end;

way;

for i:=1 to nt div 2 do write(f,vtx[t[2*i-1]]:3); writeln(f);

for i:=1 to nt div 2 do write(f,vtx[t[2*i]]:3); writeln(f);

for i:=1 to nt div 2 do write(f,b[i]:3); writeln(f); close(f); writeln('End.'); writeln('Press any key.'); end; begin clrscr; main; readkey; end.

Результаты расчетов Структура входного файла IN.TXT:

19

1. 3 2 3 4

2. 3 1 5 6

3. 2 1 7

4. 4 1 8 9 10

5. 2 2 11

6 1	2
7 3	3 12 13
8 1	4
9 3	4 14 15
10 1	4
11 3	5 16 17
12 1	7
13 1	7
14 1	9
15 3	9 18 19
16 1	11
17 1	11
18 1	15
19 1	15

Структура выходного файла OUT.TXT:

1. 2 5 1111 2 1 3 7 7 1 4 4 9 9 15 15 4

2. 5 11 16 17 6 3 7 12 13 4 8 9 14 15 18 19 10 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

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