Способы представления деревьев

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

Рис.3.2. Графическое изображение дерева

Традиционно деревья изображают графически, располагая корень вверху (т. е. дерево растет вниз), как показано на рис. 3.2. Очевидно, такое представление связано с тем, что человеку привычнее рисовать и читать рисунок сверху вниз. Узлы дерева обычно изображают с помощью окружностей, соединяя каждый узел с его сыновьями линиями (связями). Связи обычно изображают без стрелки на конце.

Другим представлением может быть так называемый уступчатый список. На рис.3.3,а,б так представлено дерево из рис.3.2.

a ▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓▓ а

b ▓▓▓▓▓▓▓▓▓▓▓▓▓▓    b

i ▓▓▓▓▓▓▓▓▓▓       i

j ▓▓▓▓▓▓▓▓▓▓       j

c ▓▓▓▓▓▓▓▓▓▓▓▓▓▓    c

h ▓▓▓▓▓▓▓▓▓▓       h

d ▓▓▓▓▓▓▓▓▓▓▓▓▓▓    d

e ▓▓▓▓▓▓▓▓▓▓       e

f ▓▓▓▓▓▓▓▓▓▓       f

    k ▓▓▓▓▓▓▓            k

g ▓▓▓▓▓▓▓▓▓▓       g

           а)              б)

Рис.3.3. Представление дерева: а – в виде уступчатого списка; б – в виде “упрощенного”уступчатого списка

Здесь двухмерность рисунка поддерживается посредством отступов.

Более компактными являются одномерные способы изображения деревьев. Например, от списка с отступами можно легко перейти к десятичной системе обозначений Дьюи, которая используется в библиографии. Например, для нашего дерева она будет выглядеть так:

1.a, 1.1.b, 1.1.1.i, 1.1.2.j, 1.2.c, 1.2.1.h,

1.3.d, 1.3.1.e, 1.3.2.f, 1.3.2.1.k, 1.3.3.g

Другой вид одномерного представления дерева - это так называемая скобочная запись, в которой отношения иерархии представляются с помощью вложенности скобок. Один из возможных вариантов скобочной записи [8] для дерева (рис.3.2) выглядит так:

(a (b (i)(j))(c (h)) (d (e) (f(k))(g)))

Можно немного сократить количество скобок:

a (b (i, j), c (h), d (e, f (k), g))

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

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

Например, представим дерево из рис. 3.2. в виде таблицы, содержащей для каждого узла обозначение его родителя. Для экономии места расположим таблицу горизонтально, хотя логичнее представить дерево в виде таблицы из двух столбцов— «узел»-«его родитель».

Таблица 3.2.

Предствление дерева из рис. 3.2 с помощью ссылок на родителей

Узел	a	b	c	d	i	j	h	e	f	g	k
Родитель	nil	a	a	a	b	b	c	d	d	d	f

 

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

Еще один способ представления деревьев с помощью указания левого сына и правого брата каждого узла также не обладает достаточной наглядностью, но очень удобен для эффективной реализации. Этот способ будет подробно рассмотрен ниже (см. разд. 3.4).

Терминология деревьев

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

Стандартная терминология деревьев происходит от генеалогических деревьев. Каждый узел (элемент дерева) является родителем (parent) корней его поддеревьев, а сами корни называются братьями, а также детьми (child) или сыновьями своего родителя. Узлы, которые или являются детьми данного узла, или являются детьми его детей, называются потомками данного узла. И наоборот, родитель узла, а также родители родителей называются предками узла. Корень является общим предком всех узлов дерева.

 Узел, не имеющий детей, называется листом или внешним узлом (leaf, external node). Остальные узлы являются внутренними (internal). Количество детей (непосредственных потомков) узла называется его степенью. Листья имеют степень ноль. Если максимальная степень узлов дерева больше двух, то такие деревья называют сильно ветвящимися.

Путем (path) из узла n₁ в узел n_k называется последовательность узлов n₁. n₂,..., n_k, где для всех i (1  i< k) узел n_i, является родителем узла n_i+1. Длиной пути называется число, на единицу меньшее числа узлов, составляющих этот путь (или равное количеству линий связи). Например, на рис. 3.2 путем из узла d в узел k будет являться последовательность d f k. Длина такого пути равна двум (две связи).

Основное свойство корневых деревьев — путь от корня до любого узла всегда существует и является единственным. Это свойство вытекает из того факта, что в иерархических структурах каждый узел всегда имеет только одного родителя (одну линию связи с родительским узлом), а значит, и единственный путь до корня дерева.

Высотой (height) узла дерева называется длина самого длинного пути из этого узла до какого-либо листа. Высота дерева совпадает с высотой корня.

Уровень узла (level) определяется как длина пути от корня до этого узла. Корень имеет уровень ноль. Все братья имеют один и тот же уровень, который на единицу больше уровня их отца. Например, на рис. 3.2 братья a, b и c имеют уровень 1, а сыновья узла с (братья e,f и g) имеют уровень 2. Высота дерева на рис.3.2 равна трем.