Определение структуры: дерево

Дерево – это конечное множество T, возможно пустое, в противном случае, состоящее из одного или более элементов (узлов или вершин дерева) таких, что:

а) имеется один специально обозначенный элемент, называемый корнем данного дерева;

б) остальные элементы содержатся в m >0 попарно непересекающихся множествах T₁,...,T_m, каждое из которых в свою очередь является деревом; деревья T₁,..., T_m называются поддеревьями данного корня (рис.1.а).

Рис.1. Виды деревьев

 

Если имеет значение относительный порядок поддеревьев T₁,...,T_{m ,} то говорят, что дерево является упорядоченным. Число поддеревьев данного узла называется степенью этого узла. Узел с нулевой степенью называется концевым узлом (или листом или терминальным узлом), все остальные элементы – внутренние узлы (нетерминальные). Максимальная степень всех вершин называется степенью дерева. Корень дерева имеет уровень равный 0. Остальные вершины имеют уровень на единицу больше уровня непосредственного предка. Максимальный уровень какой-либо из вершин называется глубиной или высотой дерева. Минимальная высота при заданном числе вершин достигается, если на всех уровнях, кроме последнего, помещается максимально возможное число вершин. Максимальное число вершин в дереве высотой h достигается в том случае, если из каждой вершины, за исключением уровня h, исходят d поддеревьев, где d –степень дерева: на 0-м уровне 1 вершина, на 1-м – d потомков, на 2-м – d² потомков, на 3-м уровне d³ потомков и т.д.

Наиболее широко используются двоичные (бинарные) деревья (рис.1.б). Бинарное дерево это конечное множество элементов, которое либо пусто, либо состоит из корня и из двух непересекающихся бинарных деревьев, называемых левым и правым поддеревьями данного корня. Таким образом, каждый элемент бинарного дерева имеет 0, 1 или 2 поддерева. Бинарное дерево – упорядоченное дерево, так как в нем различают левое и правое поддеревья.

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

Структуру данных – дерево можно представить как в статической, так и в динамической памяти.

В статической памяти дерево можно представить массивом, для которого определено понятие пустого элемента:

 

struct stree

{ type elem [ N ]; }

 stree d;

или

type d [ N ];

Рис.2. двоичное дерево представленное в виде массива

 

Вершины двоичного дерева располагаются в массиве следующим образом (см. рис.2.): если k – индекс вершины дерева, то ее потомки находятся в элементах массива с индексами 2k + 1 и 2(k + 1); корень дерева находится в элементе с индексом 0 (при индексации в массиве от 1 до N индексы потомков k-ой вершины: 2k и 2k + 1, корень имеет индекс 1).

В динамической памяти дерево представляется иерархическим списком. Задать элемент двоичного дерева можно как элемент списка с тремя полями: два ссылочных поля, содержащие указатели на его левое (L) и правое (R) поддеревья, и информационное поле (E):

Определение типа элемента бинарного динамического дерева:

struct btree

{type elem;

btree *left, *right;}

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

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

btree * d;

 

Рис.3. Двоичное динамическое дерево

 

На рис.3 представлено двоичное динамическое дерево d в соответствии с определением типа элемента, сделанным выше. Элементы дерева со степенью 0 и 1 имеют два или одно ссылочное поле со значением равным пустому указателю (NULL).

Обрабатывая дерево, приходится просматривать его элементы – эта операция называется обход дерева (или прохождение дерева).

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

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

 

Возможны два способа прохождения бинарного дерева (если дерево не пусто):

- в глубину;

- в ширину.

Алгоритмы обхода в глубину

Существует несколько способов обхода в глубину:

1. Прямой порядок (см. рис.4.а):

а) попасть в корень;

б) пройти в прямом порядке левое поддерево;

в) пройти в прямом порядке правое поддерево.

2. Обратный порядок(см. рис.4.б):

а) пройти в обратном порядке левое поддерево;

б) пройти в обратном порядке правое поддерево;

в) попасть в корень.

3. Симметричный порядок(см. рис.4.в):

а) пройти в симметричном порядке левое поддерево;

б) попасть в корень;

в) пройти в симметричном порядке правое поддерево.

 

Рис.4. Способы обхода дерева в глубину

 

 

Алгоритм прямого обхода:

 { S = NULL;

       while (d!= NULL)

{ обработка (d);

if (d->left!= NULL && d->right!= NULL)

{в стек (S, d->right); d = d->left;}

else

if (d->left = = NULL && d->right = =NULL)

if (S!= NULL) из стека (S, d); else d = NULL;

else  if (d->left!= NULL) d = d->left;

else d = d->right;

}

}

Рекурсивное описание алгоритма прямого обхода:

пр_обход (btree *d)

{ if (d!= NULL) { обработка (d); пр_обход (d->left);

    пр_обход (d->right); }

}

 

Алгоритм обратного обхода:

{ S = NULL; F = 1;

while (F)

{ while (d!= NULL)

{ встек (S, d); d = d->left; }

if (S!= NULL) { изстека (S, d);

обработка (d); d = d-right;}

else F = 0;

}

}

Рекурсивное описание алгоритма обратного обхода:

обр_обход (btree *d)

{ if (d!= NULL) { обр_обход (d->left); обработка (d);

  обр_обход (d->right); }

}

 

Алгоритм симметричного обхода можно получить преобразив и соединив оба предыдущих алгоритма

Алгоритмы обхода в ширину

 

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

Алгоритм обхода в ширину:

{ Q = NULL;

if (d!= NULL) { в_очередь (Q, d);

 do

из_очереди (Q, d); обработка (d);

         if (d->left!= NULL) в_очередь (Q, d->left);

if (d->right!= NULL) в_очередь (Q, d->right);

while (! пуста_очередь (Q));

} }

Рис.5. Порядок обхода дерева  в ширину

Ввод дерева

 

Чтобы ввести дерево надо выбрать какой-то способ перечисления его узлов. Одним из возможных способов является так называемая списочная запись (представление). Список – это конечная последовательность атомов либо списков, число которых, может быть и равно нулю (атом – это понятие, определяющее элемент из любого множества предметов). Используя скобки, список можно задать перечислением через запятую его атомов (порядок перечисления атомов определяет их упорядочение). Таким образом, дерево, представленное на рис.4.1.б можно записать в виде следующего списка:

 (A, (B, (С, 0, 0), (D, 0, 0)), (E, (F, 0, 0), (G, (H, 0, 0), (I, 0, 0))))

Ввод дерева, представленного таким списком, можно описать рекурсивной функцией (тип дерева btree описан выше, здесь type – тип информационного поля элемента – сhar):

btree * build_tree ()

{ char sym;

btree *d;

scanf (“%c”, &sym);

switch (sym)

{case ‘ (‘:

{ d = new btree;

scanf (“%c”, &sym); d->elem = sym;

d->left = build_tree ();

d->right = build_tree (); scanf(“%c”, &sym);

return d;

}

case ‘0’: return NULL;

case ‘,’: d = build_tree (); break;

}

}

Разрушение дерева

 

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

Эту операцию реализуйте самостоятельно.