Дерево это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами. - презентация

1

2 Дерево это связный ациклический граф. Связность означает наличие путей между любой парой вершин, ацикличность отсутствие циклов и то, что между парами вершинами имеется только по одному пути. Ориентированное (направленное) дерево -ориентированный граф, не содержащий циклов)

3 Дерево не имеет кратных рёбер и петель. Любое дерево с вершинами содержит ребро. Более того, конечный связный граф является деревом тогда и только тогда, когда, где число вершин, число рёбер графа. Граф является деревом тогда и только тогда, когда любые две различные его вершины можно соединить единственным элементарным путём. Любое дерево однозначно определяется расстояниями (длиной наименьшей цепи) между его концевыми (степени 1) вершинами. Для любых трёх вершин дерева, пути между парами этих вершин имеют ровно одну общую вершину.

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

5 Двоичное дерево поиска это двоичное дерево, для которого выполняются следующие дополнительные условия Свойства дерева поиска : Оба поддерева левое и правое, являются двоичными деревьями поиска. У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X. В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X. Для различных операций двоичное дерево поиска можно определить так: Двоичное дерево состоит из узлов (вершин) записей вида (data, left, right), где data некоторые данные привязанные к узлу, left и right ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент. Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё. Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] key[right[X]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого. Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

6 Есть три способа обхода: Прямой Поперечный Обратный

7 Префиксный (прямой) обход сначала обрабатывается текущий узел, затем левое и правое поддеревья; Префиксный обход: A, B, D, H, E, C, F, I, J, G

8 Инфиксный (симметричный) обход сначала обрабатывается левое поддерево текущего узла, затем корень, затем правое поддерево; инфиксный обход: D, H, B, E, A, I, F, J, C, G

9 Постфиксный (обратный) обход сначала обрабатываются левое и правое поддеревья текущего узла, затем сам узел. постфиксный обход: H, D, E, B, I, J, F, G, C, A

10 1. Двоичная куча, пирамида, или сортирующее дерево такое двоичное дерево, для которого выполнены три условия: 2. Значение в любой вершине не меньше, чем значения её потомков. 3. Глубина листьев (расстояние до корня) отличается не более чем на 1 слой. 4. Последний слой заполняется слева направо. 5. Также двоичная куча просто реализуемая структура данных, позволяющая быстро (за логарифмическое время) добавлять элементы и извлекать элемент с максимальным приоритетом (например, максимальный по значению).

11 class Heap { int[] data; // массив с элементами (индексация с 1, 0 - фиктивная вершина) int pnt = 0; // указаетель на последний элемент /* Конструктор */ Heap(int size) { data = new int [size + 1]; } /* Добавить элемент */ void add(int x) { data[++pnt] = x; for (int v = pnt, p = v >> 1; p > 0 && data[p] > data[v]; swap(data, p, v), v = p, p >>= 1); } /* Извлечь минимум */ int extractMin() { int ret = data[1]; swap(data, 1, pnt--); for (int v = 1; (v