ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ.
Под прошивкой дерева понимается замена по определенному правилу пустых указателей на сыновей указателями на последующие узлы, соответствующие обходу.
Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много указателей типа 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.
Дата добавления: 2016-07-22; просмотров: 2390;