Binary Tree. Проблема поиска значений - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Binary Tree. Проблема поиска значений, слайд №1

Binary Tree. Проблема поиска значений, слайд №2

Binary Tree. Проблема поиска значений, слайд №3

Binary Tree. Проблема поиска значений, слайд №4

Binary Tree. Проблема поиска значений, слайд №5

Binary Tree. Проблема поиска значений, слайд №6

Binary Tree. Проблема поиска значений, слайд №7

Binary Tree. Проблема поиска значений, слайд №8

Binary Tree. Проблема поиска значений, слайд №9

Binary Tree. Проблема поиска значений, слайд №10

Binary Tree. Проблема поиска значений, слайд №11

Binary Tree. Проблема поиска значений, слайд №12

Binary Tree. Проблема поиска значений, слайд №13

Binary Tree. Проблема поиска значений, слайд №14

Binary Tree. Проблема поиска значений, слайд №15

Binary Tree. Проблема поиска значений, слайд №16

Binary Tree. Проблема поиска значений, слайд №17

Binary Tree. Проблема поиска значений, слайд №18

Binary Tree. Проблема поиска значений, слайд №19

Binary Tree. Проблема поиска значений, слайд №20

Содержание ▲

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

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

Слайд 1

Описание слайда:

Binary Tree

Слайд 2

Описание слайда:

Проблема поиска значений Коллекции (вроде массивов и списков) позволяют хранить данные, а также добавлять новые, удалять более ненужные, или редактировать уже существующие элементы. Однако, кроме всего этого, часто необходимо найти определённое значение в коллекции – и делается это, например, при помощи линейного либо бинарного поиска.

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Решение проблемы поиска Если данных достаточно много, и приоритетной задачей является поиск значений, тогда динамической структурой для хранения этих данных следует избрать дерево. Кроме того, почти так же, как и в списках, в деревьях эффективно реализуются добавление и удаление элементов.

Слайд 5

Описание слайда:

Строим дерево!

Слайд 6

Описание слайда:

Определение понятия Дерево – это нелинейная структурированная совокупность элементов. Элементы данных в общем случае называются узлами (node).

Слайд 7

Описание слайда:

Виды деревьев Сбалансированные деревья K-мерные деревья R-дерево Кучи Изящный граф-звезда Двоичное (бинарное) дерево Красно-чёрное дерево Октодерево Танцующее дерево и др.

Слайд 8

Описание слайда:

Схематичное изображение

Слайд 9

Описание слайда:

Бинарное дерево Бинарное дерево – это частный случай дерева, в котором каждый узел имеет не более двух потомков (т.е. каждый узел может иметь 2, 1 или 0 потомков). Узел, не имеющий потомков, называется листом (leaf). Узел является родительским для своих потомков и дочерним для своего предка.

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Строение одного узла дерева

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Рекурсия передаёт привет  Бинарное дерево является рекурсивной структурой, поскольку каждое его поддерево само по себе является бинарным деревом, и, следовательно, каждый его узел в свою очередь является корнем самостоятельного дерева. Поэтому, при работе с деревьями обычно используются рекурсивные алгоритмы.

Слайд 14

Описание слайда:

Слайд 15

Описание слайда:

Основные операции Поиск элемента Добавление элемента Распечатка данных Изменение значения элемента Удаление элемента Подсчёт количества элементов Очистка дерева

Слайд 16

Описание слайда:

Класс элемента дерева class Node { // inner class! private int value; private Node parent; private Node right; private Node left; public int getValue() { return value; } }

Слайд 17

Описание слайда:

Распечатка дерева private void showTree(Node elem) { if (elem != null) { showTree(elem.left); System.out.print(elem.getValue()); showTree(elem.right); } }

Слайд 18

Описание слайда:

Подсчёт количества элементов private int getCount(Node elem, int count) { if (elem != null) { count = getCount(elem.left, count); count++; count = getCount(elem.right, count); } return count; }

Слайд 19

Описание слайда:

Ключ – значение На практике, элементы деревьев чаще всего хранят не просто одно лишь значение, а пару «ключ - значение». В качестве ключа обычно выступает целое число или строка, в то время как значением может быть список, любая другая коллекция, или объект пользовательского типа.