2. Общие сведения о деревьях
 

Имеется множество подходов к определению дерева как нелинейной структуры.

В частности, дерево определяется как ациклический граф G = (V,Е) со специальной вершиной r?V (корень дерева), у которого (графа):
 1) полустепень захода вершины г равна 0;
 2) полустепень захода остальных вершин равна 1;
 3) из вершины r (корня дерева) имеется единственный путь до каждой вершины v?V.

В некоторых источниках дерево определяется как иерархическая структура. Дерево представляет собой иерархию элементов называемых узлами (вершинами). На самом верхнем уровне иерархии имеется только один узел — корень дерева. Каждый узел кроме корня, связан только с одним узлом на более высоком уровне, называемым исходным узлом (предком, отцом). Каждый элемент может быть связан посредством ребер (ветвей) с одним или несколькими элементами на следующем, более низком, уровне (с порожденными узлами, дочерними узлами). Элементы, расположенные в конце ветви, т.е. не имеющие порожденных, называются листьями (висящими вершинами). От корня до любого узла существует только один путь. Длина пути (число ветвей) от корня до некоторой вершины называется уровнем или глубиной уровня этой вершины. Уровень корня — нулевой. Наибольшая длина пути от корня до листьев дерева (максимальный уровень дерева) называется высотой дерева.

Любой узел дерева с его потомками на всех уровнях также образует дерево, называемое поддеревом, дочерние узлы также образуют поддеревья. Следовательно, каждый узел имеет столько поддеревьев, сколько у него дочерних узлов.

Отсюда возникает рекурсивное определение дерева: дерево содержит одну или несколько вершин, причем одну из них называют корнем, а остающиеся объединяют в конечное множество деревьев, называемых поддеревьями. Однако во многих алгоритмах обработки деревьев используется понятие пустого дерева, не имеющего ни одного узла, тогда более подходящим является следующее рекурсивное определение.

Древовидная структура с базовым типом Т— это либо 1) пустая структура, либо 2) узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т, называемых поддеревьями. Верхний узел называется корнем.

Число поддеревьев данного узла образует степень узла, максимальное значение m степени всех узлов дерева является степенью дерева. Дерево степени m называется m-арным деревом. все узлы дерева, кроме листьев, имеют степень, равную m, то кое дерево называется полным m-арным деревом. Дерево степени 2 называется бинарным (двоичный) деревом. Оно также может быть полным или неполным.

Если в дереве на каждом уровне задан порядок следования вершин, то такое дерево называется упорядоченным деревом. Обычно деревья считаются упорядоченными, порядок следования вершин любого узла считается заданным слева направо. Каждая вершина m-арного дерева может быть представлена строкой символов над алфавитом {0,1,..., m- 1}, при этом корень дерева характеризуется пустой строкой. Узлам первого уровня приписываются односимвольные строки 0,1,...,m-1, узлам второго уровня — двухсимвольные строки, узлы i-го уровня характеризуются строками длины i. Любая дочь вершины v характеризуется строкой, префикс которой я вляется строкой узла v, к которой справа приписывается символ 0,1,...или m- 1 в зависимости от ее позиции в нижележащем от v уровне. Строка, приписанная к листу дерева, не является префиксом ни для каких других строк, характеризующих другие вершины дерева, т.е. является уникальной. Множество строк, соответствующих листьям некоторого дерева, образует префиксный код этого дерева. На рис. показаны представление тернарного (m = 3) дерева и его префиксный код.

Префиксный код дерева=(00,010,011,012,10,11,12,20,210,22)

Рис. Тернарное дерево и его префиксный код

Мы видим, что строки, приписанные к листьям, имеют длину. Если листьям дерева поставить в соответствие символ некоторого алфавита, то элементы префиксного кода дерева можно рассматривать как коды соответствующих символов алфавита. Тогда для символов алфавита получаем коды различной длины. Этот подход используется при сжатии данных по алгоритму Хаффмана, когда символы, встречающиеся чаще, имеют коды меньшей длины.