Представление корневых деревьев в ЭВМ

 

 

Дерево является одним из важных и интересных частных случаев графа, поэтому оно рассматривается отдельно от графов других видов. Деревом называется орграф, для которого:

1) Существует узел, в который не входит не одной дуги (корень);

2) В каждую вершину, кроме корня, входит одна дуга.

 

Вершины дерева подразделяют на следующие три группы:

1) Корень – вершина, в которую не входит не одной дуги;

2) Узлы – вершины, в которые входит одна дуга и выходит одна или более дуг;

3) Листья – вершины, в которые входит одна дуга и не выходит ни одной дуги.

 

Все вершины, в которые входят дуги, исходящей из одной вершины, называются потомками этой вершины, а сама вершина – предком. Корень не имеет предка, а листья не имеют потомков.

Выделяют уровни дерева. На первом уровне дерева может быть только одна вершина – корень, на втором – потомки корня, на третьем – потомки потомков корня, и т.д.

Поддеревом называется вершина со всеми ее потомками.

Высотой поддерева считается максимальная длина цепи y₁...y_n его вершин, причем такая, что y_i+1 – потомок y_i для всех i. Высота пустого дерева равна нулю. Высота дерева из одного корня – единице.

Степенью вершины в дереве называется количество дуг, которое из нее выходит. Степень дерева равна максимальной степени вершины, входящей в дерево. При этом листьями в дереве являются вершины, имеющие степень ноль.

По величине степени дерева часто различают два типа деревьев:

- Двоичные – степень дерева не более двух;

- Сильноветвящиеся – степень дерева произвольная.

 

Рисунок 3.9 – Дерево произвольной степени и его динамическая организация (схема «левый ребенок – правый сосед»)

 

Дерево произвольной степени (сильноветвящееся дерево) можно реализовывать как любой граф. Однако, учитывая специфику дерева как частного случая графа, можно рассмотреть отдельный способ реализации – как динамическая структура в виде списка. Списочное представление деревьев произвольной степени основано на элементах, соответствующих вершинам дерева. Каждый элемент имеет поле данных и два поля указателей: указатель на начало списка потомков вершины и указатель на следующий элемент в списке потомков текущего уровня. При таком способе представления дерева обязательно следует сохранять указатель на вершину, являющуюся корнем дерева. Т.е. по-прежнему в
каждой вершине хранится указатель р на родителя и атрибут root[T] является
указателем на корень дерева. Кроме р, в каждой вершине хранятся ещё два
указателя:

1) left-child[a] указывает на самого левого ребёнка вершины х;

2) right-sibling[x] указывает на ближайшего справа соседа вершины х («следующего по старшинству брата»).

Вершина х не имеет детей тогда и только тогда, когда left-child[x] = NIL. Если
вершина х – крайний правый ребенок своего родителя, то right-sibling[x] = NIL.

 

 

type

PTree = ^TTree;

TTree = record

Data: TypeElement; {поле данных}

Childs, Next: PTree; {указатели на потомков и на следующий}

end;

 

Обходы деревьев

 

Существует несколько способов обхода (просмотра) всех вершин дерева. Три наиболее часто используемых способа обхода называются:

- в прямом порядке;

- в обратном порядке;

- в симметричном (внутреннем) порядке.

Все три способа обхода рекурсивно можно определить следующим образом:

 

1) Если дерево Tree является пустым деревом, то в список обхода заносится пустая запись;

2) Если дерево Tree состоит из одной вершины, то в список обхода записывается эта вершина;

3) Если Tree – дерево с корнем n и поддеревьями Tree₁, Tree₂, … Tree_k, то:

- при прохождении в прямом порядке сначала посещается корень n, затем в прямом порядке вершины поддерева Tree₁, далее в прямом порядке вершины поддерева Tree₂, и т.д. Последними в прямом порядке посещаются вершины поддерева Tree_k;

- при прохождении в обратном порядке сначала посещаются в обратном порядке вершины поддерева Tree₁, далее последовательно в обратном порядке посещаются вершины поддеревьев Tree₂, … Tree_k. Последним посещается корень n;

- при прохождении в симметричном порядке сначала посещаются в симметричном порядке вершины поддерева Tree₁, далее корень n, затем последовательно в симметричном порядке вершины поддеревьев Tree₂, … Tree_k.

 

Рисунок 3.10 – Порядки обхода дерева (прямой, симметричный, обратный)

 

Далее приведены макеты процедур, реализующих указанные способы обходов деревьев. При доработке представленного кода необходимо учитывать конкретную реализацию деревьев.

 

procedure PreOrder(n: вершина);

{Обход дерева в прямом порядке}

begin

Занести в список обхода вершину n;

for для каждого потомка s вершины n в порядке слева направо do

PreOrder(s);

end;

 

procedure InOrder(n: вершина);

{Обход дерева в симметричном порядке}

begin

if n – лист then begin

занести в список обхода узел n;

end else begin

InOrder(самый левый потомок вершины n);

Занести в список обхода вершину n;

for для каждого потомка s вершины n, исключая самый левый,

в порядке слева направо do

InOrder(s);

end;

end;

 

procedure PostOrder(n: вершина);

{Обход дерева в обратном порядке}

begin

for для каждого потомка s вершины n в порядке слева направо do

PostOrder(s);

Занести в список обхода вершину n;

end;

 

Листинг 3.21 – Обходы деревьев (PreOrder, InOrder, PostOrder)