находящая преемника данной вершины

Рисунок 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.