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

Презентация на тему Презентация на тему Лекция 6 ДЕРЕВЬЯ (продолжение) Нерекурсивные процедуры обхода бинарных деревьев Представления и реализации бинарных деревьев Примеры функций на бинарных деревьях БД с размеченными листьями Деревья Хаффмана (начало), предмет презентации: Разное. Этот материал содержит 21 слайдов. Красочные слайды и илюстрации помогут Вам заинтересовать свою аудиторию. Для просмотра воспользуйтесь проигрывателем, если материал оказался полезным для Вас - поделитесь им с друзьями с помощью социальных кнопок и добавьте наш сайт презентаций ThePresentation.ru в закладки!

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

Слайд 1
Текст слайда:

24.09.2008

Деревья

Структуры и алгоритмы обработки данных, 1

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


Слайд 2
Текст слайда:

24.09.2008

Деревья

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

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





Слайд 3
Текст слайда:

24.09.2008

Деревья

Нерекурсивные процедуры обхода бинарных деревьев

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


Слайд 4
Текст слайда:

24.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).


Слайд 5
Текст слайда:

24.09.2008

Деревья

Общий алгоритм


Слайд 6
Текст слайда:

24.09.2008

Деревья

Выполнение procedure обход (b: BTree)

Операции со стеком:
⇓(b, 1);
⇑(b, 1); ⇓(b, 2); {начало Опер1}… ↓↑…{конец Опер1}
⇑(b, 2); ⇓(b, 3); {начало Опер2}… ↓↑…{конец Опер2}
⇑(b, 3); {начало Опер3}… ↓↑…{конец Опер3}


Слайд 7
Текст слайда:

24.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);…;


Слайд 8
Текст слайда:

24.09.2008

Деревья


Слайд 9
Текст слайда:

24.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).

Самостоятельно разобрать работу со стеком и обосновать корректность следующей процедуры.


Слайд 10
Текст слайда:

24.09.2008

Деревья


Слайд 11
Текст слайда:

24.09.2008

Деревья

ЛПК

См. пособие – фактически без упрощений


Слайд 12
Текст слайда:

24.09.2008

Деревья

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


Слайд 13
Текст слайда:

24.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))))))


Слайд 14
Текст слайда:

24.09.2008

Деревья

Представления и реализации бинарных

См. учебное пособие «ДСД», п. 3.5


Слайд 15
Текст слайда:

24.09.2008

Деревья

Примеры функций на бинарных деревьях

Число узлов БД:
0, при T = Λ
Nv(T) =
Nv(TL) + Nv(TR) +1, при T ≠ Λ


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



Слайд 16
Текст слайда:

24.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


Слайд 17
Текст слайда:

24.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
! Самостоятельно написать хороший вариант


Слайд 18
Текст слайда:

24.09.2008

Деревья

Бинарные деревья с размеченными листьями

〈БД РЛ〉 ::= 〈атом〉 ⏐ 〈пара〉
〈пара〉 ::= 〈БД РЛ〉 〈БД РЛ〉












F

E

D

C

B

А

БД РЛ ≡ S-expr


Слайд 19
Текст слайда:

24.09.2008

Деревья

БД → БД РЛ

А

B

C

D

E

F

G









А

B

D

C








E

F

G

r


Слайд 20
Текст слайда:

24.09.2008

Деревья

Деревья Хаффмана

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


Слайд 21
Текст слайда:

24.09.2008

Деревья

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ

КОНЕЦ ЛЕКЦИИ


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

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

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

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

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


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

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