Деревья

Конечное корневое дерево

$T$

формально определяется как непустое множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на

$m \geqslant 0$

поддеревьев

$T_1,T_2,\ldots,T_m$

. Будем рассматривать только корневые деревья. Узлы, не имеющие поддеревьев, называются листьями; остальные узлы называются внутренними узлами.

Рис. 4.1.

Дерево с 11 узлами, помеченными буквами от

$A$

до

$K$

. Узлы с метками

$D,E,F,H,J,K$

являются листьями; другие узлы внутренние. Узел с меткой

$A$

- корень

В первой лекции уже было использовано дерево - при изучении необходимого числа взвешиваний в задаче о фальшивой монете с

$n$

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

В описании соотношений между узлами дерева используем терминологию, принятую в генеалогических деревьях. Так, говорят, что в дереве или поддереве все узлы являются потомками его корня, и наоборот, корень есть предок всех своих потомков. Корень именуют отцом корней его поддеревьев, которые в свою очередь будут сыновьями корня. Например, на рис. 4.1 узел

$A$

является отцом узлов

$B,G$

$I$

;

$J,K$

- сыновья

$I$

, а

$C,E,F$

- братья.

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

Рис. 4.2. Различные деревья

Определим лес как упорядоченное множество деревьев; в связи с этим можно перефразировать определение дерева: дерево есть непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с

$m \geqslant 0$

поддеревьями корня. Важной разновидностью корневых деревьев является класс бинарных деревьев. Бинарное дерево

$T$

либо пустое, либо состоит из выделенного узла, называемого корнем, и двух бинарных поддеревьев: левого

$T_l$

и правого

$T_r$

.

Содержание Вперед