Деревья
<<  Деревья В гости к деревьям  >>
Деревья
Деревья
Что такое дерево
Что такое дерево
Применение деревьев
Применение деревьев
Свойства дерева
Свойства дерева
Свойства дерева
Свойства дерева
Типы деревьев
Типы деревьев
Кучи
Кучи
Двоичные деревья поиска
Двоичные деревья поиска
Двоичные деревья поиска
Двоичные деревья поиска
Использование деревьев в STL
Использование деревьев в STL
Использование двоичных деревьев поиска
Использование двоичных деревьев поиска
Использование двоичных деревьев поиска
Использование двоичных деревьев поиска
Множества
Множества
Множества
Множества
Множества
Множества
Карты
Карты
Карты
Карты
Карты
Карты
Очереди приоритета
Очереди приоритета
Очереди приоритета
Очереди приоритета

Презентация на тему: «Деревья». Автор: slon. Файл: «Деревья.ppt». Размер zip-архива: 192 КБ.

Деревья

содержание презентации «Деревья.ppt»
СлайдТекст
1 Деревья

Деревья

курс «Алгоритмы и структуры данных» Отделение Программной инженерии

2 Что такое дерево

Что такое дерево

Связный неориентированный граф, не имеющий циклов

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

3 Применение деревьев

Применение деревьев

Каталоги книжных интернет-магазинов представление файловых систем алгоритмы сжатия файлов реализации компиляторов

4 Свойства дерева

Свойства дерева

Дерево состоит из совокупности узлов только один узел не имеет предков: это корень дерева любой другой узел имеет только одного предка из любого узла можно попасть в корень, постоянно двигаясь от узла к его предку

5 Свойства дерева

Свойства дерева

Узлы, не имеющие потомков – листья высота дерева – это количество уровней в дереве, включая корень (то есть количество узлов в самой длинной цепочке от корня до листа)

6 Типы деревьев

Типы деревьев

Дерево общего вида (количество дочерних узлов для каждого узла не ограничено)

Бинарное дерево (количество дочерних узлов для каждого узла равно двум)

7 Кучи

Кучи

Это деревья, содержащие элементы либо в возрастающем,

Либо в убывающем порядке

8 Двоичные деревья поиска

Двоичные деревья поиска

Содержат элементы в отсортированном порядке, благодаря чему легко осуществляется поиск по дереву

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

9 Двоичные деревья поиска

Двоичные деревья поиска

Двоичное дерево поиска называется незавершенным, если один или несколько его узлов имеют один дочерний узел

10 Использование деревьев в STL

Использование деревьев в STL

11 Использование двоичных деревьев поиска

Использование двоичных деревьев поиска

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

12 Использование двоичных деревьев поиска

Использование двоичных деревьев поиска

template <class T> const T* const BSTree<T>::search_helper(BSTNode<T> *nodep, const T &x) { if (nodep == 0) { return NULL; } if (x == nodep->data) { return &(nodep->data); } if (x < nodep->data) { return search_helper(nodep->left, x); } else { return search_helper(nodep->right, x); } }

13 Множества

Множества

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

14 Множества

Множества

Объявление множества set<int> s1; set<int> s2; Добавление элементов в существующее множество for (int i = 0; i < 20; i++) { s1.insert(i); s2.insert(30 - i); }

15 Множества

Множества

Реализация функции поиска во множестве: if (s1.find(10) != s1.end()) { cout << "s1 contains 10\n"; } Функция возвращает итератор найденного элемента (если элемент не найден, то возвращается итератор конца множества)

16 Карты

Карты

Контейнер «карта» - это ассоциативная структура данных, которая хранит элементы по парам «ключ - значение». Структура называется ассоциативной, так как ставит в соответствие один элемент данных (ключ) другому элементу данных (значению). Ключ должен быть уникальным (то есть соответствовать только одному значению)

17 Карты

Карты

Объявление карты, имеющей строковый тип ключа и значения map<string, string> m1; Добавление элементов в карту m1.insert(pair<string, string>("apple", "a small red fruit")); m1.insert(pair<string, string>("orange", "a small orange fruit"));

18 Карты

Карты

Другой способ добавления элементов в карту m1[“apple”] = “a small red fruit”; m1[“banana”] = “a long yellow fruit”; Доступ к элементам по ключу в карте: cout << m1[“apple”] << endl; cout << m1[“banana”] << endl; Реализация итератора для просмотра элементов: map<string, string>::iterator it = m1.begin(); for ( ; it != m1.end(); it++) { cout << it->first << ": " << it->second << endl; }

19 Очереди приоритета

Очереди приоритета

Очереди приоритета похожи по поведению на обычные очереди. Очередь приоритета предоставляет доступ только к элементу с высшим приоритетом. Определение относительного приоритета элементов осуществляется при помощи оператора сравнения (<)

20 Очереди приоритета

Очереди приоритета

priority_queue<int> pq; pq.push(1); pq.push(4); pq.push(2); cout << pq.top() << endl; // outputs '4' pq.pop(); cout << pq.top() << endl; // outputs '2' pq.pop(); cout << pq.top() << endl; // outputs '1'

В некоторых типах (например, int) операция сравнения определена по умолчанию

Если операция сравнения не определена (например, для типа string), то программист определяет ее самостоятельно

«Деревья»
http://900igr.net/prezentacija/okruzhajuschij-mir/derevja-131278.html
cсылка на страницу
Урок

Окружающий мир

79 тем
Слайды