- •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.4. Алгоритмы обхода бинарных деревьев
Наиболее типичная операция, выполняемая над бинарными деревьями – обход дерева. Обход– это процедура, при выполнении которой каждый узел обрабатывается ровно один раз некоторым единым образом. Обход дерева заключается в разбиении дерева на корень, левое и правое поддеревья и применении к каждому из поддеревьев соответствующей процедуры обработки до тех пор, пока в процессе разбиения не будет получено пустое дерево.
Полный обход дерева дает линейную расстановку узлов, что облегчает выполнение многих алгоритмов. Существует три принципа упорядочения, которые естественно вытекают из структуры дерева. Как и саму древовидную структуру, их удобно выразить с помощью рекурсии. Им соответсвуют три левосторонних алгоритма обхода.
Нисходящий (прямой) обходвыполняется по формуле“корень-левый-правый” (К-Л-П).
обработать корневой узел;
обойти левое поддерево в нисходящем порядке;
обойти правое поддерево в нисходящем порядке.
Трасса нисходящего обхода дерева рис. 68: A B C D E F.
Восходящий (концевой) обходвыполняется по формуле“левый-правый-корень” (Л-П-К).
обойти левое поддерево в восходящем порядке;
обойти правое поддерево в восходящем порядке;
обработать корневой узел.
Трасса восходящего обхода дерева рис. 68 C D B F E A .
Смешанный (обратный) обходвыполняется по формуле“левый—корень-правый” (Л-К-П).
обойти левое поддерево в смешанном порядке;
обработать корневой узел;
обойти правое поддерево в смешанном порядке.
Трасса смешанного обхода дерева рис. 68: С B D A E F .
Заметим, что при различных алгоритмах обхода порядок обработки терминальных узлов не изменяется (содержимое терминальных узлов в трассах обхода выделено жирным шрифтом).
Ниже приведена процедура, распечатывающая трассу нисходящего обхода бинарного дерева – последовательность информационных полей узлов дерева.
|
Procedure KLP( root: PTree ); |
{ root – указатель на корень дерева } | ||||
|
begin |
| ||||
|
if root <> nil then begin |
{ дерево не пусто? } | ||||
|
writeln( root^.info ); |
{ распечатать информ. поле корневого узла } | ||||
|
KLP( root^.left ); |
{ обойти левое поддерево в нисходящем порядке } | ||||
|
(* 1 *) KLP( root^.right ) |
{ обойти правое поддерево в нисходящем порядке } | ||||
|
(* 2 *) end; |
| ||||
|
(* 3 *) end; |
| ||||
Таблица 4. Трасса состояний стека при работе процедуры нисходящего обхода бинарного дерева
|
Номер входа в процедуру |
Номер уровня рекур- сии |
Значение фактичес-кого параметра |
Стек |
Выход-ная трасса |
Выход из уровня | |
|
Исходное состояние |
Конечное состояние | |||||
|
1 |
1 |
^A |
(-,-) |
(^A, *1*) |
A |
|
|
2 |
2 |
^B |
(^A, *1*) |
(^B, *1*) (^A, *1*) |
B |
|
|
3 |
3 |
^C |
(^B, *1*) (^A, *1*) |
(^C, *1*) (^B, *1*) (^A, *1*) |
C |
|
|
4 |
4 |
NIL |
(^C, *1*) (^B, *1*) (^A, *1*) |
(NIL,*1*) (^C, *1*) (^B, *1*) (^A,*1*) |
|
|
|
4 |
NIL |
(NIL,*1*) (^C, *1*) (^B, *1*) (^A,*1*) |
(^C, *1*) (^B, *1*) (^A, *1*) |
|
(*3*) | |
|
3 |
^C |
(^C, *1*) (^B, *1*) (^A, *1*) |
(^C, *2*) (^B, *1*) (^A, *1*) |
|
| |
|
5 |
4 |
NIL |
(^C, *2*) (^B, *1*) (^A, *1*) |
(NIL,*2*) (^C, *2*) (^B, *1*) (^A, *1*) |
|
|
|
4 |
NIL |
(NIL,*2*) (^C, *2*) (^B, *1*) (^A, *1*) |
(^C, *2*) (^B, *1*) (^A, *1*) |
|
(*3*) | |
|
3 |
^C |
(^C, *2*) (^B, *1*) (^A,*1*) |
(^B, *1*) (^A, *1*) |
|
(*3*) | |
|
2 |
^B |
(^B, *1*) (^A,*1*) |
(^B, *2*) (^A, *1*) |
|
| |
|
6 |
3 |
^D |
(^B,*2*) (^A,*1*) |
(^D, *1*) (^B, *2*) (^A, *1*) |
D |
|
|
7 |
4 |
NIL |
(^D, *1*) (^B, *2*) (^A, *1*) |
(NIL,*1*) (^D, *1*) (^B, *2*) (^A, *1*) |
|
|
|
4 |
NIL |
(NIL,*1*) (^D, *1*) (^B, *2*) (^A, *1*) |
(^D, *1*) (^B, *2*) (^A, *1*) |
|
(*3*) | |
|
3 |
^D |
(^D, *1*) (^B, *2*) (^A, *1*) |
(^D, *2*) (^B, *2*) (^A, *1*) |
|
| |
|
8 |
4 |
NIL |
(^D, *2*) (^B, *2*) (^A, *1*) |
(NIL,*2*) (^D, *2*) (^B, *2*) (^A, *1*) |
|
|
|
4 |
NIL |
(NIL,*2*) (^D, *2*) (^B, *2*) (^A, *1*) |
(^D, *2*) (^B, *2*) (^A, *1*) |
|
(*3*) | |
|
3 |
^D |
(^D, *2*) (^B, *2*) (^A, *1*) |
(^B, *2*) (^A, *1*) |
|
(*3*) | |
|
2 |
^B |
(^B, *2*) (^A, *1*) |
(^A, *1*) |
|
(*3*) | |
|
1 |
^A |
(^A, *1*) |
(^A, *2*) |
|
| |
|
9 |
2 |
^E |
(^A, *2*) |
(^E, *1*) (^A, *2*) |
E |
|
|
10 |
3 |
NIL |
(^E, *1*) (^A, *2*) |
(NIL,*1*) (^E, *1*) (^A, *2*) |
|
|
|
3 |
NIL |
(NIL,*1*) (^E, *1*) (^A, *2*) |
(^E, *1*) (^A, *2*) |
|
(*3*) | |
|
2 |
^E |
(^E, *1*) (^A, *2*) |
(^E, *2*) (^A, *2*) |
|
| |
|
|
|
|
|
|
|
|
|
Номер входа в процедуру |
Номер уровня рекур- сии |
Значение фактичес-кого параметра |
Исходное состояние стека |
Конечное состояние стека |
Выход-ная трасса |
Выход из уровня |
|
11 |
3 |
^F |
(^E, *2*) (^A, *2*) |
(^F, *1*) (^E, *2*) (^A, *2*) |
F |
|
|
12 |
4 |
NIL |
(^F, *1*) (^E, *2*) (^A, *2*) |
(NIL, *1*) (^F, *1*) (^E, *2*) (^A, *2*) |
|
|
|
4 |
NIL |
(NIL, *1*) (^F, *1*) (^E, *2*) (^A, *2*) |
(^F, *1*) (^E, *2*) (^A, *2*) |
|
(*3*) | |
|
3 |
^F |
(^E, *2*) (^A, *2*) |
(^F, *2*) (^E, *2*) (^A, *1*) |
|
| |
|
13 |
4 |
NIL |
(^F, *2*) (^E, *2*) (^A, *2*) |
(NIL, *2*) (^F, *2*) (^E, *2*) (^A, *2*) |
|
|
|
4 |
NIL |
(NIL, *2*) (^F, *2*) (^E, *2*) (^A, *2*) |
(^F, *2*) (^E, *2*) (^A, *2*) |
|
(*3*) | |
|
3 |
^F |
(^F, *2*) (^E, *2*) (^A, *2*) |
(^E, *2*) (^A, *2*) |
|
(*3*) | |
|
2 |
^E |
(^E, *2*) (^A, *2*) |
(^A, *2*) |
|
(*3*) | |
|
1 |
^A |
(^A, *2*) |
(-, -) |
|
(*3*) | |
Для иллюстрации работы этой процедуры и построения трассы состояний стека будем использовать следующие обозначения:
^A– адрес узла дерева, в информационном поле которого хранится символ“A”;
(* 1 *) и (* 2 *) – адреса возврата из уровня рекурсивной процедуры, номер которой на 1 больше текущего;
(* 3 *) – адрес возврата из рекурсивной процедуры текущего уровня.
Трасса нисходящего обхода дерева, приведенного на рис. 68, содержится в таблице 4.