Презентация Графы: деревья онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Графы: деревья абсолютно бесплатно. Урок-презентация на эту тему содержит всего 41 слайд. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:41 слайд
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:217.98 kB
- Просмотров:89
- Скачиваний:2
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда: ПРОГРАММИРОВАНИЕ
Семинар 11.
Графы: деревья
№2 слайд
Содержание слайда: Определения
(a, b) = {a, {a, b}} — упорядоченная пара.
(a, b) = (c, d)⇔ a = c & b = d
{a, b} = {b, a}
A× B = {(a, b) | a ∈ A & b ∈ B} — декартово произведение.
№3 слайд
Содержание слайда: Пример
A = {1, 2}
B = {2, 3, 4}
A× B = {(1, 2), (1, 3), (1, 4), (2, 2),
(2, 3), (2, 4)}
№4 слайд
Содержание слайда: Отношения
Произвольное подмножество A× B называется отношением из A в B.
A — область определения.
B — область значений.
Если A = B, то отношение задано
на A.
(a, b)∈ R ⇔ aRb
№5 слайд
Содержание слайда: Свойства отношений
Пусть на множестве A задано отношение R:
рефлексивное, если aRa∀a∈ A;
симметричное, если aRb⇒ bRa∀a, b∈ A;
транзитивное, если aRb & bRc⇒ aRc∀a, b, c∈ A.
Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.
A = ⋃a∈ A Aa — разбиение:
Aa = {b | aRb} — класс эквивалентности;
Aa⋂ Ab =∅, a ≠ b.
№6 слайд
Содержание слайда: Графы
Неупорядоченный граф G = (V, E), где:
V — множество вершин;
E — отношение на V.
Граф G ориентированный (орграф), если E — асимметричное, иначе — неориентированный.
№7 слайд
Содержание слайда: Пример
V = {1, 2, 3, 4}
E = {(1, 1), (1, 2), (2, 3), (2, 4), (3, 4), (4, 1), (4, 3)}
№8 слайд
Содержание слайда: Графы
(a, b)∈ R — дуга (ребро):
дуга выходит из a и входит в b;
a предшествует b;
b следует за a;
b смежна с a.
№9 слайд
Содержание слайда: Пути в графах
Последовательность вершин (a0, a1, a2, …, an), n ≥ 1 называется путём (маршрутом) длины n из a0 в an, если (ai - 1, ai)∈ E∀i∈ {1, 2, …, n}, при этом, говорят, что an достижима из a0.
Путь, в котором a0 = an, называется циклом.
Орграф называется сильно связным, если для любых его двух вершин существует путь из одной в другую.
№10 слайд
Содержание слайда: Степень вершины
Степень по входу (полустепень входа) вершины — число входящих в неё дуг.
Степень по выходу (полустепень выхода) вершины — число исходящих из неё дуг.
Если граф неориентированный, то степень вершины — количество связанных с ней рёбер.
№11 слайд
Содержание слайда: Ациклические графы
Ациклический граф — орграф без циклов.
Вершина с полустепенью входа 0 — базовая.
Вершина с полустепенью выхода 0 — лист (концевая).
№12 слайд
Содержание слайда: Пример
Базовая
№13 слайд
Содержание слайда: Ациклические графы
(a, b)∈ R — дуга:
a — прямой предок b;
b — прямой потомок a.
Если существует путь из a в b, то:
a — предок b;
b — потомок a.
№14 слайд
Содержание слайда: Деревья
(Ориентированное) дерево — (ориентированный) граф со специальной вершиной r (корнем):
полустепень по входу равна 0;
полустепень по входу всех остальных равна 1;
каждая вершина достижима из корня.
Свойства:
1. Дерево — ациклический граф.
2. Для каждой вершины дерева существует единственный путь в неё из корня.
№15 слайд
Содержание слайда: Поддерево
Поддерево дерева T = (V, E) — любое дерево T' = (V', E'):
1. V' ≠ ∅ & V'⊆ V.
2. E' = (V'× V')⋂ E.
3. Ни одна вершина из V \ V' не является потомком вершины из V'.
Орграф из нескольких деревьев — лес.
№16 слайд
Содержание слайда: Пример
№17 слайд
Содержание слайда: Деревья
(a, b)∈ R — дуга:
a — отец b;
b — сын a.
Глубина (уровень) вершины — длина пути до неё из корня.
Высота вершины — длина максимального пути от неё до листа.
Высота дерева — длина максимального пути от корня до листа.
№18 слайд
Содержание слайда: Бинарные деревья
Упорядоченное дерево — дерево, в котором множество сыновей каждой вершины упорядочено слева направо.
Бинарное дерево — это упорядоченное дерево:
1. Любой сын либо левый, либо правый.
2. Любая вершина имеет не более одного левого и не более одного правого сына.
№19 слайд
Содержание слайда: Пример
№20 слайд
Содержание слайда: Бинарные деревья
Бинарное дерево полное, если существует целое k, такое что любая вершина глубины меньше k имеет и левого, и правого сыновей, а любая вершина глубины k — лист.
№21 слайд
Содержание слайда: Пример
№22 слайд
Содержание слайда: Представление полных бинарных деревьев
Массив T[2k - 2]:
T[0] — корень;
левый сын вершины i — T[2 * i - 1];
правый сын вершины i — T[2 * i].
Отец вершины в позиции i > 0 расположен в позиции ⌊i / 2⌋ - 1.
№23 слайд
Содержание слайда: Пример
T == {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}
№24 слайд
Содержание слайда: Обходы деревьев
Обход дерева — способ исследования вершин дерева, при котором каждая вершина проходится только один раз.
Виды:
1. В глубину.
2. В ширину.
№25 слайд
Содержание слайда: Обходы деревьев в глубину
Пусть T — дерево c корнем r, а v1, v2, …, vn — сыновья r.
Прямой (префиксный) обход:
1. Посетить корень r.
2. Посетить в прямом порядке поддеревья с корнями v1, v2, …, vn.
Обратный (постфиксный) обход:
1. Посетить в обратном порядке поддеревья с корнями v1, v2, …, vn.
2. Посетить корень r.
Внутренний (инфиксный) обход:
1. Посетить в0 внутреннем порядке левое поддерево корня r.
2. Посетить корень r.
3. Посетить в0 внутреннем порядке правое поддерево корня r.
№26 слайд
Содержание слайда: Пример: прямой обход
№27 слайд
Содержание слайда: Пример: обратный обход
№28 слайд
Содержание слайда: Пример: внутренний обход
№29 слайд
Содержание слайда: Пример
№30 слайд
Содержание слайда: Пример
Префиксный: + * a - d e / + f g c
Постфиксный: a d e - * f g + c / +
Инфиксный: a * (d - e) + (f + g) / c
№31 слайд
Содержание слайда: Обход в ширину
Это обход по уровням, начиная от корня, слева направо (или справа налево).
Алгоритм:
0. Поместить в очередь корень.
1. Взять из очереди очередную вершину. Поместить в очередь всех её сыновей слева направо (справа налево).
2. Если очередь пуста — конец.
Иначе на шаг 1.
№32 слайд
Содержание слайда: Пример
b
h i
i a j
a j k l
j k l
k l d e
l d e f g
d e f g
e f g
f g
g
№33 слайд
Содержание слайда: Представления деревьев
Левое скобочное представление Lrep(T):
1. Если a — корень T с поддеревьями T1, T2, …, Tn, корни которых — сыновья a, то
Lrep(T) = a(Lrep(T1), Lrep(T2), …, Lrep(Tn)).
2. Если у a сыновей нет, то Lrep(T) = a.
Правое скобочное представление Rrep(T):
1. Если a — корень T с поддеревьями T1, T2, …, Tn, корни которых — сыновья a, то
Rrep(T) = (Rrep(T1), Rrep(T2), …, Rrep(Tn))a.
2. Если у a сыновей нет, то Rrep(T) = a.
№34 слайд
Содержание слайда: Пример
Lrep(T) = b(h(a, j(d)), i(k(e, f, g), l))
Rrep(T) = ((a, (d)j)h, ((e, f, g)k, l)i)b
№35 слайд
Содержание слайда: Представления деревьев
Список прямых предков:
Составляется список прямых предков для вершин дерева с номерами 1, 2, …, n. Для корня полагаем, что предок имеет номер 0.
№36 слайд
Содержание слайда: Пример
0 1 2 2 4 1 6 6 7 7 7
№37 слайд
Содержание слайда: Дерево двоичного поиска
Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждая вершина v которого помечена элементом l(v)∈ S:
1. l(u) < l(v) для всех вершин u из левого поддерева вершины v.
2. l(u) > l(v) для всех вершин u из правого поддерева вершины v.
3. ∀a∈ S ∃!v: l(v) = a.
№38 слайд
Содержание слайда: Пример
№39 слайд
Содержание слайда: Просмотр дерева двоичного поиска
Вход: дерево T двоичного поиска для множества S, элемент a.
Выход: истина, если a∈ S, ложь — иначе.
Метод: Если T = ∅, то выдать ложь, иначе выдать ПОИСК(a, r), где r — корень дерева T.
функция ПОИСК(a, v)
{
если a = l(v) то выдать истина
иначе
если a < l(v) то
если v имеет левого сына w
то выдать ПОИСК(a, w)
иначе выдать ложь
иначе
если v имеет правого сына w
то выдать ПОИСК(a, w)
иначе выдать ложь
}
№40 слайд
Содержание слайда: Построение дерева двоичного поиска
Вход: последовательность слов произвольной длины.
Выход: введённые слова в лексикографическом порядке.
Метод: каждое слово при вводе помещается в вершину дерева двоичного поиска. По окончании ввода дерево обходится в инфиксном порядке и слова выводятся.
№41 слайд
Содержание слайда: Пример
orange
melon
apple
grape
plum
banana
Скачать все slide презентации Графы: деревья одним архивом:
