Similar presentations:
Деревья. Лекция 6
1.
Алгоритмы и структуры данныхЛекция 6
ДЕРЕВЬЯ
(продолжение)
1.
Представления и реализации бинарных деревьев (См.
2.
3.
Примеры функций на бинарных деревьях
БД с размеченными листьями
учебное пособие «ДСД», п. 3.5)
10.10.2019
Деревья
1
2.
Ссылочная реализация бинарногодерева в связанной памяти
Базовый тип узлов Elem.
BT (Elem) представляетя рекурсивными типами BinT и
Node
type
BinT = ^Node;
{представление бинарного
дерева}
Node = record
{узел: }
Info: Elem; { содержимое}
LSub: BinT; { левое поддерево}
RSub: BinT { правое поддерево}
end {Node}
10.10.2019
Деревья
2
3.
Пример: бинарное дерево (а) и егопредставление в ссылочной реализации (б)
a
b
d
c
e
f
g
а
a
b
c
d
e
f
g
б
10.10.2019
Деревья
3
4.
Набор основных функций для работы сбинарным деревом на основе ссылочной
реализации
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);
Функция CreateBT формально специфицируется соотношениями
CreateBT: BT; Null (CreateBT) = true.
Otkaz вызывается при попытке некорректного применения основных функций
10.10.2019
Деревья
4
5.
В процедурно-модульной парадигмеинтерфейс АТД "Бинарное дерево” представлен
в файле Btree.h,
реализация основных функций для работы с АТД
"Бинарное дерево” - в файле
bt_implementanion.cpp,
пример работы с АТД "Бинарное дерево” - в
файле work_bt.cpp, где для ввода BT из файла
используется его КЛП-представление, а для
вывода его на экран порядок КЛП, ЛКП и ЛПК.
Программа также подсчитывает высоту и количество узлов BT.
10.10.2019
Деревья
5
6.
Ссылочная реализация ограниченногобинарного дерева на базе вектора
type Adr = 0 .. MaxAdr;
{диапазон «адресов» в векторе Mem}
BinT = Adr;
{представление бинарного дерева}
Node = record
{узел: }
Info: Elem;
{ содержимое}
LSub: BinT;
{ левое поддерево}
RSub: BinT
{ правое поддерево}
end {Node};
Mem = array [Adr] of Node {вектор для хранения дерева}
10.10.2019
Деревья
6
7.
Пример ссылочного представлениябинарного дерева на базе вектора
Дерево представляется переменной b: Bin T, значение b = 3 - номер
элемента массива, в котором хранится корень.
LSub
10.10.2019
Info
0:
2
1:
2:
0
3:
RSub
Связи списка
свободной
памяти:
Бинарное
дерево:
a
f
0
5
a
4
4:
0
c
1
5:
8
b
7
6:
9
7:
10
e
0
8:
0
d
0
9:
11
10:
0
g
0
11:
12
12:
0
6
b
c
d
e
f
g
Деревья
7
8.
Примеры функций на бинарных деревьяхT:
Число узлов БД:
0,
TL
TR
при 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);
}
10.10.2019
Деревья
8
9.
Примеры функций на бинарных деревьяхЧисло листьев БД:
T:
TL
TR
0,
при T =
NLeaf(T) = 1,
при (TL = ) & (TR = )
NLeaf(TL) + NLeaf(TR), иначе
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)));
}
10.10.2019
Деревья
9
10.
Высота БД:T:
0,
при T =
H(T) =
TL
TR
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);
}
10.10.2019
Деревья
10
11.
Вычисление H (b)H( )=0
H(
b
5
3
4
)=1
2
0 1
2
1
3
1
0 0
0
2
0
0 00 0
0
1
0 0
10.10.2019
Деревья
11
12.
Проверить свойство дерева:для каждого узла БД имеем 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
!Самостоятельно написать хороший вариант
10.10.2019
Деревья
12
13.
Бинарные деревья с размеченнымилистьями (комбинации)
Бинарное дерево с размеченными листьями - это
либо знак («атом», атомарное дерево), либо
(упорядоченная) пара бинарных деревьев с
размеченными листьями.
comb( ) ::= atomic( ) left( ) right( )
atomic( ) ::=
left( ) ::= comb( )
right( ) ::= comb( )
Можно ввести понятие «пара» (pair):
comb( ) ::= atomic( ) pair( )
pair( ) ::= comb( ) comb( )
10.10.2019
Деревья
13
14.
Примеры скобочной записи играфического изображения комбинаций:
(a.b)
a
b
((a.b).(c.d.))
a
b
((a.b).c)
c
a
(a.(b.c))
b
a
b
10.10.2019
d
c
Деревья
c
14
15.
Cмешанное бинарное дерево (СБД)Можно ввести «гибрид» бинарных деревьев и
комбинаций.
Определим смешанное (расширенное, декорированное)
бинарное дерево (СБД) над базовыми типами
(внутренние узлы) и (внешние узлы - листья):
СБД( , ) ::= atomic( ) root( ) left( , ) right( , ) ,
atomic( ) ::= ,
root( ) ::= ,
left( , ) ::= СБД( , ) ,
right( , ) ::= СБД( , ) .
10.10.2019
Деревья
15
16.
Примеры СБД= {A, B, C, …}; = {a, b, c, …}
A
A
B
a
b
a
A
B
a
b
cc
d
D
b
10.10.2019
C
e
c
Если - пусто, то получим комбинации
над типом , а если - пусто (пустое
дерево),
то
получим
бинарные
деревья над типом .
Деревья
16
17.
Соответствие между деревьями (T) икомбинациями (С)
• дерево с нулевым лесом поддеревьев (с пустым листингом)
соответствует атомарной комбинации;
• дерево с ненулевым лесом поддеревьев (с непустым
листингом) преобразуется в комбинацию так, что первое
дерево леса соответствует левой части комбинации, а
оставшееся дерево, состоящее из корня и остальных деревьев
леса, соответствует правой части комбинации.
10.10.2019
Деревья
17
18.
Формально соответствие «дерево комбинация»может быть описано функцией
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))) – дерево, состоящее из корня
исходного дерева и остальных деревьев леса его поддеревьев.
10.10.2019
Деревья
18
19.
Преобразование на предыдущем слайде можноразвернуть по последовательности поддеревьев:
10.10.2019
Деревья
19
20.
Пример преобразования«дерево комбинация»
a
b
b
c
e
d
f
e
a
d
f
c
Обратное преобразование из комбинации в дерево получается обращением
стрелок на рисунках слайдов 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)))))
10.10.2019
Деревья
20
21.
Преобразования«бинарное дерево комбинация»
1. бинарное дерево лес,
2. лес дерево (добавляется фиктивный корень),
3. дерево комбинация
a
c
b
e
d
b
f
d
c
a
b
10.10.2019
d
a
e
c
f
f
e
Деревья
21
22.
Примеры соответствия комбинаторных объектов (3 узла)Задание. Представить аналогичную таблицу для случая «Число узлов =4».
Дональд Э. Кнут, Искусство программирования. Том 4. Выпуск 4. Генерация всех деревьев.
№
Лес
Бинарное дерево
Комбинация
Скобки
1
()()()
2
()(())
3
(())()
4
(()())
5
((()))
10.10.2019
Деревья
Рукопожатия
22
23.
Ползущий червьСкобки: ( ( )
10.10.2019
())
((( ) (
Деревья
) (
)))
23
24.
КОНЕЦ ЛЕКЦИИКОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
10.10.2019
Деревья
24