- •1. Абстрагирование типов
- •1.1. Понятие типа данных
- •1.1.1. Простые типы
- •1.1.2. Абстрактные типы
- •2. Идентификация объектов
- •2.1. Именование
- •2.2. Указание
- •2.2.1. Организация адресного пространства оперативной
- •2.2.2. Понятие указателя
- •2.2.3. Действия над указателями
- •2.2.4. Связывание идентификатора объекта с его
- •3. Время жизни объекта. Классы памяти
- •3.1. Понятие “времени жизни” объекта
- •3.2. Классы памяти
- •3.2.1. Статическая память
- •3.2.2. Автоматическая память
- •3.2.3. Динамическая память
- •4. Динамические структуры данных
- •4.1. Метод вычисляемого и хранимого адреса.
- •4.2. Понятие динамической структуры данных
- •4.3. Линейные динамические структуры данных (списки)
- •4.3.1. Основные виды списков
- •4.4. Односвязные списки
- •4.4.1. Включение узла в начало списка
- •4.4.2. Создание списка из n узлов за счет добавления
- •4.4.3. Создание списка из n узлов за счет добавления
- •4.4.4. Исключение узла из начала списка
- •4.4.5. Перестановка указателя
- •4.4.6. Поиск в списке узла по заданному условию
- •4.4.7. Включение нового узла в список за тем узлом, на
- •4.4.8. Исключение из списка узла за тем узлом, на
- •4.4.9. Исключение из списка узла, на который предварительно
- •4.4.10. Разрушение списка
- •4.4.11. Программный модуль, реализующий операции
- •4.5. Односвязные циклические списки
- •4.6. Двусвязные списки
- •4.6.1. Включение нового узла в список за тем узлом, на
- •4.6.2. Исключение из списка узла, на который
- •4.7. Ортогональные списки (мультисписки)
- •4.8. Разнородные списки
- •4.9. Управление динамической памятью
- •4.9.1. Администратор кучи
- •4.9.2. Алгоритмы выделения участков памяти по запросу
- •4.9.3. Фрагментация
- •4.9.4. Накопление мусора
- •4.9.5. Висящие ссылки
- •5. Множественная интерпретация объектов
- •5.1. Совместимость типов. Приведение и преобразование типов
- •5.2. Методы совмещения типов
- •5.2.1. Запись с вариантной частью
- •5.2.2. Использование директивы absolute
- •5.2.3. Параметры без типа
- •5.2.4. Открытые массивы
- •5.2.5. Наложение масок с помощью указателей
- •6. Рекурсивные структуры данных
- •6.1. Итерация и рекурсия в программировании
- •6.1.1. Понятие рекурсии
- •6.1.2. Итеративная и рекурсивная схема организации
- •6.2. Задача о “ханойских башнях”
- •6.3. Виды рекурсивных структур данных
- •6.3.1. Арифметические выражения
- •6.3.2. Динамические линейные структуры данных: списки
- •6.3.3. Иерархические линейные структуры данных: наборы
- •6.4. Эффективность рекурсивных вычислений
- •7. ИерархическиеНелинейные структуры данных.Деревья
- •7.1. Деревья общего вида
- •7.2. Бинарные деревья
- •7.3. Представление бинарных деревьев
- •7.3.1. Представление бинарных деревьев на статической
- •7.3.2. Представление бинарных деревьев на
- •7.4. Алгоритмы обхода бинарных деревьев
- •7.5. Виды бинарных деревьев
- •7.5.1. Сбалансированные деревья
- •7.5.2. Дихотомические деревья (деревья поиска)
- •7.5.3. Деревья выражений
- •7.6. Программный модуль, реализующий операции
- •Список рекомендуемой литературы
7.2. Бинарные деревья
Особенно важное практическое значение имеют упорядоченные деревья второй степени. Их называют двоичными или бинарными деревьями.
Бинарное дерево– это конечное множество узлов, которое или пусто, или состоит из корня и двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Примеры бинарных деревьев приведены на рис. 65.
Рис. 65. Примеры бинарных деревьев
Максимальное число узлов в бинарном дереве высотой h (d=2):
.
Максимальное число узлов на уровне i в бинарном дереве:
.
Высота полного бинарного дерева, содержащего Nузлов:
.
означает взятие целой части числа.
Существуют различные алгоритмы преобразования дерева произвольной степени, т.е. дерева общего вида, к виду бинарного. Левосторонний алгоритм формулируется следующим образом: у каждого узла дерева произвольной степени необходимо сохранить самую левую связь, а узлы – потомки одного и того же узла следует соединить правой связью. На рис. 66 представлено исходное дерево общего вида, а на рис. – эквивалентное бинарное.
Рис. 66. Преобразование произвольного дерева к виду бинарного
7.3. Представление бинарных деревьев
7.3.1. Представление бинарных деревьев на статической
памяти
Если известен максимальный размер дерева (т.е. высота, а следовательно, и количество узлов, соответствующих полному дереву), то структуру дерева можно хранить в виде массива. При этом корень дерева будет храниться в элементе массива с индексом [1]. Для каждого узла с номеромkего левый потомок будет хранится в элементе с индексом[2 * k], а правый - в элементе с индексом[2 * k + 1] (см. рис. 67).
Рис. 67. Представление бинарного дерева на статической памяти
Достоинством представления бинарных деревьев на статической памяти является простота доступа как от предка к потомку, так и от потомка к предку, а недостатком - то, что если дерево не является полным, в массиве появляется большое число пустых элементов. Ограниченный размер массива не позволяет включать в дерево новые узлы, т.е. дерево не может “расти”. Удаление узла из дерева и соответствующее изменение его структуры потребует модификации содержимого массива.
7.3.2. Представление бинарных деревьев на
динамической памяти
Элемент хранения узла бинарного дерева состоит из одного или нескольких информационных полей и двух полей связи, указывающих соответственно на левое и правое поддеревья данного узла.
Type |
|
PTree = ^ Tree; |
{ тип – указатель на узел дерева } |
Tree = record |
{ тип – элемент хранения узла дерева} |
info: char; |
{ информационное поле } |
left, right: PTree |
{ ссылки на поддеревья } |
End; |
|
Var Root: PTree; |
{ указатель на корень дерева } |
Дерево задается указателем на его корень. Если дерево пусто, указатель на его корень равен NIL. Связанное представление бинарного дерева иллюстрирует рис. 68.
Рис. 68. Связанное представление бинарного дерева