Деревья можно представлять с помощью связных списков и масси-
вов (или последовательных списков).
Чаще всего используется связное представление деревьев, т.к.
оно очень сильно напоминает логическое. Связное хранение состоит
в том, что задается связь от отца к сыновьям. В бинарном дереве
имеется два указателя, поэтому удобно узел представить в виде
структуры:
┌──────┬──────┬──────┐ где LPTR - указатель на левое поддерево,
│ LPTR │ DATA │ RPTR │ RPTR - указатель на правое поддерево,
└──────┴──────┴──────┘ DATA - содержит информацию, связанную
с вершиной.
Рассмотрим машинное представление бинарного дерева, изобра-
женного на рис. 6.20.
┌─┬───┬─┐
┌───┼ │ A │ ┼───┐
│ └─┴───┴─┘ │
(A) ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐
/ ┌─┼ │ b │ │ ┌────┼ │ c │ ┼───┐
(b) (c) │ └─┴───┴─┘ │ └─┴───┴─┘ │
/ / ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐ ┌─┬─┴─┬─┐
(d) (e) (g) │ │ d │ │ │ │ e │ ┼──┐ │ │ g │ │
└─┴───┴─┘ └─┴───┴─┘ │ └─┴───┴─┘
(f) ┌─┬─┴─┬─┐
│ │ f │ │
Рис. 6.20. Логическое └─┴───┴─┘
представление дерева Рис. 6.21. Машинное связное представление
дерева представленного на рис.6.20
Рассмотрим последовательное представление деревьев. Оно
удобно и эффективно в случае, если древовидная структура в тече-
ние времени своего существования не подвергается значительным из-
менениям, за счет включения вершин, удаления вершин и т.д.
Выбор метода последовательного представления деревьев опре-
деляется также набором тех операций, которые должны быть выполне-
ны над древовидными структурами. (Пример статистической древовид-
ной структуры - пирамидальный метод сортировки). Простейший метод
представления дерева в виде последовательной структуры заключает-
ся во введении вектора FATHER, задающего отбор для всех его вер-
шин. Этот метод можно использовать также для представления леса.
Недостаток метода - он не отображает упорядочения вершин дерева.
Если в предыдущем примере поменять местами вершины 9 и 10, после-
довательное представление останется тем же.
a) (1) б) (1)
/ │ │
(2) (3) (4) (2)─(3)───────(4)
/ / / │ │ │
(5) (6) (7)(9) (10) (5) (6)─(7) (9)─(10)
│
(8) (8)
Рис. 6.21. Диаграммы дерева: а) исходное
б) перестройка в бинарное
Последовательное представление дерева, логическая диаграмма
которого дана на рис. 6.21 , задается следующим образом:
i 1 2 3 4 5 6 7 8 9 10
FATHER [i] 0 1 1 1 2 3 3 7 4 4 ,
где ветви определяются как {(FATHER[i],i)}, i = 2,3,...,10.
Вершины 2,3,4 являются\\овьями вершины 1, вершина 5 - сы-
ном вершины 2, вершины 6,7 - сыновьями вершины 3, вершина 8 имеет
отца вершина 7 и вершины 9 и 10 - сыновья вершины 4.
Числовые поля данных используются здесь, чтобы упростить
представление дерева. Корневая вершина не имеет отца, поэтому
вместо отца для нее задается нулевое значение.
Общее правило: если T обозначает индекс корневой вершины де-
рева, то FATHER[T] = 0.
Другой метод последовательного представления деревьев заклю-
чается в использовании физической смежности элементов машинной
памяти вместо одного из полей LPTR или RPTR, например, способ
опускания полей, т.е. чтобы вершины появлялись в нисходящем по-
рядке. Дерево ( рис.6.21б), можно описать как:
┌──────────┐ указатель
RPTR ┌─────┐│ ┌──┐ │ ┌───┐
│ │ │ │
DATA 1 2 5 3 6 7 8 4 9 10 информация
TAG 1 1 1 1 1 листья
Рис. 6.22. Последовательное представление дерева методом
опускания полей
где RPTR,DATA и TAG представляют векторы. В данном методе указа-
тель LPTR не требуется, т.к. если бы он не был пуст, то указывал
бы на вершину, стоящую непосредственно справа от данной. Вектор
TAG - бинарный вектор, в котором единицы отмечают концевые верши-
ны исходного дерева. При таком представлении имеются значительные
потери памяти, т.к. свыше половины указателей RPTR оказываются
пустыми. Эти пустые места можно использовать путем установки ука-
зателя RPTR каждой данной вершины на вершину, которая следует не-
посредственно за поддеревом, расположенном под ней. В таком
представлении поле RPTR переименовывается в RANGE:
┌──────────────────────────────────┐
│ ┌─────────────┐ │
│ ┌──────┐│ ┌──────┐│┌─────┐ │
RANGE │ │ ┌──┐││ ┌──┐│ ┌──┐│││ ┌──┐│┌>│
│ │ │ │ │ │ │ │ │ │
DATA 1 2 5 3 6 7 8 4 9 10
Рис. 6.23. Последовательное представление дерева с
размещением вершин в возрастающем порядке
В этом случае поле TAG не требуется поскольку концевой узел
определяется условием RANGE(P) = P + 1.
Третий метод состоит в представлении дерева общего вида на
основе его восходящего обхода. Такое представление состоит из
двух векторов: один вектор описывает все вершины дерева в восхо-
дящей последовательности, а второй - задает полустепени исхода
этих вершин (см. рис.6.24). Восходящий метод представления удобен
для вычисления функцией, заданных на определенных вершинах дерева
( например, использование таких функций для генерации объектного
кода по обратной польской записи некоторого выражения ).
( + )
/
( ) ( / )
/ /
() ( b )( c ) ( d )
│
( a )
Рис. 6.24. Последовательное представление
дерева на основе восходящего обхода
В заключении приведем два важных понятия.
Подобие бинарных деревьев - два дерева подобны, если они
имеют одинаковую структуру ( форму ).
Эквивалентные бинарные деревья - два дерева эквивалентные,
если они подобны, и если соответствующие вершины у них содержат
одинаковую информацию.