🗊Презентация Бинарные деревья

Категория: Устройства и комплектующие
Нажмите для полного просмотра!
Бинарные деревья, слайд №1Бинарные деревья, слайд №2Бинарные деревья, слайд №3Бинарные деревья, слайд №4Бинарные деревья, слайд №5Бинарные деревья, слайд №6Бинарные деревья, слайд №7Бинарные деревья, слайд №8Бинарные деревья, слайд №9Бинарные деревья, слайд №10Бинарные деревья, слайд №11Бинарные деревья, слайд №12Бинарные деревья, слайд №13Бинарные деревья, слайд №14Бинарные деревья, слайд №15Бинарные деревья, слайд №16Бинарные деревья, слайд №17Бинарные деревья, слайд №18Бинарные деревья, слайд №19Бинарные деревья, слайд №20Бинарные деревья, слайд №21
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Бинарные деревья. Доклад-сообщение содержит 21 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Основы С# Лекция 7 Бинарные деревья
Описание слайда:
Основы С# Лекция 7 Бинарные деревья

Слайд 2


Бинарное дерево
Описание слайда:
Бинарное дерево

Слайд 3


Понятие бинарного дерева Эта динамическая структура данных состоит из узлов (вершин), каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья (поддеревья, ветви). На каждый узел (вершину) имеется ровно одна ссылка. Начальный узел (вершина) называется корнем дерева. Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом
Описание слайда:
Понятие бинарного дерева Эта динамическая структура данных состоит из узлов (вершин), каждый из которых содержит, кроме данных, не более двух ссылок на различные бинарные деревья (поддеревья, ветви). На каждый узел (вершину) имеется ровно одна ссылка. Начальный узел (вершина) называется корнем дерева. Дерево является рекурсивной структурой данных, поскольку каждое поддерево также является деревом

Слайд 4


Терминология Узел(вершина) дерева – каждый элемент дерева. Корень дерева- начальный узел. Ветви дерева – вершины дерева соединенные направленными дугами Лист – вершина, не имеющий поддеревьев. Предок – исходящий узел. Потомок – входящий узел. Высота дерева – количество уровней(слоев), на которых располагаются вершины. Поддерево – часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Степень вершины – количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево Уровень вершины – это количество дуг от корня дерева до вершины.
Описание слайда:
Терминология Узел(вершина) дерева – каждый элемент дерева. Корень дерева- начальный узел. Ветви дерева – вершины дерева соединенные направленными дугами Лист – вершина, не имеющий поддеревьев. Предок – исходящий узел. Потомок – входящий узел. Высота дерева – количество уровней(слоев), на которых располагаются вершины. Поддерево – часть древообразной структуры данных, которая может быть представлена в виде отдельного дерева. Степень вершины – количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево Уровень вершины – это количество дуг от корня дерева до вершины.

Слайд 5


Терминология Бинарное (двоичное) дерево – это дерево, в котором каждая вершина имеет не более двух потомков. Неполное бинарное дерево – это дерево, уровни которого заполнены не полностью. Полное бинарное дерево – это дерево, которое содержит только полностью заполненные уровни. Почти сбалансированное дерево – это дерево, у которого длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Строгое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев) или два (у узлов).
Описание слайда:
Терминология Бинарное (двоичное) дерево – это дерево, в котором каждая вершина имеет не более двух потомков. Неполное бинарное дерево – это дерево, уровни которого заполнены не полностью. Полное бинарное дерево – это дерево, которое содержит только полностью заполненные уровни. Почти сбалансированное дерево – это дерево, у которого длины всевозможных путей от корня к внешним вершинам отличаются не более, чем на единицу. Строгое бинарное дерево – это дерево, у которого вершины имеют степень ноль (у листьев) или два (у узлов).

Слайд 6


Бинарное упорядоченное дерево
Описание слайда:
Бинарное упорядоченное дерево

Слайд 7


Бинарное упорядоченное дерево (дерево поиска) Если дерево организовано таким образом, что для каждого узла все ключи его правого поддерева больше ключа этого узла, а все ключи его левого поддерева – меньше, то такое дерево называется упорядоченным, или деревом поиска. Одинаковые ключи не допускаются.
Описание слайда:
Бинарное упорядоченное дерево (дерево поиска) Если дерево организовано таким образом, что для каждого узла все ключи его правого поддерева больше ключа этого узла, а все ключи его левого поддерева – меньше, то такое дерево называется упорядоченным, или деревом поиска. Одинаковые ключи не допускаются.

Слайд 8


Пример построение дерева поиска Бинарное упорядоченное дерево по приходящим числам: 17, 18, 6, 5, 9, 23, 12, 7, 8.
Описание слайда:
Пример построение дерева поиска Бинарное упорядоченное дерево по приходящим числам: 17, 18, 6, 5, 9, 23, 12, 7, 8.

Слайд 9


Идеально сбалансированное дерево
Описание слайда:
Идеально сбалансированное дерево

Слайд 10


Идеально сбалансированное дерево Идеально сбалансированным дерево - это дерево, в котором число узлов (вершин) в левом и правом поддеревьях отличается не более чем на единицу.
Описание слайда:
Идеально сбалансированное дерево Идеально сбалансированным дерево - это дерево, в котором число узлов (вершин) в левом и правом поддеревьях отличается не более чем на единицу.

Слайд 11


Идеально сбалансированное дерево Алгоритм равномерного распределения для известного числа вершин формулируют, используя рекурсию. 1. Взять одну вершину в качестве корня. 2. Построить тем же способом левое поддерево с nl=n/2 вершинами. 3. Построить тем же способом правое поддерево с nr=n-nl-1 вершинами.
Описание слайда:
Идеально сбалансированное дерево Алгоритм равномерного распределения для известного числа вершин формулируют, используя рекурсию. 1. Взять одну вершину в качестве корня. 2. Построить тем же способом левое поддерево с nl=n/2 вершинами. 3. Построить тем же способом правое поддерево с nr=n-nl-1 вершинами.

Слайд 12


Идеально сбалансированное дерево
Описание слайда:
Идеально сбалансированное дерево

Слайд 13


Операции с бинарным упорядоченным деревом 1.Удаление узла из дерева
Описание слайда:
Операции с бинарным упорядоченным деревом 1.Удаление узла из дерева

Слайд 14


Исключаемый узел – лист. Действия: Удалить ссылку на данный узел.
Описание слайда:
Исключаемый узел – лист. Действия: Удалить ссылку на данный узел.

Слайд 15


Из исключаемого узла выходит одна ветвь. Действия: переназначить указатель (пунктир).
Описание слайда:
Из исключаемого узла выходит одна ветвь. Действия: переназначить указатель (пунктир).

Слайд 16


Из исключаемого узла выходят две ветви Действия: на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева.
Описание слайда:
Из исключаемого узла выходят две ветви Действия: на место удаляемого узла надо поставить либо самый правый узел левой ветви, либо самый левый узел правой ветви для сохранения упорядоченности дерева.

Слайд 17


Операции с бинарным упорядоченным деревом 2. Обход (просмотр) дерева
Описание слайда:
Операции с бинарным упорядоченным деревом 2. Обход (просмотр) дерева

Слайд 18


Обходы (просмотры) дерева Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.
Описание слайда:
Обходы (просмотры) дерева Обход дерева – это упорядоченная последовательность вершин дерева, в которой каждая вершина встречается только один раз.

Слайд 19


Способы обхода (просмотра) дерева а) Просмотр слева-направо: ARB (левое поддерево-корень-правое поддерево). б) Просмотр сверху-вниз: RAB (корень до поддеревьев). в) Просмотр снизу-вверх: ABR (корень после поддеревьев). г) Просмотр справа-налево: BRA (правое поддерево-корень-левое поддерево).
Описание слайда:
Способы обхода (просмотра) дерева а) Просмотр слева-направо: ARB (левое поддерево-корень-правое поддерево). б) Просмотр сверху-вниз: RAB (корень до поддеревьев). в) Просмотр снизу-вверх: ABR (корень после поддеревьев). г) Просмотр справа-налево: BRA (правое поддерево-корень-левое поддерево).

Слайд 20


Пример обхода дерева а) ARB: - инфиксная запись. б) RAB: - префиксная запись. в) ABR: - постфиксная запись.
Описание слайда:
Пример обхода дерева а) ARB: - инфиксная запись. б) RAB: - префиксная запись. в) ABR: - постфиксная запись.

Слайд 21


Пример обхода дерева а) ARB: - 5, 6, 8, 9, 11, 12, 17, 18, 23. б) BRA - 23, 18, 17, 12, 11, 9, 8, 7, 6, 5.
Описание слайда:
Пример обхода дерева а) ARB: - 5, 6, 8, 9, 11, 12, 17, 18, 23. б) BRA - 23, 18, 17, 12, 11, 9, 8, 7, 6, 5.

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию