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

            Write (#10);           { вниз }
            Write (' ');         { вправо }
            DisplayBT ( LeftBT ( b ) );
            Write (#8); Write (#8); { возврат влево }
           end;
    end {else}
end { DisplayBT };
begin
   Assign ( Fin , 'inbintree.dat'); Reset ( Fin );
   b := EnterBT;
   WriteLn ( 'Построили бинарное дерево по его КЛП-представлению,',
         'вот КЛП-представление :');
   OutBT ( b );        WriteLn;
   WriteLn ('... а теперь − вид дерева ...');
   DisplayBT ( b );
   WriteLn;
   DestroyBt ( b );
end.

    Определение структуры данных бинарного дерева через описанный в
3.2 набор базовых операций естественно с математической точки зрения и
удобно при функциональном (рекурсивном) стиле программирования (в осо-
бенности в языках функционального программирования, например, в Лиспе).
Однако при итеративном стиле программирования в случае необходимости
модификации дерева возникают некоторые неудобства, связанные с употреб-
лением функции ConsBT. Дело в том, что если мы перестраиваем бинарное
дерево, работая только через базовые функции, т.е. не используя особенности
ссылочного представления и работу с указателями, то нам приходится сначала
“разбирать”текущее поддерево с помощью селекторов, а затем “собирать” за-
ново с помощью конструктора ConsBT. При этом приходится производить со-
ответствующие операции с динамической памятью для замены старого узла
на новый. Это приводит к дополнительным накладным расходам при выпол-
нении программы. Во многих случаях этих накладных расходов можно избе-
жать, вводя более удобный набор конструкторов. Например, полезно выде-
лить как самостоятельные следующие дополнительные функции:
    1) функцию MakeRoot, порождающую бинарное дерево из одного узла
(корня);
    2) функцию SetLeft, модифицирующую заданное бинарное дерево таким обра-
зом, что на месте его пустого левого поддерева появляется заданный лист;
    3) функцию SetRight, аналогичную SetLeft, но для правого поддерева.
    Функциональная спецификация этих функций имеет вид:
             MakeRoot : α → NonNullBT;
             SetLeft : α ⊗ NonNullBT → NonNullBT;
             SetRight: α ⊗ NonNullBT → NonNullBT

                                    60