Составители:
56
Высотой поддерева будем считать максимальную длину цепи y
1
, …,
y
n
его вершин такую, что y
i+1
– потомок y
i
для всех i. Высота пустого
дерева равна нулю, высота дерева из одного корня – единице.
Степенью вершины в дереве называется количество дуг, которое из
нее выходит. Степень дерева равна максимальной степени вершины,
входящей в дерево. При этом листьями в дереве являются вершины,
имеющие степень нуль.
По величине степени дерева часто различают два типа деревьев:
– двоичные – степень дерева не более двух;
– сильноветвящиеся – степень дерева произвольная.
Дерево произвольной степени (сильноветвящееся дерево) можно реа-
лизовывать как любой граф (см. 1.3.3.2). Однако, учитывая специфику де-
рева как частного случая графа, можно рассмотреть отдельный способ реа-
лизации – как динамическую структуру в виде списка (рис. 14). Списоч-
ное представление деревьев произвольной степени основано на элемен-
тах, соответствующих вершинам дерева. Каждый элемент имеет поле дан-
ных и два поля указателей: указатель на начало списка потомков вершины
и указатель на следующий элемент в списке потомков текущего уровня.
При таком способе представления дерева обязательно следует сохранять
указатель на вершину, являющуюся корнем дерева:
type
PTree = ^TTree;
d4 d5d3
d1
d2
d6
Указатель на дерево
Сильноветвящееся дерево
Динамическая
реализация
d1
nil
d7 d8
d2 d3
nil
d4
nil
d5
nil
d6
nil
d7
nil
d8
nil
nil
d5
d5
nil
nil
Рис. 14. Дерево произвольной степени и его динамическая организация
Страницы
- « первая
- ‹ предыдущая
- …
- 54
- 55
- 56
- 57
- 58
- …
- следующая ›
- последняя »
