- •1.1. Элементарные данные
- •1.1.1. Данные числовых типов
- •1.1.1.1. Данные целочисленного типа
- •1.1.1.2. Данные вещественного типа
- •1.1.2. Данные символьного типа
- •1.1.3. Данные логического типа
- •1.1.4. Данные типа указатель
- •1.2. Линейные структуры данных
- •1.2.1. Массив
- •1.2.2. Строка
- •1.2.3. Запись
- •1.2.4. Множество
- •1.2.5. Таблица
- •1.2.6. Линейные списки
- •1.2.6.2. Линейный двунаправленный список
- •1.2.7. Циклические списки
- •1.2.8. Разреженные матрицы
- •1.2.9. Стек
- •1.2.10. Очередь
- •1.3. Нелинейные структуры данных
- •1.3.1. Мультисписки
- •1.3.2. Слоеные списки
- •1.3.3. Графы
- •1.3.3.1. Спецификация
- •1.3.3.2. Реализация
- •1.3.4. Деревья 1.3.4.1. Общие понятия
- •1.3.4.2. Обходы деревьев
- •1.3.4.3. Спецификация двоичных деревьев
- •1.3.4.4. Реализация
- •1.3.4.5. Основные операции
- •1.4. Файлы
- •1.4.1. Организация
- •1.4.2.2. Основные операции
- •1.4.2.3. Общая оценка b-деревьев
1.3.4. Деревья 1.3.4.1. Общие понятия
Дерево является одним из важных и интересных частных случаев графа, поэтому оно рассматривается отдельно от графов других видов. Деревом называется орграф, для которого:
существует узел, в который не входит ни одной дуги (корень);
в каждую вершину, кроме корня, входит одна дуга. Вершины дерева подразделяют на следующие три группы: – корень – вершина, в которую не входит ни одной дуги; – узлы – вершины, в которые входит одна дуга и выходит одна или
более дуг;
– листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.
Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина – предком. Корень не имеет предка, а листья не имеют потомков.
Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня и т. д.
Поддеревом называется вершина со всеми ее потомками.
55
Высотой поддерева будем считать максимальную длину цепи y1, …, yn его вершин такую, что yi+1 – потомок yi для всех i. Высота пустого дерева равна нулю, высота дерева из одного корня – единице.
Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень нуль.
По величине степени дерева часто различают два типа деревьев:
– двоичные – степень дерева не более двух;
– сильноветвящиеся – степень дерева произвольная.
Дерево произвольной степени (сильноветвящееся дерево) можно реа-лизовывать как любой граф (см. 1.3.3.2). Однако, учитывая специфику дерева как частного случая графа, можно рассмотреть отдельный способ реализации – как динамическую структуру в виде списка (рис. 14). Списочное представление деревьев произвольной степени основано на элементах, соответствующих вершинам дерева. Каждый элемент имеет поле данных и два поля указателей: указатель на начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня. При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева:
type PTree
ATTree;
Динамическая реализация
Указатель на дерево
|
|
d1 |
| |||||||
|
|
_^ |
| |||||||
|
' |
|
— |
| ||||||
|
nil |
| ||||||||
|
|
|
|
|
|
|
| |||
|
d2 |
|
d3 |
d4 |
|
d5 | ||||
|
|
|
|
nil |
nil |
_ | ||||
|
|
|
| |||||||
|
|
|
^ |
^ |
nil | |||||
|
|
"^ |
* |
|
* |
J | ||||
\ |
у |
|
|
|
|
|
|
| ||
d6 |
|
d7 |
|
d8 |
|
d5 | ||||
nil |
nil |
nil |
nil | |||||||
|
|
|
|
nil |
nil | |||||
|
|
|
|
|
56
Рис. 14. Дерево произвольной степени и его динамическая организация
TTree = record
Data: TypeElement; {поле данных}
Childs, Next: PTree; {указатели на потомков и на следующий} end;