Графы

НЕЛИНЕЙНЫЕ СТРУКТУРЫ ДАННЫХ

Графы

Логическая структура, определения

структура, отображающая свойства и связи сложного объекта. Многосвязная структура обладает следующими свойствами: 1) на каждый элемент (узел, вершину) может быть произвольное

Машинное представление оpгpафов

ЭВМ: матричный, т.е. массивами, и связными нелинейными списками. Выбор метода представления зависит от природы данных и операций, выполняемых над ними. Если задача требует большого числа включе-

Логическое представление и изображение деревьев.

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

Представление любого дерева,леса бинарными деревьями.

образом в эквивалентное бинарное дерево. Правило построения бинарного дерева из любого дерева: 1. В каждом узле оставить только ветвь к старшему сыну (верти-

Машинное представление деревьев в памяти ЭВМ.

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

Основные операции над деревьями.

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

которых приведены реализующие их программы.

1) Поиск узла с заданным ключом ( Find ).

2) Добавление нового узла ( Dob ).

3) Удаление узла ( поддерева ) ( Udal ).

4) Обход дерева в определенном порядке:

- Нисходящий обход ( процедура Preorder , рекурсивная процедура

r_Preoder);

- Смешанный обход (процедура Inorder, рекурсивная процедура

r_Inorder);

- Восходящий обход ( процедура Postorder, рекурсивная процедура

r_Postorder).

Приведенные ниже программы процедур и функций могут быть не-

посредственно использованы при решении индивидуальных задач. Кро-

ме выше указанных процедур приведены следующие процедуры и функ-

ции:

- процедура включения в стек при нисходящем обходе (Push_st);

- функция извлечения из стека при нисходящем обходе (Pop_st);

- процедура включения в стек при восходящем и смешанном обходе

(S_Push);

- функция извлечения из стека при восходящем и смешанном обходе

(S_Pop).

Для прошитых деревьев:

- функция нахождения сына данного узла ( Inson );

- функция нахождения отца данного узла ( Inp );

- процедура включения в дерево узла слева от данного (leftIn);

ПОИСК ЗАПИСИ В ДЕРЕВЕ( Find ). Нужная вершина в дереве ищет-

ся по ключу. Поиск в бинарном дереве осуществляется следующим об-

разом.

Пусть построено некоторое дерево и требуется найти звено с

ключом X. Сначала сравниваем с X ключ, находящийся в корне дере-

ва. В случае равенства поиск закончен и нужно возвратить указа-

тель на корень в качестве результата поиска. В противном случае

переходим к рассмотрению вершины, которая находится слева внизу,

если ключ X меньше только что рассмотренного, или справа внизу,

если ключ X больше только что рассмотренного. Сравниваем ключ X с

ключом, содержащимся в этой вершине, и т.д. Процесс завершается в

одном из двух случаев:

1) найдена вершина, содержащая ключ, равный ключу X;

2) в дереве отсутствует вершина, к которой нужно перейти для

выполнения очередного шага поиска.

В первом случае возвращается указатель на найденную вершину.

Во втором - указатель на звено, где остановился поиск, (что удоб-

но для построения дерева ). Реализация функции Find приведена в

программном примере 6.2.

{=== Программный пример 6.2. Поиск звена по ключу === }

Function Find(k:KeyType;d:TreePtr;var rez:TreePtr):bollean;

{ где k - ключ, d - корень дерева, rez - результат }

Var

p,g: TreePtr;

b: boolean;

Begin

b:=false; p:=d; { ключ не найден }

if d <> NIL then

repeat q: =p; if p^.key = k then b:=true { ключ найден }

else begin q:=p; { указатель на отца }

if k < p^.key then p:=p^.left { поиск влево }

else p:=p^.right { поиск вправо}

end; until b or (p=NIL);

Find:=b; rez:=q;

End; { Find }

ДОБАВЛЕНИЕ НОВОГО УЗЛА ( Dop ). Для включения записи в дере-

во прежде всего нужно найти в дереве ту вершину, к которой можно

"подвести" (присоединить) новую вершину, соответствующую включае-

мой записи. При этом упорядоченность ключей должна сохраняться.

Алгоритм поиска нужной вершины, вообще говоря, тот же самый,

что и при поиске вершины с заданным ключом. Эта вершина будет

найдена в тот момент, когда в качестве очередного указателя, оп-

ределяющего ветвь дерева, в которой надо продолжить поиск, ока-

жется указатель NIL ( случай 2 функции Find ). Тогда процедура

вставки записывается так, как в программном примере 6.3.

{=== Программный пример 6.3. Добавление звена ===}

Procedure Dob (k:KeyType; var d:TreePtr; zap:data);

{ k - ключ, d - узел дерева, zap - запись }

Var

r,s: TreePtr;

t: DataPtr;

Begin

if not Find(k,d,r) then

begin (* Занесение в новое звено текста записи *)

new(t); t^:=zap; new(s); s^.key:=k;

s^.ssil:=t; s^.left:=NIL; s^.right:=NIL;

if d = NIL then d:=s (* Вставка нового звена *)

else if k < r^.key

then r^.left:=s

else r^.right:=s;

end; End; { Dop }

ОБХОД ДЕРЕВА. Во многих задачах, связанных с деревьями, тре-

буется осуществить систематический просмотр всех его узлов в оп-

ределенном порядке. Такой просмотр называется прохождением или

обходом дерева.

Бинарное дерево можно обходить тремя основными способами:

нисходящим, смешанным и восходящим ( возможны также обратный нис-

ходящий, обратный смешанный и обратный восходящий обходы). Приня-

тые выше названия методов обхода связаны с временем обработки

корневой вершины: До того как обработаны оба ее поддерева (Preor-

der), после того как обработано левое поддерево, но до того как

обработано правое (Inorder), после того как обработаны оба подде-

рева (Postorder). Используемые в переводе названия методов отра-

жают направление обхода в дереве: от корневой вершины вниз к

листьям - нисходящий обход; от листьев вверх к корню - восходящий

обход, и смешанный обход - от самого левого листа дерева через

корень к самому правому листу.

Схематично алгоритм обхода двоичного дерева в соответствии с

нисходящим способом может выглядеть следующим образом:

1. В качестве очередной вершины взять корень дерева. Пе-

рейти к пункту 2.

2. Произвести обработку очередной вершины в соответствии с

требованиями задачи. Перейти к пункту 3.

3. а) Если очередная вершина имеет обе ветви, то в качестве

новой вершины выбрать ту вершину, на которую ссылается левая

ветвь, а вершину, на которую ссылается правая ветвь, занести в

стек; перейти к пункту 2;

б) если очередная вершина является конечной, то выбрать в

качестве новой очередной вершины вершину из стека, если он не

пуст, и перейти к пункту 2; если же стек пуст, то это означает,

что обход всего дерева окончен, перейти к пункту 4;

в) если очередная вершина имеет только одну ветвь, то в ка-

честве очередной вершины выбрать ту вершину, на которую эта ветвь

указывает, перейти к пункту 2.

4. Конец алгоритма.

Для примера рассмотрим возможные варианты обхода дерева

(рис.6.25).

A При обходе дерева представленно-

/ го на рис.6.25 этими тремя методами мы

B D получим следующие последовательности:

/ / ABCDEFG ( нисходящий );

C E G CBAFEDG ( смешанный );

/ CBFEGDA ( восходящий ).

F

Рис.6.25. Схема дерева

 

НИСХОДЯЩИЙ ОБХОД (Preorder, r_Preorder).В соответствии с ал-

горитмом, приведенным выше, текст процедуры имеет вид:

{=== Программный пример 6.4. Нисходящий обход ===}

Procedure Preorder (t: TreePtr);

Type

Stack=^Zveno;

Zveno = record

next: Stack;

el: pointer;

end;

Var

st: stack;

p: TreePtr;

(*------------ Процедура занесения в стек указателя ------*)

Procedure Push_st (var st:stack; p:pointer);

Var

q: stack;

begin new(q); q^.el:=p; q^.next:=st; st:=g; end;

(*----------- Функция извлечения из стека указателя ------*)

Function Pop_st (var st: stack):pointer;

Var

e,p: stack;

begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end;

Begin

if t = NIL then

begin writeln('Дерево пусто'); exit; end

else begin st:=nil; Push_st(St,t); end;

while st <> nil do { контроль заполнения стека }

begin p:=Pop_st(st);

while p <> nil do

begin { Обработка данных звена }

if p^.right <> nil

then Push_st(st,p^.right);

p:=p^.left;

end; end;

End; { Preorder }

Трассировка нисходящего обхода приведена в табл.6.1:

Таблица 6.1

 

 

─────────────────────────────────────────────────────

@ узла @ узел обработка выходная

в стеке указателя узла строка

─────────────────────────────────────────────────────

p:=pt A A A

D <──── RPA D

│ LPA B B AB

│ RPB=nil

│ LPB C C ABC

│ RPC=nil

│ LPC=nil

└───────> D D D ABCD

G <──── RPD G

│ LPD E E ABCDE

│ RPE=nil

│ LPE F F ABCDEF

│ RPF=nil

│ LPF=nil

└───────> G G G ABCDEFG

RPG=nil

LPG=nil Стек пуст. Конец алгоритма.

─────────────────────────────────────────────────────

РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД. Алгоритм существенно упрощает-

ся при использовании рекурсии. Так, нисходящий обход можно опи-

сать следующим образом:

1). Обработка корневой вершины;

2). Нисходящий обход левого поддерева;

3). Нисходящий обход правого поддерева.

Алгоритм рекурсивного нисходящего обхода реализован в прог-

раммном примере 6.5.

{=== Программный пример 6.5. Рекурсивное выполнение нисходящего

обхода ===}

Procedure r_Preorder (t: TreePtr);

begin

if t = nil then begin writeln('Дерево пусто'); exit; end;

(*------------------- Обработка данных звена --------------*)

................................

if t^.left <> nil then r_Preorder(t^.left);

if t^.right <> nil then r_Preorder(t^.right);

End; { r_Preorder }

CМЕШАННЫЙ ОБХОД (Inorder, r_Inorder). Смешанный обход можно

описать следующим образом:

1) Спуститься по левой ветви с запоминанием вершин в стеке;

2) Если стек пуст то перейти к п.5;

3) Выбрать вершину из стека и обработать данные вершины;

4) Если вершина имеет правого сына, то перейти к нему; перей-

ти к п.1.

5) Конец алгоритма.

В программном примере 6.6. реализован алгоритм смешанного

обхода дерева.

{=== Программный пример 6.6. Процедура смешанного обхода ===}

Procedure Inorder (t: TreePtr);

label 1;

type Stack=^Zveno; { тип стека }

Zveno = record

next: Stack;

El: pointer; end;

Var

st: stack;

p: TreePtr;

(*---------- Процедура занесения в стек указателя ---------*)

Procedure Push_st (var st:stack; p:pointer);

Var

q: stack;

begin new(q); q^.el:=p; q^.next:=st; st:=g; end;

(*------------ Функция извлечения из стека указателя ------*)

Function Pop_st (var st: stack):pointer;

Var

e,p: stack;

begin Pop_st:=st^.el; e:=st; st:=st^.next; dispose(e); end;

Begin

if t = NIL then begin writeln('Дерево пусто'); exit; end

else begin p:=t; st:=nil; end;

1: while p^.left <> nil do

begin (* Спуск по левой ветви и заполнение очереди *)

Push_st(st,p); p:=p^.left; end;

if st = NIL { контроль заполнения стека }

then exit;

p:=Pop_st(st);{выборка очередного элемента на обработку}

(*--------------- Обработка данных звена --------------*)

................................

if p^.right <> nil

then begin p:=p^.right; { переход к правой ветви }

goto 1; end;

End; { Inorder }

Трассировка смешанного обхода приведена в табл. 6.2:

i1

Таблица 6.2

───────────────────────────────────────────────────────────

@ узла @ узел обработка выходная

в стеке указателя узла строка

───────────────────────────────────────────────────────────

A <──── pt:=@A A

│B <──── LPA B

││C <──── LPB C

│││ LPC=nil

││└────────> C C C C

││ RPC=nil

│└─────────> B B B CB

│ RPB=nil

└──────────> A A A CBA

D <──── RPA D

│E <──── LPD E

││F <──── LPE F

│││ LPF=nil

││└────────> F F F CBAF

││ RPF=nil

│└─────────> E E E CBAFE

│ RPE=nil

└──────────> D D D CBAFED

G <──── RPD G

│ LPG=nil

└────────> G G G CBAFEDG

RPG=nil Стек пуст. Конец алгоритма.

──────────────────────────────────────────────────────────

Рекурсивный смешанный обход описывается следующим образом:

1) Смешанный обход левого поддерева;

2) Обработка корневой вершины;

3) Смешанный обход правого поддерева.

Текст программы рекурсивной процедуры ( r_Inorder ) демонс-

трируется в программном примере 6.7.

{=== Программный пример 6.7. Рекурсивное выполнение смешанного

обхода === }

Procedure r_Inorder(t: TreePtr);

begin

if t = nil then

begin writeln('Дерево пусто'); exit; end;

if t^.left <> nil then R_inorder (t^.left);

(*--------------- Обработка данных звена --------------*)

................................

if t^.right <> nil then R_inorder(t^.right);

End;

ВОСХОДЯЩИЙ ОБХОД ( Postorder, r_Postorder ). Трудность зак-

лючается в том, что в отличие от Preorder в этом алгоритме каждая

вершина запоминается в стеке дважды: первый раз - когда обходится

левое поддерево, и второй раз - когда обходится правое поддерево.

Таким образом, в алгоритме необходимо различать два вида стековых

записей: 1-й означает, что в данный момент обходится левое подде-

рево; 2-й - что обходится правое, поэтому в стеке запоминается

указатель на узел и признак (код-1 и код-2 соответственно) . Ал-

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

1) Спуститься по левой ветви с запоминанием вершины в сте-

ке как 1-й вид стековых записей;

2) Если стек пуст, то перейти к п.5;

3) Выбрать вершину из стека, если это первый вид стековых

записей, то возвратить его в стек как 2-й вид стековых запи-

сей; перейти к правому сыну; перейти к п.1, иначе перейти к

п.4;

4) Обработать данные вершины и перейти к п.2;

5) Конец алгоритма.

Текст программы процедуры восходящего обхода ( Postorder)

представлен в программном примере 6.8.

{=== Программный пример 6.8. Восходящий обход ====}

Procedure Postorder (t: TreePtr);

label 2;

Var

p: TreePtr;

top: point; { стековый тип }

Sign: byte; { sign=1 - первый вид стековых записей}

{ sign=2 - второй вид стековых записей}

Begin (*------------- Инициализация ------------------*)

if t = nil then

begin writeln('Дерево пусто'); exit; end

else begin p:=t; top:=nil; end; {инициализация стека}

(*------- Запоминание адресов вдоль левой ветви -------*)

2: while p <> nil do

begin s_Push(top,1,p); { заносится указатель 1-го вида}

p:=p^.left; end;

(*-- Подъем вверх по дереву с обработкой правых ветвей ----*)

while top <> nil do

begin p:=s_Pop(top,sign); if sign = 1 then

begin s_Push(top,0,p); { заносится указатель 2-го вида }

p:=p^.right; goto 2; end

else (*---- Обработка данных звена ---------*)

................................

end; End; { Postorder }

РЕКУРСИВНЫЙ СМЕШАННЫЙ ОБХОД описывается следующим образом:

1). Восходящий обход левого поддерева;

2). Восходящий обход правого поддерева;

3). Обработка корневой вершины.

Текст программы процедуры рекурсивного обхода

(r_Postorder) демонстрируется в програмном примере 6.9.

{ ==== Программный пример 6.9. ===== }

(*--------- Рекурсивное выполнение нисходящего обхода -----*)

Procedure r_Postorder (t: TreePtr);

Begin

if t = nil then begin writeln('Дерево пусто'); exit; end;

if t^.left <> nil then r_Postorder (t^.left);

if t^.right <> nil then r_Postorder (t^.right);

(*-------------- Обработка данных звена --------------*)

................................

End; { r_Postorder }

Если в рассмотренных выше процедурах поменять местами поля

left и right, то получим процедуры обратного нисходящего, обрат-

ного смешанного и обратного восходящего обходов.

ПРОЦЕДУРЫ ОБХОДА ДЕРЕВА, ИСПОЛЬЗУЮЩИЕ СТЕК. Тип стека при

нисходящем обходе.

Stack=^Zveno;

Zveno = record

next: Stack;

El: pointer;

end;

Процедура включения элемента в стек при нисходящем и смешан-

ном обходе ( Push_st ) приведена в программном примере 6.10.

{ === Програмнный пример 6.10 ====}

Procedure Push_st (var st: stack; p: pointer);

Var

q: stack;

begin new(q); q^.el:=p; q^.next:=st; st:=q; end;

Функция извлечения элемента из стека при нисходящем и сме-

шанном обходе ( Pop_st ) приведена в программном примере 6.11.

{ === Програмнный пример 6.11 ====}

Function Pop_st (var st: stack):pointer;

Var

e,p: stack

begin

Pop_st:=st^.el;

e:=st; { запоминаем указатель на текущую вершину }

st:=st^.next;{сдвигаем указатель стека на следующий элемент}

dispose(e); { возврат памяти в кучу }

end;

При восходящем обходе может быть предложен следующий тип

стека:

point=^st;

st = record

next: point;

l: integer;

add: pointer;

end;

Процедура включения элемента в стек при восходящем обходе

( S_Push ) приведена в программном примере 6.12.

{ === Програмнный пример 6.12 ====}

Procedure S_Push (var st: point; Har: integer; add: pointer);

Var q: point;

begin

new(q); { выделяем место для элемента }

q^.l:=Har; { заносим характеристику }

q^.add:=add; { заносим указатель }

q^.next:=st; { модифицируем стек }

st:=q;

end;

Функция извлечения элемента из стека при восходящем обходе

( S_Pop) демонстрируется в программном примере 6.13.

{ === Програмнный пример 6.13 ====}

Function S_Pop (var st: point; var l: integer):pointer;

Var

e,p: point;

begin

l:=st^.l;

S_Pop:=st^.add;

e:=st; { запоминаем указатель на текущую вершину}

st:=st^.next; {сдвигаем указатель стека на след. элемент }

dispose(e); { уничтожаем выбранный элемент }

end;

ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ.Под прошивкой дерева понимается

замена по определенному правилу пустых указателей на сыновей ука-

зателями на последующие узлы, соответствующие обходу.

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

имеются много указателей типа NIL. Действительно в дереве с N

вершинами имеется ( N+1 ) указателей типа NIL. Это незанятое

пространство можно использовать для изменения представления де-

ревьев. Пустые указатели заменяются указателями - "нитями", кото-

рые адресуют вершины дерева, и расположенные выше. При этом дере-

во прошивается с учетом определенного способа обхода. Например,

если в поле left некоторой вершины P стоит NIL, то его можно за-

менить на адрес, указывающий на предшественника P, в соответствии

с тем порядком обхода, для которого прошивается дерево. Аналогич-

но, если поле right пусто, то указывается преемник P в соответс-

твии с порядком обхода.

Поскольку после прошивания дерева поля left и right могут

характеризовать либо структурные связи, либо "нити", возникает

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

туры дерева характеристики левого и правого указателей (FALSE и

TRUE).

Таким образом, прошитые деревья быстрее обходятся и не тре-

буют для этого дополнительной памяти (стек), однако требуют до-

полнительной памяти для хранения флагов нитей, а также усложнены

операции включения и удаления элементов дерева.

Прошитое бинарное дерево на Паскале можно описать следующим

образом:

type TreePtr:=^S_Tree;

S_Tree = record

key: KeyType; { ключ }

left,right: TreePtr; { левый и правый сыновья }

lf,rf: boolean; { характеристики связей }

end;

где lf и rf - указывают, является ли связь указателем на элемент

или нитью. Если lf или rf равно FALSE, то связка является нитью.

До создания дерева головная вершина имеет следующий вид:

┌───┬──────┬───┐ Здесь пунктирная стрелка

┌────┤ L │ HEAD │ R ├ ─ ─ ─┐ определяет связь по нити. Дере-

└───┴──────┴─ ─┘ во подшивается к левой ветви.

Рис. 6.26.

В программном примере 6.14 приведена функция ( Inson ) для

определения сына (преемника) данной вершины.

{ === Програмнный пример 6.14 ====}

(*------ Функция, находящая преемника данной вершины X ----*)

(*-------- в соответствии со смешанным обходом ------------*)

Funtion Inson (x: TreePtr):TreePtr;

begin

Inson:=x^.right;

if not (x^.rf) then exit; { Ветвь левая ?}

while Insonon^.lf do { связь не нить }

Inson:=Inson^.left; { перейти по левой ветви }

end; { Inson }

В программном примере 6.15 приведена функция (Int) для опре-

деления отца (предка) данной вершины.

{ === Програмнный пример 6.15 ====}

(*---------- Функция, выдающая предшественника узла ------*)

(*------- в соответствии со смеш1анным обходом ------------*)

Function Inp (x:TreePtr):TreePtr;

begin

Inp:=x^.left;

if not (x^.lf) then exit;

while Inp^.rf do Inp:=Inp^.right; { связка не нить }

end;

В программном примере 6.16 приведена функция, реализующая

алгоритм включения записи в прошитое дерево ( leftIn ). Этот ал-

горитм вставляет вершину P в качестве левого поддерева заданной

вершины X в случае, если вершина X не имеет левого поддерева. В

противном случае новая вершина вставляется между вершиной X и

вершиной X^.left. При этой операции поддерживается правильная

структура прошивки дерева, соответствующая смешанному обходу.

{ === Програмнный пример 6.16 ====}

(*- Вставка p слева от x или между x и его левой вершиной -*)

Procedure LeftIn (x,p: TreePtr);

Var

q: TreePtr;

begin

(*--------------- Установка указателя ------------------*)

p^.left:=x^.left; p^.lf:=x^.lf; x^.left:=p;

x^.lf:=TRUE; p^.right:=x; p^.rf:=FALSE;

if p^.lf then

(*-------- Переустановка связи с предшественником --------*)

begin q:=TreePtr(Inp(p)); q^.right:=p; q^.rf:=FALSE;

end; end; { LeftIn }

Для примера рассмотрим прошивку дерева приведенного на

рис.6.20. при нисходящем обходе.

Машинное представление дерева при нисходящем обходе с про-

шивкой приведено на рис.6.27.

 

┌─┬───┬─┐

│ │ H │ │<---------------------------─┐

└┼┴───┴─┘ |

┌┴┬───┬─┐ |

┌──────┼ │ A │ ┼─────────────┐ |

│ └─┴───┴─┘ │ |

┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐ |

┌─┼ │ B │ │ ┌----------------->│ │ D │ ┼────┐ |

│ └─┴───┴─┘ | ┌────└─┴───┴─┘ │ |

┌─┬─┴─┬─┐ | ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐ |

┌->│ │ C │ │ | ┌─┼ │ E │ │<┐ ┌-->│ │ G │ │ |

| └|┴───┴|┘ | │ └─┴───┴┬┘ | | ┌>└|┴───┴|┘ |

|___| |________| ┌─┬─┴─┬─┐ |__| | |__| |___|

┌>│ │ F │ │ |

| └|┴───┴|┘ |

|__| |____________|

Рис. 6.27. Машинное связное представление исходного дерева,

представленного на рис.6.20 при нисходящем обходе с прошивкой

Трассировка нисходящего обхода с прошивкой приведена в табл.6.3.

Рассмотрим на примере того же дерева прошивку при смешанном

обходе. Машинное представление дерева при смешанном обходе с про-

шивкой приведено на рис.6.28.

Таблица 6.3

───────────────────────────────────────────────────

@ узел обработка выходная

указателя узла строка

───────────────────────────────────────────────────

PT:=H H

LPH A A A

LPA B B AB

LPB C C ABC

-LPC

-RPC D D ABCD

LPD E E ABCDE

LPE F F ABCDEF

-LPF

-RPF G G ABCDEFG

-LPG

-RPG H Конец алгоритма

───────────────────────────────────────────────────

┌─┬───┬─┐

│ │ H │ │<--------------------------┐

└┼┴───┴─┘ |

┌┴┬───┬─┐ |

┌──────────┼ │ A │ ┼───────────┐ |

│ └─┴───┴─┘ │ |

┌─┬─┴─┬─┐ ^ ┌─┬─┴─┬─┐ |

┌─┼ │ B │ │---------─┘ ┌────┼ │ D │ ┼────┐ |

│ └─┴───┴─┘ │ └─┴───┴─┘ │ |

┌─┬─┴─┬─┐ ^ ┌─┬─┴─┬─┐ ^ ┌─┬─┴─┬─┐ |

┌->│ │ C │ │ | ┌──────┼ │ E │ │----┘ │ │ G │ │ |

| └|┴───┴|┘ | │ └─┴───┴─┘ ┌>└|┴───┴|┘ |

|___| |__| ┌─┬─┴─┬─┐ ^ |__| |___|

┌>│ │ F │ │ |

| └|┴───┴|┘ |

|__| |__________|

Рис. 6.28. Машинное связное представление дерева при

смешанном обходе с прошивкой

Трассировка смешанного обхода с прошивкой приведена в табл.6.4.

Таблица 6.4.

──────────────────────────────────────────────────────

@ узел обработка выходная

указателя узла строка

──────────────────────────────────────────────────────

P:=PT H

LPH A

LPA B

LPB C

-LPC C C C

-RPC B B CB

-RPB A A CBA

RPA D

LPD E

LPE F

-LPF F F CBAF

-RPF E E CBAFE

-RPE D D CBAFED

RPD G

-LPG G G CBAFEDG

-RPG H Конец алгоритма

Приложения деревьев.

Деревья имеют широкое применение при реализации трансляторов

таблиц решений, при работе с арифметическими выражениями, при

создании и ведении таблиц символов, где их используют для отобра-

жения структуры предложений, в системах связи для экономичного

кодирования сообщений и во многих других случаях. Рассмотрим не-

которые из них.

Деревья Хаффмена (деревья минимального кодирования)

битов: А В А С С D А кодом, минимизирующим длину закодированного сообщения. 1) назначим коды:

Деревья при работе с арифметическими выражениями

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

МАНИПУЛИРОВАНИЕ АРИФМЕТИЧЕСКИМИ ВЫРАЖЕНИЯМИ.

Операции выполняются над выражениями, представленными в виде бинарных деревьев. Такие выражения можно символьно складывать, ш1.0

Формирование таблиц символов.

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

Сбалансированные деревья

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