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

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

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

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

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

5 Деревья5 procedure обход (b: BTree); var S: Stack of (BTree, operation); p: BTree; op: operation {=1..3}; begin S := Create; S (b, 1); while not Null (S) do begin (p, op) S; if op = 1 then begin S (p, 2); операция 1 end else if op = 2 then begin S (p, 3); операция 2 end else {op = 3} операция 3 end{while} end{обход} Общий алгоритм

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

7 Деревья7 КЛП Операция 1 –посетить (p); Операция 2 if not Null (Left (p)) thenS (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);…;

8 Деревья8 procedure обход_КЛП (b: BTree); {прямой} var S: Stack of BTree; p: BTree; begin S:= Create; S b; while not Null (S) do begin p S; посетить (p); if not Null (Right (p)) then S Right (p); if not Null (Left (p)) then S Left (p) end{while} end{обход_КЛП}

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

10 Деревья10 procedure обход_ЛКП (b: BTree); {обратный} var S: Stack of (BTree, operation); p: BTree; op: operation {=1..2}; begin S:= Create; S (b, 1); while not Null (S) do begin (p, op) S; if op = 1 then begin S (p, 2); if not Null (Left (p)) then S (Left (p), 1) end else {op=2} begin посетить (p); if not Null (Right (p)) then S (Right (p), 1) end end{while} end{обход_ЛКП}

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

12 Деревья12 Обход БД в горизонтальном порядке (в ширину) procedure обход_горизонтальный (b: BTree); var Q: queue of BTree; p: BTree; begin Q := Create; Q b; while not Null (Q) do begin p Q; посетить (p); if not Null (Left (p)) then Q Left (p); if not Null (Right (p)) then Q Right (p) end{while} end{обход_горизонтальный}

13 Деревья13 КЛП a b c d e f g h i j k l m n a d b e g c j f c h i k l m n (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))))))

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

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

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

17 Деревья17 Проверить свойство дерева: для каждого узла БД H(T L ) – H(T R ) = 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 ! Пояснить неэффективность такой реализации функции HF ! Самостоятельно написать хороший вариант

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

19 Деревья19 БД БД РЛ T: TLTL TRTR r S: S(T L ) S(T R ) А B C D E F G А B D C E F G r

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

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