Модели и структуры данных
       

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


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

  • 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 }

ОБХОД ДЕРЕВА.

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

Бинарное дерево можно обходить тремя основными способами: нисходящим, смешанным и восходящим ( возможны также обратный нисходящий, обратный смешанный и обратный восходящий обходы).


Принятые выше названия методов обхода связаны с временем обработки корневой вершины: До того как обработаны оба ее поддерева (Preorder), после того как обработано левое поддерево, но до того как обработано правое (Inorder), после того как обработаны оба поддерева (Postorder). Используемые в переводе названия методов отражают направление обхода в дереве: от корневой вершины вниз к листьям - нисходящий обход; от листьев вверх к корню - восходящий обход, и смешанный обход - от самого левого листа дерева через корень к самому правому листу.

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


  • 1. В качестве очередной вершины взять корень дерева. Перейти к пункту 2.
  • 2. Произвести обработку очередной вершины в соответствии с требованиями задачи. Перейти к пункту 3.
  • 3.а) Если очередная вершина имеет обе ветви, то в качестве новой вершины выбрать ту вершину, на которую ссылается левая ветвь, а вершину, на которую ссылается правая ветвь, занести в стек; перейти к пункту 2;
  • 3.б) если очередная вершина является конечной, то выбрать в качестве новой очередной вершины вершину из стека, если он не пуст, и перейти к пункту 2; если же стек пуст, то это означает, что обход всего дерева окончен, перейти к пункту 4;
  • 3.в) если очередная вершина имеет только одну ветвь, то в качестве очередной вершины выбрать ту вершину, на которую эта ветвь указывает, перейти к пункту 2.
  • 4. Конец алгоритма.


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

При обходе дерева представленного на рис.6.26 этими тремя методами мыполучим следующие последовательности: ABCDEFG ( нисходящий ); CBAFEDG ( смешанный ); CBFEGDA ( восходящий ).



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

НИСХОДЯЩИЙ ОБХОД (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

РЕКУРСИВНЫЙ НИСХОДЯЩИЙ ОБХОД.

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


  • 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:



Таблица 6.2

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


  • 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, то связка является нитью.

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



Рис. 6.27.

В программном примере 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.28.
Рис. 6.28. Машинное связное представление исходного дерева, представленного на рис.6.20 при нисходящем обходе с прошивкой

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

Рассмотрим на примере того же дерева прошивку при смешанном обходе. Машинное представление дерева при смешанном обходе с прошивкой приведено на рис.6.28.

@ указателя Узел Обработка узла Выходная строка
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 Конец алгоритма
Таблица 6.3



Рис. 6.29. Машинное связное представление дерева при смешанном обходе с прошивкой

Трассировка смешанного обхода с прошивкой приведена в табл.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 Конец алгоритма
Таблица 6.4.




Содержание раздела