Хранение деревьев в программе

Можно было бы сопоставить вершины полного двоичного дерева с числами (считая, что левый сын n есть 2n , правый сын n есть 2n + 1 ) и хранить пометки в массиве val [1...]. Однако этот способ неэкономен, поскольку тратится место на хранение пустых вакансий в полном двоичном дереве.

Более экономен такой способ. Введем три массива  

       val: array [1..n] of T;
       left, right: array [1..n] of 0..n;

Вместо значения 0 (обозначающего отсутствие вершины) можно было бы воспользоваться любым другим числом вне 1..n. Чтобы подчеркнуть это, будем вместо 0 использовать константу null=0.

12.1.2. Составить программу, определяющую, содержится ли элемент t:T в упорядоченном дереве (хранимом так, как только что описано).

  if root = null then begin
  | ..не принадлежит
  end else begin
  | x := root;
  | {инвариант: остается проверить наличие t в непустом
  |   поддереве с корнем x}
  | while ((t < val [x]) and (left [x] <> null)) or
  | |     ((t > val [x]) and (right [x] <> null)) do begin
  | | if t < val [x] then begin {left [x] <> null}
  | | | x := left [x];
  | | end else begin {t > val [x], right [x] <> null}
  | | | x := right [x];
  | | end;
  | end;
  | {либо t = val [x], либо t отсутствует в дереве}
  | ..ответ = (t = val [x])
  end;`

12.1.3. Упростить решение, используя следующий трюк. Расширим область определения массива val, добавив ячейку с номером null и положим val[null]=t.

  val [null] := t;
  x := root;
  while t <> val [x] do begin
  | if t < val [x] then begin
  | | x := left [x];
  | end else begin
  | | x := right [x];
  | end;
  end;
  ..ответ: (x <> null).`

12.1.4. Составить программу добавления элемента t в множество, представленное упорядоченным деревом (если элемент t уже есть, ничего делать не надо).

  procedure get_free (var i: integer);
  begin
  | {free <> null}
  | i := free;
  | free := left [free];
  end;

  if root = null then begin
  | get_free (root);
  | left [root] := null; right [root] := null;
  | val [root] := t;
  end else begin
  | x := root;
  | {инвариант: осталось добавить t к непустому поддереву с
  |  корнем в x}
  | while ((t < val [x]) and (left [x] <> null)) or
  | |     ((t > val [x]) and (right [x] <> null)) do begin
  | | if t < val [x] then begin
  | | | x := left [x];
  | | end else begin {t > val [x]}
  | | | x := right [x];
  | | end;
  | end;
  | if t <> val [x] then begin {t нет в дереве}
  | | get_free (i);
  | | left [i] := null; right [i] := null;
  | | val [i] := t;
  | | if t < val [x] then begin
  | | | left [x] := i;
  | | end else begin {t > val [x]}
  | | | right [x] := i;
  | | end;
  | end;
  end;`

12.1.5. Составить программу удаления элемента t из множества, представленного упорядоченным деревом (если его там нет, ничего делать не надо).

if root = null then begin
| {дерево пусто, ничего делать не надо}
end else begin
| x := root;
| {осталось удалить t из поддерева с корнем в x; поскольку
|  это может потребовать изменений в отце x, введем
|  переменные  father: 1..n и direction: (l, r);
|  поддерживаем такой инвариант: если x не корень, то father
|  - его отец, а direction равно l или r в зависимости от
|  того, левым или правым сыном является x}
| while ((t < val [x]) and (left [x] <> null)) or
| |     ((t > val [x]) and (right [x] <> null)) do begin
| | if t < val [x] then begin
| | | father := x; direction := l;
| | | x := left [x];
| | end else begin {t > val [x]}
| | | father := x; direction := r;
| | | x := right [x];
| | end;
| end;
| {t = val [x] или t нет в дереве}
| if t = val [x] then begin
| | ..удаление вершины x  с отцом father и
| |   направлением direction
| end;
end;

  procedure make_free (i: integer);
  begin
  | left [i] := free;
  | free := i;
  end;

if (left [x] = null) and (right [x] = null) then begin
| {x - лист, т.е. не имеет сыновей}
| make_free (x);
| if x = root then begin
| | root := null;
| end else if direction = l then begin
| | left [father] := null;
| end else begin {direction = r}
| | right [father] := null;
| end;
end else if (left[x]=null) and (right[x] <> null) then begin
| {x удаляется, а right [x] занимает место x}
| make_free (x);
| if x = root then begin
| | root := right [x];
| end else if direction = l then begin
| | left [father] := right [x];
| end else begin {direction = r}
| | right [father] := right [x];
| end;
end else if (left[x] <> null) and (right[x]=null) then begin
| ..симметрично
end else begin {left [x] <> null, right [x] <> null}
| ..удалить вершину с двумя сыновьями
end;