Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Семестр2.doc
Скачиваний:
7
Добавлен:
19.09.2019
Размер:
1.26 Mб
Скачать

Лекция 5

5.1 Деревья

Дерево – структура данных, позволяющая смоделировать иерархические отношения. У каждого элемента этой структуры имеется свой единственный «непосредственный начальник» и некоторое количество «подчиненных». Примерами древовидной структуры могут служить подчиненность служащих в армии, структура бюрократического управления производством, почтовый адрес, организация хранения данных в файловой подсистеме системы Windows, и другие.

Термины: корень, узлы, листы, ветки, поддерево, пень, предок, потомок, братья, уровень, высота.

Определение (рекурсивное):

Dn – n-арное дерево (n>=2), Dno – непустое n-арное дерево.

Dn = (либо пусто, либо Dno);

Dno = (i:инф; n штук Dn)

n=2 - бинарное дерево.

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

D = (либо пусто, либо Dо);

Dо = (i:инф; лев:D; прав:D).

Операции:

  • Создать (Создается пустое дерево)

  • Пусто? (Функция логического типа, истина, если дерево пусто, ложь в противном случае)

  • Корень? (Функция логического типа, истина, если дерево состоит лишь из корня. Такое дерево можно назвать «пнем»)

  • Корень (Процедура выделяет из дерева корень, левое и правое поддеревья как самостоятельные деревья)

  • Левое поддерево (Процедура выделяет из дерева левое поддерево, корень, и правое поддерево как самостоятельные деревья)

  • Правое поддерево (Процедура выделяет из дерева правое поддерево, корень и левое поддерево как самостоятельные деревья)

  • Конструирование (Из «пня» и двух деревьев конструируется дерево. Это операция, обратная к предыдущим трем)

  • Обходы (6 штук! Их названия – ЛКП, ЛПК, ПКЛ, ПЛК, КЛП, КПЛ зависят от порядка обхода)

Пример. Правильное арифметическое выражение (((a+b)*c)/(c+d)).

Представим в виде бинарного дерева

Обходы:

ЛКП – (((a+b)*c)/(c+d)) – исходное выражение.

ЛПК – ab+c*cd+/ – обратная польская запись.

Логическое описание двоичного дерева

pTree=^Tree; Tree=record Корень:Inf; Лев,Прав:pTree end;

Корень

Лев

Прав

Арифметическое выражение как линейный список p погрузить в двоичное дерево

Голова(p) – функция с побочным эффектом

(Голова указывает на голову, p на хвост).

Функция Погрузить(р:pElem):pTree;

если атом?(р) то создается пень q,

иначе

q:=Конструирование(Погрузить(Голова(р)), Погрузить(Голова(р)), Погрузить(Голова(р)));

Погрузить=q

5.3 Реализация операций

Конструирование(р1:pTree; i:Inf; p2:pTree):pTree

Var p:pTree;

begin

NEW(p);

p^.Корень:=i;

p^.Лев:=p1;

p^.Прав:=p2;

Конструирование:=p

end

Теперь можно реализовать функцию Погрузить

ЛКП(р)

если р<>NIL то ЛКП(р^.Лев), TRT(p^.Корень), ЛКП(р^.Прав)

(TRT(i:Inf) - процедура обработки данного типа Inf, например печать)

5.4 Программа

ПАВ (строка символов) => LS => Линейный список

ПАВ (строка символов) => Задача! => Двоичное дерево

Линейный список => Погрузить => Двоичное дерево

Линейный список => Val => Значение выражения (число!)

Двоичное дерево => ЛПК => Обратная польская запись

Обратная польская запись => Стек => Значение выражения (число!)

program from_list_and_tree_to_list;

uses crt;

type

pList=^List;

List=record

next:pList;

case R:0..1 of

0: (level:pList);

1: (atom:char);

end;

pTree=^Tree;

Tree=record

root:char;

left:pTree;

right:pTree;

end;

var p:pList; q:pTree;

procedure Input_to_List(var p:pList);

var c:char;

begin

if not eoln then

begin

read(c);

case c of

'(': begin

new(p); p^.R:=0;

Input_to_List(p^.level);

Input_to_List(p^.next);

end;

'a'..'z','+','-','*','/': begin

new(p); p^.R:=1;

p^.atom:=c;

Input_to_List(p^.next);

end;

')': p:=nil

end

end else p:=nil

end;

procedure Print_of_List(p:pList);

var q:pList;

begin

if p<>nil then

begin

if p^.R=1 then write(p^.atom)

else

begin

write('(');

q:=p^.level;

while q<>nil do

begin

Print_of_List(q);

q:=q^.next

end;

write(')');

end

end

end;

function CutHead(var p:pList):pList;

var q:pList;

begin

q:=p^.level;

p^.level:=q^.next;

q^.next:=nil;

CutHead:=q

end;

function List_to_Tree(p:pList):pTree;

var q:pTree;

begin

new(q);

if p^.R=1 then

begin

q^.root:=p^.atom;

q^.left:=nil;

q^.right:=nil

end else

begin

q^.left:=List_to_Tree(CutHead(p));

q^.root:=CutHead(p)^.atom;

q^.right:=List_to_Tree(CutHead(p));

end;

List_to_Tree:=q

end;

procedure Print_of_Tree(p:pTree);

begin

if p<>nil then

begin

if (p^.left<>nil)and(p^.right<>nil)then write('(');

Print_of_Tree(p^.left);

write(p^.root);

Print_of_Tree(p^.right);

if (p^.left<>nil)and(p^.right<>nil)then write(')');

end;

end;

Procedure AddHead(var p:pList; q:pList);

begin

q^.next:=p^.level;

p^.level:=q

end;

function Tree_to_List(p:pTree):pList;

var ps:pList; pright,pleft,proot:pTree;

begin

new(ps);

ps^.next:=nil;

if (p^.left=nil) and (p^.right=nil) then

begin

ps^.R:=1;

ps^.atom:=p^.root;

dispose(p)

end else

begin

ps^.R:=0;

ps^.level:=nil;

{Расчленение p на pleft, pright, proot}

pright:=p^.right;

pleft:=p^.left;

p^.right:=nil;

p^.left:=nil;

proot:=p;

AddHead(ps,Tree_to_List(pright));

AddHead(ps,Tree_to_List(proot));

AddHead(ps,Tree_to_List(pleft));

end;

Tree_to_List:=ps

end;

begin

ClrScr;

Input_to_List(p);

Print_of_List(p);

writeln;

q:=List_to_Tree(p);

print_of_Tree(q);

writeln;

p:=Tree_to_List(q);

Print_of_List(p);

writeln;

repeat until keypressed

end.