Логическое описание двоичного дерева

Логическое описание представляет двоичное дерево как последовательность элементов типа T, возможно, пустую. С помощью формул Бэкуса его можно определить следующим образом:

тип ДвоичноеДерево = (Пусто | НепустоеДвоичноеДерево)

тип НепустоеДвоичноеДерево = (корень: T; ЛевоеПоддерево, ПравоеПоддерево: ДвоичноеДерево)

Операции функционального описания для любого двоичного дерева имеют следующие свойства:

ДеревоПусто(Создание()) = истина - создается пустое дерево;

ДеревоПусто(Включение(t, Создание())) = ложь - если в пустое дерево включается элемент, результирующее дерево не пусто;

ДеревоПусто(Построение(t, Tree, Tree')) = ложь - дерево, построенное из узла t и двух поддеревьев не пусто;

Корень(Включение(t, Создание())) = t - корень дерева с единственным элементом – этот элемент;

ЛевоеПоддерево(Построение(t, Tree, Tree')) = Tree - левое поддерево вновь созданного дерева;

ПравоеПоддерево(Построение(t, Tree, Tree')) = Tree' - правое поддерево вновь созданного дерева;

Построение(Корень(Tree), ЛевоеПоддерево(Tree), ПравоеПоддерево(Tree)) = Tree - формирование дерева из корня, левого и правого поддеревьев.

. Двоичное дерево, каждый внутренний узел которого имеет двух сыновей, называют расширенным двоичным деревом. Расширенное двоичное дерево, у которого все листья расположены на одном уровне, называют полным двоичным деревом. Высота полного двоичного дерева с n узлами равна [log2 n ].