Лекция 6 ДЕРЕВЬЯ (продолжение) Нерекурсивные процедуры обхода бинарных деревьев Представления и реализации бинарных деревьев Примеры функций на бинарных деревьях БД с размеченными листьями Деревья Хаффмана (начало)


The Presentation inside:

Slide 0

24.09.2008 Деревья 1 Структуры и алгоритмы обработки данных, 1 Лекция 6 ДЕРЕВЬЯ (продолжение) Нерекурсивные процедуры обхода бинарных деревьев Представления и реализации бинарных деревьев Примеры функций на бинарных деревьях БД с размеченными листьями Деревья Хаффмана (начало)


Slide 1

24.09.2008 Деревья 2 procedure обходКЛП (b: BTree); {прямой} begin  if not Null (b) then begin посетить (Root (b)); обходКЛП (Left (b)); обходКЛП (Right (b)); end end {обходКЛП}; 4. Обходы бинарных деревьев и леса Обходы БД


Slide 2

24.09.2008 Деревья 3 Нерекурсивные процедуры обхода бинарных деревьев В стеке S хранятся упорядоченные пары (p, n), где p ? узел бинарного дерева, а n ? номер операции, которую надо применить к p, когда пара (p, n) будет выбрана из стека. Операции «посетить корень», «пройти левое поддерево», «пройти правое поддерево» нумеруются числами 1, 2, 3 в зависимости от порядка их выполнения в данном варианте обхода.


Slide 3

24.09.2008 Деревья 4 В алгоритме: посетить корень – посетить (p); пройти левое поддерево ? if not Null (Left (p)) then S ? (Left (p), 1); пройти правое поддерево ? if not Null (Right (p)) then S ? (Right (p), 1). Для краткости использованы следующие обозначения операций со стеком: S ? e вместо S := Push (e, S) e ? S вместо Pop2 (e, S).


Slide 4

24.09.2008 Деревья 5 Общий алгоритм


Slide 5

24.09.2008 Деревья 6 Выполнение procedure обход (b: BTree) Операции со стеком: ?(b, 1); ?(b, 1); ?(b, 2); {начало Опер1}… ??…{конец Опер1} ?(b, 2); ?(b, 3); {начало Опер2}… ??…{конец Опер2} ?(b, 3); {начало Опер3}… ??…{конец Опер3}


Slide 6

24.09.2008 Деревья 7 КЛП Операция 1 –посетить (p); Операция 2  ? if not Null (Left (p)) then S ? (Left (p), 1); Операция 3  ? if not Null (Right (p)) then S ? (Right (p), 1). ?(b, 1); ?(b, 1); ?(b, 2); посетить (p); ?(b, 2); ?(b, 3); if not Null (Left (p)) then ?(Left (p), 1); ?(Left (p), 1); …; ?(b, 3); if not Null (Right (p)) then ?(Right (p), 1); ?(Right (p), 1);…;


Slide 7

24.09.2008 Деревья 8


Slide 8

24.09.2008 Деревья 9 лкп Операция 1  ? if not Null (Left (p)) then S ? (Left (p), 1); Операция 2 – посетить (p); Операция 3  ? if not Null (Right (p)) then S ? (Right (p), 1). Самостоятельно разобрать работу со стеком и обосновать корректность следующей процедуры.


Slide 9

24.09.2008 Деревья 10


Slide 10

24.09.2008 Деревья 11 ЛПК См. пособие – фактически без упрощений


Slide 11

24.09.2008 Деревья 12 Обход БД в горизонтальном порядке (в ширину)


Slide 12

24.09.2008 Деревья 13 КЛП (a (d) (e (j) (k)) (f (l))) (b (g) (h)) (c (i (m) (n))) КЛП: a d b e g c j f h i k l m n (a (d ? (e (j ?(k)) (f (l)) (b (g ? (h)) (c (i (m ?(n))))))


Slide 13

24.09.2008 Деревья 14 Представления и реализации бинарных См. учебное пособие «ДСД», п. 3.5


Slide 14

24.09.2008 Деревья 15 Примеры функций на бинарных деревьях Число узлов БД: 0, при T = ? Nv(T) = Nv(TL) + Nv(TR) +1, при T ? ? Число листьев БД: 0, при T = ? NLeaf(T) = 1, при (TL = ?) & (TR = ?) NLeaf(TL) + NLeaf(TR), иначе


Slide 15

24.09.2008 Деревья 16 Высота БД: 0, при T = ? H(T) = max (H(TL), H(TR)) +1, при T ? ? Function H (t: BinT): Nat0; begin if Null(t) then H := 0 else H := max (H(LeftBT(t)), H(RightBT(t))) +1 end


Slide 16

24.09.2008 Деревья 17 Проверить свойство дерева: для каждого узла БД H(TL) – H(TR) = 1 Function HF (t: BinT): Boolean; begin if Null(t) then HB := True else begin HL := H(LeftBT(t)); HR := H(RightBT(t)); HF := HF(LeftBT(t)) & HF(RightBT(t)) & ( (HL – HR) = 1) end end ! Пояснить неэффективность такой реализации функции HF ! Самостоятельно написать хороший вариант


Slide 17

24.09.2008 Деревья 18 Бинарные деревья с размеченными листьями ?БД РЛ? ::= ?атом? ? ?пара? ?пара? ::= ?БД РЛ? ?БД РЛ? F E D C B А БД РЛ ? S-expr


Slide 18

24.09.2008 Деревья 19 БД ? БД РЛ А B C D E F G А B D C E F G r


Slide 19

24.09.2008 Деревья 20 Деревья Хаффмана См. разделы пособия «ДКиП» 1.1.-1.4 (файлы MS Word)


Slide 20

24.09.2008 Деревья 21 КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ КОНЕЦ ЛЕКЦИИ


×

HTML:





Ссылка: