Материал: АиСД деревья

else DisplayBT1 (RightBT (b), n+1);

if not NullBT (LeftBT (b)) then

begin

for i := 1 to n do Write (' '); {вправо}

DisplayBT1 (LeftBT (b), n+1);

end;

end;

end {DisplayBT1}

Определение структуры данных бинарного дерева через описанный в 3.2  набор базовых операций естественно с математической точки зрения и удобно при функциональном (рекурсивном) стиле программирования (в особенности в языках функционального программирования, например в Лиспе). Однако при итеративном стиле программирования в случае необходимости модификации дерева возникают некоторые неудобства, связанные с употреблением функции ConsBT. Дело в том, что если перестраивать бинарное дерево, работая только через базовые функции, т. е. не используя особенности ссылочного представления и работу с указателями, то приходится сначала «разбирать» текущее поддерево с помощью селекторов, а затем «собирать» заново с помощью конструктора ConsBT. При этом производятся соответствующие операции с динамической памятью для замены старого узла на новый. Это приводит к дополнительным накладным расходам при выполнении программы, которых во многих случаях можно избежать, вводя более удобный набор конструкторов. Например, полезно выделить как самостоятельные следующие дополнительные функции:

1) функцию MakeRoot, порождающую бинарное дерево из одного узла (корня);

2) функцию SetLeft, модифицирующую бинарное дерево таким образом, что на месте его пустого левого поддерева появляется заданный лист;

3) функцию SetRight, аналогичную SetLeft, но для правого поддерева.

Функциональная спецификация этих функций имеет вид:

MakeRoot: α  NonNullBT;

SetLeft: α  NonNullBT  NonNullBT;

SetRight: α  NonNullBT  NonNullBT

с набором аксиом:

• аксиомы для MakeRoot (u: α):

• Root (MakeRoot (u)) = u;

• Null (Left (MakeRoot (u))) = true;

• Null (Right (MakeRoot (u))) = true;

• аксиомы для SetLeft (u: α; b: NonNullBT: Null (Left (b))):

• Left (SetLeft (u, b)) = MakeRoot (u);

• Root (SetLeft (u, b)) = Root (b);

• Right (SetLeft (u, b)) = Right (b);

• аксиомы для SetRight (u: α; b:NonNullBT: Null (Right (b))):

• Right (SetRight (u, b)) = MakeRoot (u);

• Root (SetRight (u, b)) = Root (b);

• Left (SetRight (u, b)) = Left (b).

На уровне функциональной спецификации все эти функции могут быть выражены через функцию ConsBT. При этом приводимые далее соотношения справедливы для u: α и для таких переменных b1 и b2, что b2: NonNullBT: Null (Right (b2)); b1: NonNullBT: Null (Left (b1)):

• MakeRoot(u) = ConsBT(u, , );

• SetLeft (u, b1) = ConsBT (Root (b1), MakeRoot (u), Right (b1));

• SetRight (u, b2) = ConsBT (Root (b2), Left (b2), MakeRoot (u)).

Абстрактные функции SetLeft и SetRight удобнее реализовать в виде процедур, например:

Рассмотрим ссылочную реализации ограниченного бинарного дерева на базе вектора:

Здесь вектор типа Mem представляет собой память для хранения одного бинарного дерева (или нескольких бинарных деревьев, ограниченных в совокупности). Элемент вектора есть запись типа Node, содержащая узел и ссылки на поддеревья. На рис. 3.11 приведен пример представления бинарного дерева. Дерево представляется переменной b: BinT, причем значение b = 3 есть номер элемента массива, в котором хранится корень дерева. Фактически переменная b играет роль ссылки на корень дерева (или адреса корня в векторной памяти). Пустому дереву соответствовало бы значение b = 0, т. е. в этом представлении константа NillBT = 0. Элементы вектора, не занятые под хранение узлов дерева, образуют свободную память, которую удобно организовать в виде линейного циклического списка (для этого используется одно из полей звена Node, например, поле LSub). При этом элемент вектора с индексом (адресом) 0 играет роль ссылки на начало списка свободной памяти.

Рис. 3.11. Пример ссылочного представления бинарного дерева на базе вектора. Справа – бинарное дерево; слева – его размещение в массиве, играющем роль динамической памяти

Более подробное описание данной реализации рекомендуется в качестве самостоятельного упражнения, поскольку она во многом аналогична ссылочной реализации линейного списка на базе вектора, рассмотренной в 1.4.

Упражнения

При выполнении упражнений следует использовать вариант реализации бинарного дерева (см. 3.5), соответствующий варианту.

Для представления деревьев во входных данных рекомендуется использовать скобочную запись, кроме случаев, специально оговоренных в условии задачи. В выходных данных рекомендуется представлять дерево (лес) в горизонтальном виде (т. е. с поворотом на 90°), а бинарные деревья  в виде уступчатого списка.

В заданиях 1  4, в зависимости от варианта, предлагается реализовать рекурсивные или нерекурсивные процедуры (функции); в последнем случае следует использовать стек и операции над ним.

1. Задано бинарное дерево b типа BT с типом элементов Elem. Для введенной пользователем величины E (var E: Elem):

- определить, входит ли элемент Е в дерево b;

- определить число вхождений элемента Е в дерево b;

- найти в дереве b длину пути (число ветвей) от корня до ближайшего узла с элементом Е (если Е не входит в b, за ответ принять 1).

2. Для заданного бинарного дерева b типа BT с произвольным типом элементов:

- определить максимальную глубину дерева b, т. е. число ветвей в самом длинном из путей от корня дерева до листьев;

- вычислить длину внутреннего пути дерева b, т. е. сумму по всем узлам длин путей от корня до узла;

- напечатать элементы из всех листьев дерева b;

- подсчитать число узлов на заданном уровне n дерева b (корень считать узлом 1-го уровня);

3. Для заданного бинарного дерева b типа BT с произвольным типом элементов определить, есть ли в дереве b хотя бы два одинаковых элемента.

4. Заданы два бинарных дерева b1 и b2 типа BT с произвольным типом элементов. Проверить:

- подобны ли они (два бинарных дерева подобны, если они оба пусты либо они оба непусты и их левые поддеревья подобны и правые поддеревья подобны);

- равны ли они (два бинарных дерева равны, если они подобны и их соответствующие элементы равны);

- зеркально подобны ли они (два бинарных дерева зеркально подобны, если они оба пусты либо они оба непусты и для каждого из них левое поддерево одного подобно правому поддереву другого);

- симметричны ли они (два бинарных дерева симметричны, если они зеркально подобны и их соответствующие элементы равны).

5. Задано бинарное дерево b типа ВТ с произвольным типом элементов. Используя очередь и операции над ней, напечатать все элементы дерева b по уровням: сначала  из корня дерева, затем (слева направо)  из узлов, сыновних по отношению к корню, затем (также слева направо)  из узлов, сыновних по отношению к этим узлам, и т. д.

6. Для заданного леса с произвольным типом элементов:

- получить естественное представление леса бинарным деревом;

- вывести изображение леса и бинарного дерева;

- перечислить элементы леса в горизонтальном порядке (в ширину).

7. (Обратная задача.) Для заданного бинарного дерева с произвольным типом элементов:

- получить лес, естественно представленный этим бинарным деревом;

- вывести изображение бинарного дерева и леса;

- перечислить элементы леса в горизонтальном порядке (в ширину).

8. Рассматриваются бинарные деревья с элементами типа Elem (в качестве Elem использовать char). Заданы перечисления узлов некоторого дерева b в порядке КЛП и ЛКП. Требуется:

- восстановить дерево b и вывести его изображение;

- перечислить узлы дерева b в порядке ЛПК.

9. Рассматриваются бинарные деревья с элементами типа Elem (в качестве Elem использовать char). Заданы перечисления узлов некоторого дерева b в порядке ЛКП и ЛПК. Требуется:

- восстановить дерево b и вывести его изображение;

- перечислить узлы дерева b в порядке КЛП.

10-13. Формулу вида

< формула > ::= < терминал > | ( < формула > < знак > < формула > )

< знак > ::= + |  | *

< терминал > ::= 0 | 1 | ... | 9 | a | b | ... | z

можно представить в виде бинарного дерева («дерева-формулы») с элементами типа Elem=char согласно следующим правилам:

- формула из одного терминала представляется деревом из одной вершины с этим терминалом;

- формула вида (f₁ s f₂) представляется деревом, в котором корень  это знак s, а левое и правое поддеревья  соответствующие представления формул f₁ и f₂. Например, формула (5 * (a + 3)) представляется деревом-формулой, показанной на рис. 3.12.

Error: Reference source not found

Рис. 3.12. Дерево-формулa

Требуется:

- Для всех вариантов (10-13):

- для заданной формулы f построить дерево-формулу t;

- для заданного дерева-формулы t напечатать соответствующую формулу f;

Вариант 10:

- с помощью построения дерева-формулы t преобразовать заданную формулу f из инфиксной формы в префиксную (перечисление узлов t в порядке КЛП) и в постфиксную (перечисление в порядке ЛПК);

- преобразовать дерево-формулу t, заменяя в нем все подде­ревья, соответствующие формулам (f₁ * (f₂ + f₃)) и ((f₁ + f₂) * f₃), на поддеревья, соответствующие формулам ((f₁ * f₂) + (f₁ * f₃)) и ((f₁ * f₃) + (f₂ * f₃)).

Вариант 11:

- с помощью построения дерева-формулы t преобразовать заданную формулу f из префиксной формы (перечисление узлов t в порядке КЛП) в инфиксную;

- упростить дерево-формулу t, заменяя в нем все поддеревья, соответствующие формулам (f + 0), (0 + f), (f  0), (f * 1), (1 * f), на поддеревья, соответствующие формуле f, а поддеревья, соответствующие формулам (f * 0) и (0 * f),  на узел с 0.

Вариант 12:

- если в дереве-формуле t терминалами являются только цифры, то вычислить (как целое число) значение дерева-формулы t;

- построить дерево-формулу t1  производную дерева-формулы t по заданной переменной.

Вариант 13:

- преобразовать дерево-формулу t, заменяя в нем все подде­ревья, соответствующие формулам ((f₁ * f₂) + (f₁ * f₃)) и ((f₁ * f₃) + (f₂ * f₃)), на поддеревья, соответствующие формулам (f₁ * (f₂ + f₃)) и ((f₁ + f₂) * f₃);

- с помощью построения дерева-формулы t преобразовать заданную формулу f из постфиксной формы (перечисление узлов в порядке ЛПК) в инфиксную.

14. Бинарное дерево называется бинарным деревом поиска, если для каждого его узла справедливо: все элементы правого поддерева больше этого узла, а все элементы левого поддерева – меньше этого узла.

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