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

Содержание

Слайды и текст этой презентации

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

бинарных деревьев
Представления и реализации бинарных деревьев
Примеры функций на бинарных деревьях
БД с размеченными листьями
Деревья Хаффмана (начало)

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

Слайд 224.09.2008
Деревья
procedure обходКЛП (b: BTree);
{прямой}
begin 
if not Null (b) then
begin
посетить

(Root (b));
обходКЛП (Left (b));
обходКЛП (Right (b));
end
end {обходКЛП};

4. Обходы бинарных деревьев и леса Обходы БД




24.09.2008Деревьяprocedure обходКЛП (b: BTree); {прямой} begin 	if not Null (b) then	begin 		посетить (Root

Слайд 324.09.2008
Деревья
Нерекурсивные процедуры обхода бинарных деревьев
В стеке S хранятся упорядоченные пары (p, n),


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

Слайд 424.09.2008
Деревья
В алгоритме:
посетить корень – посетить (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).
24.09.2008ДеревьяВ алгоритме:посетить корень – посетить (p);пройти левое поддерево − if not Null (Left (p))

Слайд 524.09.2008
Деревья
Общий алгоритм

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

Слайд 624.09.2008
Деревья
Выполнение procedure обход (b: BTree)
Операции со стеком:
⇓(b, 1);
⇑(b, 1); ⇓(b,

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

Слайд 724.09.2008
Деревья
КЛП
Операция 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);…;

24.09.2008ДеревьяКЛПОперация 1 –посетить (p);Операция 2  − if not Null (Left (p)) then	S ← (Left

Слайд 824.09.2008
Деревья

24.09.2008Деревья

Слайд 924.09.2008
Деревья
лкп
Операция 1  − if not Null (Left (p)) then S ← (Left (p), 1);
Операция

2 – посетить (p);
Операция 3  − if not Null (Right (p)) then S ← (Right (p), 1).

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

Слайд 1024.09.2008
Деревья

24.09.2008Деревья

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

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

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

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

Слайд 1324.09.2008
Деревья
КЛП


(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))))))

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

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

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

Слайд 1524.09.2008
Деревья
Примеры функций на бинарных деревьях
Число узлов БД:
0, при T = Λ
Nv(T)

=
Nv(TL) + Nv(TR) +1, при T ≠ Λ


Число листьев БД:
0, при T = Λ
NLeaf(T) = 1, при (TL = Λ) & (TR = Λ)
NLeaf(TL) + NLeaf(TR), иначе


24.09.2008ДеревьяПримеры функций на бинарных деревьяхЧисло узлов БД:		0, 	при T = ΛNv(T) =

Слайд 1624.09.2008
Деревья
Высота БД:
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

24.09.2008ДеревьяВысота БД:		0, 	при T = ΛH(T) = 		 max (H(TL), H(TR)) +1,

Слайд 1724.09.2008
Деревья
Проверить свойство дерева:
для каждого узла БД 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
! Самостоятельно написать хороший вариант
24.09.2008ДеревьяПроверить свойство дерева:для каждого узла БД H(TL) – H(TR) = 1Function HF

Слайд 1824.09.2008
Деревья
Бинарные деревья с размеченными листьями
〈БД РЛ〉 ::= 〈атом〉 ⏐ 〈пара〉
〈пара〉 ::=

〈БД РЛ〉 〈БД РЛ〉












F

E

D

C

B

А

БД РЛ ≡ S-expr

24.09.2008ДеревьяБинарные деревья с размеченными листьями〈БД РЛ〉 ::= 〈атом〉 ⏐ 〈пара〉〈пара〉 ::= 〈БД

Слайд 1924.09.2008
Деревья
БД → БД РЛ
А
B
C
D
E
F
G








А
B
D
C







E
F
G
r

24.09.2008ДеревьяБД → БД РЛАBCDEFGАBDCEFGr

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

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

Слайд 2124.09.2008
Деревья
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ ЛЕКЦИИ
КОНЕЦ

ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

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

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.


Для правообладателей

Яндекс.Метрика