yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->Листинг 3.7. Функция CREATE2      

Алгоритмы структуры данных

Загрузка...

Листинг 3.7. Функция CREATE2      

function CREATE2   (   v:   labeltype;   Т1,    Т2:   integer  ):   integer;

{  возвращает новое дерево с корнем v и поддеревьями  T1 и  Т2   }

var

temp:   integer;   {  хранит индекс первой свободной ячейки

для корня нового дерева  }

begin

temp:=  avail;

avail:= cellspace[avail].right_sibling;

cellspace[temp].leftmost_child:= T1;

cellspace[temp].label:= v;

cellspace[temp].right_sibling:= 0;

cellspace[Tl].right_sibling:= T2;

cellspace[ T2 ] .right_sibling:= 0,-{необязательный оператор)

return(temp)

end; { CREATE2 }

Можно уменьшить область памяти, занимаемую узлами дерева (но при этом увеличится время выполнения операторов), если в поле right_sibling самого правого сына вместо нулевого указателя поместить указатель на родителя. Но в этом случае, чтобы избежать двусмысленности, необходимо в каждую ячейку поместить еще двоичную (логическую) переменную, которая будет показывать, что содержится в поле right_sibling: указатель на правого брата или указатель на родителя.

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

 

39

yandex rtb 4