Прошивка бинарных деревьев.

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

Рассматривая бинарное дерево, легко обнаружить, что в нем имеются много указателей типа 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 – Головная вершина

В программном примере ниже приведена функция (Inson) для определения сына (преемника) данной вершины.

(*------ Функция, находящая преемника данной вершины 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 }

В программном примере приведена функция (Int) для определения отца (предка) данной вершины.

(*---------- Функция, выдающая предшественника узла ------*) (*------- в соответствии со смеш1анным обходом ------------*) Function Inp (x:TreePtr):TreePtr; begin Inp:=x^.left; if not (x^.lf) then exit; while Inp^.rf do Inp:=Inp^.right; { связка не нить } end;

В программном примере ниже приведена функция, реализующая алгоритм включения записи в прошитое дерево (leftIn). Этот алгоритм вставляет вершину P в качестве левого поддерева заданной вершины X в случае, если вершина X не имеет левого поддерева. В противном случае новая вершина вставляется между вершиной X и вершиной X^.left. При этой операции поддерживается правильная структура прошивки дерева, соответствующая смешанному обходу.

(*- Вставка 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. при нисходящем обходе.

Рисунок 8 – Машинное представление дерева при нисходящем обходе с прошивкой

 

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

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

Таблица 3 - Трассировка нисходящего обхода с прошивкой

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

 

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

Таблица 4 - Трассировка смешанного обхода с прошивкой

 

- прямой обход. Сначала посещается корень n, затем в прямом порядке узлы поддерева T 1, далее все узлы поддерева T 2 и т.д. Последними посещаются в прямом порядке узлы поддерева T m;

- обратный обход. Сначала посещаются в обратном порядке все узлы поддерева T 1, затем в обратном порядке узлы поддеревьев T 2 … T m, последним посещается корень n;

- симметричный обход. Сначала в симметричном порядке посещаются все узлы поддерева T 1, затем корень n, после чего в симметричном порядке все узлы поддеревьев T 2 … T m.

Рассмотрим пример всех способов обхода дерева, изображенного на рисунке 10

 

Рисунок 10 – Способы обхода дерева

 

Порядок узлов данного дерева в случае прямого обхода будет следующим: 1 2 3 5 8 9 6 10 4 7.

Обратный обход этого же дерева даст нам следующий порядок узлов: 2 8 9 5 10 6 3 7 4 1.

При симметричном обходе получим последовательность узлов: 2 1 8 5 9 3 10 6 7 4.