Презентация Деревья. Лекция 11, 12 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Деревья. Лекция 11, 12 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 36 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Деревья. Лекция 11, 12
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:36 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:340.27 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
![Дерево Ориентированным](/documents_6/9548b88d574821e2d7206be06ffa0b07/img2.jpg)
Содержание слайда: Дерево
Ориентированным деревом Т называется ориентированный граф G = (А,R) со специальной вершиной r А, называемой корнем, у которого
степень по входу вершины r равна 0,
степень по входу всех остальных вершин равна 1,
каждая вершина аА достижима из r.
Базовые свойства деревьев
Дерево не содержит циклов
Каждая вершина дерева соединяется с его корнем единственным путём
№5 слайд
![Высота дерева Пусть Т A, R](/documents_6/9548b88d574821e2d7206be06ffa0b07/img4.jpg)
Содержание слайда: Высота дерева
Пусть Т=(A, R) – дерево, (a, b) R, тогда
a – отец b, а b – сын a.
Глубина или уровень вершины – длина пути от корня до этой вершины.
Высота вершины – длина максимального пути от этой вершины до листа.
Высота дерева – длина максимального пути от корня до листа.
Глубина корня = 0.
№9 слайд
![Обходы в глубину Пусть T](/documents_6/9548b88d574821e2d7206be06ffa0b07/img8.jpg)
Содержание слайда: Обходы в глубину
Пусть T – дерево, r - корень, v1, v2, …, vn – сыновья вершины r
Прямой (префиксный) обход
Пронумеровать (посетить) корень r
Пронумеровать в прямом порядке поддеревья с корнями v1, v2,…, vn
Обратный (постфиксный) обход
Пронумеровать в обратном порядке поддеревья с корнями v1, v2,…, vn
Пронумеровать корень r
Внутренний ( инфиксный) обход для бинарных деревьев
Пронумеровать во внутреннем порядке левое поддерево корня r (если существует)
Пронумеровать корень r
Пронумеровать во внутреннем порядке правое поддерево корня r (если существует)
№12 слайд
![Обход деревьев в ширину Обход](/documents_6/9548b88d574821e2d7206be06ffa0b07/img11.jpg)
Содержание слайда: Обход деревьев в ширину
Обход вершин дерева по уровням от корня слева направо (или справа налево)
Алгоритм обхода дерева в ширину
Шаг 0:
Поместить в очередь корень дерева
Шаг 1:
Взять из очереди очередную вершину
Поместить в очередь всех ее сыновей по порядку
слева направо (справа налево)
Шаг 2:
Если очередь пуста, то конец обхода, иначе перейти на Шаг 1
№14 слайд
![Бинарное дерево -- операции](/documents_6/9548b88d574821e2d7206be06ffa0b07/img13.jpg)
Содержание слайда: Бинарное дерево -- операции
T -- данные
tree_t -- двоичное дерево с данными Т
place_t -- ячейка дерева
tree_t create (); place_t left (place_t t);
void insert (tree_t *t, T val); place_t right (place_t t);
void erase (tree_t *t, T val); T getval (place_t t);
place_t find (tree_t t, T val); void setval (place_t t, T val);
void destroy (tree_t *t); place_t end ();
№15 слайд
![Представление бинарных](/documents_6/9548b88d574821e2d7206be06ffa0b07/img14.jpg)
Содержание слайда: Представление бинарных деревьев с помощью указателей
struсt place_t {
T data; // данные
struct place_t *left; // левое п/дерево
struct place_t *right; // правое п/дерево
};
struct tree_t {
struct place_t *root;
};
typedef struct tree_t tree_t;
typedef struct place_t * place_t;
№18 слайд
![Скобочное представление](/documents_6/9548b88d574821e2d7206be06ffa0b07/img17.jpg)
Содержание слайда: Скобочное представление деревьев
Левое и правое скобочные представления Lrep(Т) и Rrep(Т) дерева Т строятся по следующим рекурсивным правилам
Если корнем дерева Т служит вершина а, не имеющая прямых потомков, то
Lrep (Т) = Rrep(T) = а
Если корнем дерева Т служит вершина а с поддеревьями T1, Т2, . . ., Тn, расположенными в этом порядке (их корни — прямые потомки вершины а), то
Lrep(Т) = а(Lrep (T1), Lrep (Т2) , . . ., Lrep (Тn))
Rrep(Т) = (Rrep(Т1), Rrep(T2), . . ., Rrep (Тn))а
№20 слайд
![Пример печати левого](/documents_6/9548b88d574821e2d7206be06ffa0b07/img19.jpg)
Содержание слайда: Пример печати левого скобочного представления двоичного дерева
void print_Lrep (tree_t t)
{
print_Lrep_body (t.root);
}
void print_Lrep_body (place_t t)
{
if (t == end()) return;
printf ("%d(", getval(t));
print_Lrep_body (left(t));
print_Lrep_body (right(t));
printf (")");
}
№22 слайд
![Дерево двоичного поиска](/documents_6/9548b88d574821e2d7206be06ffa0b07/img21.jpg)
Содержание слайда: Дерево двоичного поиска
Деревом двоичного поиска для множества S называется помеченное двоичное дерево, каждый узел v которого помечен элементом l(v)S так, что
l(u) < l(v) для каждого узла u из левого поддерева узла v,
l(w) > l(v) для каждого узла w из правого поддерева узла v,
для любого элемента a S существует единственный узел v , такой что l(v) = a.
№24 слайд
![Поиск в дереве двоичного](/documents_6/9548b88d574821e2d7206be06ffa0b07/img23.jpg)
Содержание слайда: Поиск в дереве двоичного поиска
Вход
Дерево Д двоичного поиска для множества S, элемент a.
Выход
истина, если aS
ложь иначе
логическая функция ПОИСК (a, Lrep(Д))
{
если Lrep(Д) == x, то вернуть I(x) == a;
иначе
Lrep(Д) = x(Л, П);
если а == I(х), то вернуть истина;
иначе если a < I(x), то вернуть ПОИСК(а, Л);
иначе вернуть ПОИСК(а, П);
всё;
всё;
}
№26 слайд
![Сбалансированные деревья АВЛ](/documents_6/9548b88d574821e2d7206be06ffa0b07/img25.jpg)
Содержание слайда: Сбалансированные деревья АВЛ
Время вставки вершины в дерево двоичного поиска, содержащее n вершин
O(log2n) в лучшем случае для полных деревьев
O(n) в худшем случае для вырожденных деревьев, имеющих структуру списка
Можно устранить вырождение дерева в список и сократить время вставки вершины с O(n) до O(log2n) даже в худшем случае
Дерево двоичного поиска сбалансировано, если высоты поддеревьев каждой из его вершин отличаются не более, чем на единицу
№31 слайд
![Оптимизация вставки в](/documents_6/9548b88d574821e2d7206be06ffa0b07/img30.jpg)
Содержание слайда: Оптимизация вставки в АВЛ-дерево
Для балансировки достаточно хранить разность высот левого и правого поддеревьев
-1: Высота левого поддерева на 1 больше высоты правого поддерева
0: Высоты поддеревьев одинаковы
+1: Высота правого поддерева на 1 больше высоты левого поддерева
Скачать все slide презентации Деревья. Лекция 11, 12 одним архивом:
Похожие презентации
-
Многопоточное программирование (Лекция 1). Стандарты C, контейнеры C, красно-черные деревья, B-деревья
-
Алгоритмы и структуры данных. Лекция 7. Сбалансированные деревья. АВЛ-деревья
-
Проектирование высоко-нагруженных систем. Лекция 3
-
Методы улучшения алгоритмов сортировок. Лекция 7
-
Пирамидальная сортировка. Лекция 8
-
Классификация структур данных. Лекция 2
-
Базовые типы данных языков программирования высокого уровня. Лекция 3
-
Проектирование высоконагруженных систем. Лекция 2
-
Техники тест-дизайна. Планирование, оценка трудозатрат. Отчетность. Лекция 5
-
Операции и выражения. (Лекция 4)