Деревья. Лекция 6

*
Деревья
Ссылочная реализация бинарного дерева в связанной памяти
Базовый тип узлов Elem.
BT (Elem) представляетя рекурсивными типами BinT и Node
type
BinT = ^Node; {представление бинарного дерева}
Node = record {узел: }
Info: Elem; {− содержимое}
LSub: BinT; {− левое поддерево}
RSub: BinT {− правое поддерево}
end {Node}

Пример: бинарное дерево (а) и его представление в ссылочной реализации (б)
*
Деревья

Набор основных функций для работы с бинарным деревом на основе ссылочной реализации
Функция CreateBT формально специфицируется соотношениями
CreateBT: → BT; Null (CreateBT) = true.
Otkaz вызывается при попытке некорректного применения основных функций
*
Деревья
CreateBT: BinT;
NullBT (t: BinT): Boolean;
RootBT (t: BinT): Elem;
LeftBT (t: BinT): BinT;
RightBT (t: BinT): BinT;
ConsBT (e: Elem; LS, RS: BinT): BinT;
DestroyBT (var b: BinT);
Otkaz (n: Byte);

В процедурно-модульной парадигме
интерфейс АТД "Бинарное дерево” представлен в файле Btree.h,
реализация основных функций для работы с АТД "Бинарное дерево” - в файле bt_implementanion.cpp,
пример работы с АТД "Бинарное дерево” - в файле work_bt.cpp, где для ввода BT из файла используется его КЛП-представление, а для вывода его на экран порядок КЛП, ЛКП и ЛПК.
Программа также подсчитывает высоту и количество узлов BT.
*
Деревья

Ссылочная реализация ограниченного бинарного дерева на базе вектора
*
Деревья

Пример ссылочного представления бинарного дерева на базе вектора
*
Деревья
LSub
Info
RSub
Связи списка свободной памяти:
Дерево представляется переменной b: Bin T, значение b = 3 - номер элемента массива, в котором хранится корень.

*
Деревья
Примеры функций на бинарных деревьях
Число узлов БД:
0, при T = Λ
Nv(T) =
Nv(TL) + Nv(TR) +1, при T ≠ Λ
Nat0 Nv (BinT t)
{
if (Null(t)) return 0;
else return (Nv (LeftBT(t)) + Nv (RightBT(t)) +1);
}

*
Деревья
Примеры функций на бинарных деревьях
Nat0 NLeaf (BinT t):
{
if (Null(t)) return 0;
else if (Null(LeftBT(t)) && Null(RightBT(t))) return 1;
else return (NLeaf (LeftBT(t)) + NLeaf (RightBT(t)));
}
Число листьев БД:
0, при T = Λ
NLeaf(T) = 1, при (TL = Λ) & (TR = Λ)
NLeaf(TL) + NLeaf(TR), иначе

*
Деревья
Высота БД:
0, при T = Λ
H(T) =
max (H(TL), H(TR)) +1, при T ≠ Λ
Nat0 H ( BinT t)
{
if (Null(t)) return 0;
else return (max (H(LeftBT(t)), H(RightBT(t))) +1);
}

Вычисление H (b)
*
Деревья
H(Λ)=0
0
0
1
0
2
0
0
1
0
2
3
0
0
1
0
0
1
2
3
0
4
5
0
b

*
Деревья
Проверить свойство дерева:
для каждого узла БД имеем H(TL) – H(TR) = 1
Bool HF (BinT t)
{ if (Null(t)) return true;
else
{
HL = H(LeftBT(t));
HR = H(RightBT(t));
return (HF(LeftBT(t)) && HF(RightBT(t)) && ( (HL – HR) == 1));
}
}
!Пояснить неэффективность такой реализации функции HF
!Самостоятельно написать хороший вариант

Бинарные деревья с размеченными листьями (комбинации)
Бинарное дерево с размеченными листьями - это либо знак («атом», атомарное дерево), либо (упорядоченная) пара бинарных деревьев с размеченными листьями.
〈comb(α)〉 ::= 〈atomic(α)〉 ⏐ 〈left(α)〉 〈right(α)〉
〈atomic(α)〉 ::= 〈α〉
〈left(α)〉 ::= 〈comb(α)〉
〈right(α)〉::= 〈comb(α)〉
Можно ввести понятие «пара» (pair):
〈comb(α)〉 ::= 〈atomic(α)〉 ⏐〈pair(α)〉
〈pair(α)〉 ::= 〈comb(α)〉 〈comb(α)〉
*
Деревья

Примеры скобочной записи и графического изображения комбинаций:
*
Деревья
a
b
c
d
a
b
c
a
b
c

Cмешанное бинарное дерево (СБД)
Можно ввести «гибрид» бинарных деревьев и комбинаций.
Определим смешанное (расширенное, декорированное) бинарное дерево (СБД) над базовыми типами α (внутренние узлы) и β (внешние узлы - листья):
〈СБД(α, β)〉 ::= 〈atomic(β)〉 ⏐〈root(α)〉 〈left(α, β)〉 〈right(α,β)〉,
〈atomic(β)〉 ::= 〈β〉,
〈root(α)〉 ::= 〈α〉,
〈left(α, β)〉 ::= 〈СБД(α, β)〉,
〈right(α,β)〉 ::= 〈СБД(α, β)〉.
*
Деревья

Примеры СБД
*
Деревья
α = {A, B, C, …}; β = {a, b, c, …}
A
A
B
b
c
Если α - пусто, то получим комбинации над типом β, а если β - пусто (пустое дерево), то получим бинарные деревья над типом α.

Соответствие между деревьями (T) и комбинациями (С)
дерево с нулевым лесом поддеревьев (с пустым листингом) соответствует атомарной комбинации;
дерево с ненулевым лесом поддеревьев (с непустым листингом) преобразуется в комбинацию так, что первое дерево леса соответствует левой части комбинации, а оставшееся дерево, состоящее из корня и остальных деревьев леса, соответствует правой части комбинации.
*
Деревья

Формально соответствие «дерево ⇒ комбинация» может быть описано функцией
C(T) ≡ if Null(Listing(T)) then Root(T)
else ConsComb ( C(Head(Listing(T))), C( ConsTree(Root(T), Tail(Listing(T))))
Listing(T) – лес поддеревьев исходного дерева,
Head(Listing(T)) – первое дерево этого леса,
Tail(Listing(T)) – лес остальных поддеревьев (т.е. за исключением первого),
ConsTree(Root(T), Tail(Listing(T))) – дерево, состоящее из корня исходного дерева и остальных деревьев леса его поддеревьев.
*
Деревья

Преобразование на предыдущем слайде можно развернуть по последовательности поддеревьев:
*
Деревья

Обратное преобразование из комбинации в дерево получается обращением стрелок на рисунках слайдов 17, 19 и описывается функцией
T(C) ≡ if Atom(C) then ConsTree(Val(C), nil)
else ConsTree(Root(T(Right(C))), Cons(T(Left(C)), Listing(T(Right(C)))))
Пример преобразования
«дерево ⇒ комбинация»
*
Деревья

Преобразования
«бинарное дерево ⇒ комбинация»
*
Деревья
1. бинарное дерево ⇒ лес,
2. лес ⇒ дерево (добавляется фиктивный корень),
3. дерево ⇒ комбинация

Примеры соответствия комбинаторных объектов (3 узла)
*
Деревья
Задание. Представить аналогичную таблицу для случая «Число узлов =4».
Дональд Э. Кнут, Искусство программирования. Том 4. Выпуск 4. Генерация всех деревьев.

Ползущий червь
*
Деревья