3. Структура данных дерево: общее определение. Двоичные деревья, способы реализации Деревья Общие сведения

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

Деревом называется орграф, для которого:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 4. Дерево произвольной степени и его динамическая организация

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

type

PTree = ^TTree;

TTree = record

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

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

end;

двоичные (бинарные) деревья – это деревья со степенью не более двух.

По степени вершин двоичные деревья бывают:

• строгие – вершины дерева имеют степень ноль (у листьев) или два (у узлов);

• нестрогие – вершины дерева имеют степень ноль (у листьев), один или два (у узлов).

В общем случае на k-м уровне двоичного дерева может быть до 2^k-1 вершин.

Двоичное дерево, содержащее только полностью заполненные уровни (то есть 2^k-1 вершин на каждом k-м уровне), называется полным.

Рисунок 5. Двоичные деревья