Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

ПРОШИВКА БИНАРНЫХ ДЕРЕВЬЕВ.




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

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





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:



©2015- 2022 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.