Динамические структуры данных. Алексеев А.Ю - 55 стр.

          3.5. Представления и реализации бинарных деревьев

     Рассмотрим варианты представления и реализации структуры данных
бинарного дерева. Пусть базовый тип узлов есть Elem.

   Ссылочная реализация бинарного дерева в связанной памяти основана
на представлении типа BT ( Elem ) рекурсивными типами BinT и Node:

    type
        BinT = ^Node;             { представление бин.дерева }
        Node = record             { узел :                    }
                 Info : Elem;     {        = содержимое       }
                 LSub : BinT;     {       = левое поддерево }
                 RSub : BinT      {        = правое поддерево }
               end { Node }
   Здесь каждый узел дерева рассматривается как корень соответствующего
поддерева, и этому поддереву сопоставляется запись из трех полей: поле Info
хранит значение корня (типа Elem), а поля LSub и RSub − указатели на левое и
правое поддеревья. Пустому дереву сопоставляется константа NilBT (на абст-
рактном уровне обозначаемая ранее как Λ). На рис.3.9, а, б изображены би-
нарное дерево и его представление в ссылочной реализации.
   Интерфейсная часть модуля для работы с бинарным деревом на основе
ссылочной реализации представлена на рис. 3.10.
   Здесь в сравнении с функциональной спецификацией из 3.2 добавлены
функция CreateBT и процедура DestroyBT, используемые для начала и завер-
шения работы с экземпляром динамической структуры. Функция CreateBT
формально специфицируется соотношениями

                CreateBT: → BT;     Null ( CreateBT ) = True.

   Кроме того, добавлена процедура Otkaz, вызываемая при попытке некор-
ректного применения основных функций.
   Тип узлов дерева Elem должен быть задан в модуле GlobalBT, например,
таким образом:

                      Unit GlobalBT;
                      Interface type Elem = Char;
                      Implementation
                      begin
                      end.

                                     55