5.Связываем предыдущий элемент с новым key -> Next = t;

6.Если элемент добавляется не в конец списка (как показано на схеме ниже), т.е. key != end, то

( t -> Next ) -> Prev = t;

7. Иначе, если key = end, то указатель key->Next равен NULL (в п. 4 установлено окончание списка) и новым последним становится t

end = t;

Р

Общая схема вставки элемента:

key

key->Next

info

У

t

info

И

. . .

Prev

Г

Prev

Next

Б

. . .

info

Prev

а

Next

к

е

Алгоритм освобождения памяти, занятой списком, аналогичен

т

рассмотренному алгоритму для ст ка (см. разд. 15.2).

о

15.5. Нелинейные структуры данных

пи

л

В предыдущ х разделах мы рассмотрели линейные структуры

динамических с сковых данных.

б

Введение в динамическую переменную двух и более полей-указателей

и

по учить

нелинейные

структуры

данных. Наиболее

позволяет

распространенными являются структуры с иерархическим представлением, Б

которые хорошо изображаются следующим образом:

Корень дерева

Узлы

x

Y

Листья

Такая конструкция данных получила название «дерево».

142

Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X→Y вершина X

называется родителем, а Y – сыном (дочерью).

Дерево имеет единственный узел, не имеющий родителей (ссылок на этот узел), который называется корнем. Любой другой узел имеет ровно одного родителя, т.е. на каждый узел дерева имеется ровно одна ссылка.

Узел, не имеющий сыновей, называется листом.

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

15.5.1. Бинарные деревья

Р

Бинарное дерево – это динамическая структура данных, в которой ка-

ждый узел-родитель содержит, кроме данных, не более двух сыновейИ(левый

и правый).

У

На рисунке приведен пример бинарного дерева (корень обычно

изображается сверху, хотя изображение можно и перевернуть).

Г

Корень дере

Б

Root

Левое поддерево

ва

Правое поддерево

Left

к

Right

е

Такая структура данных

рганизуется следующим образом (N – NULL):

т

о

info

Left

Right

и

л

info

info

б

и

Б

info

info

info

info

N N

N N

N N

N N

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

Если дерево организовано таким образом, что для каждого узла все ключи его левого поддерева меньше ключа этого узла, а все ключи его

143

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

Представление динамических данных в виде древовидных структур оказывается довольно удобным и эффективным для решения задач быстрого поиска информации.

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

отличие от идеальной сбалансированности, когда для каждого узла дерева
	Р
количество узлов в его левом и правом поддеревьях различаются не более
чем на единицу [44].	И
Дерево по своей организации является рекурсивной структурой

данных, поскольку каждое его поддерево также является деревом. В связи с
					У
этим действия с такими структурами чаще всего описываются с помощью
рекурсивных алгоритмов.				Г
				Б
15.5.2. Основные алгоритмы работы с бинарным деревом
В общем случае при работе с такими структурами необходимо уметь:
– построить (создать) дерево;
– вставить новый элемент;		к
– обойти все элементы дере , н пример, для просмотра или
выполнения некоторой операции;			ва
е
– выполнить поиск элемента с у азанным значением в узле;
нт
– удалить заданный элеме .
Обычно бинарное дер во	с роится сразу упорядоченным, т.е. узел

левого сына имеет значение меньшее, чем значение родителя, а узел правого сына – большее.

15.5.3. Форм р вание дерева

о

Например, меется последовательность ключей 17, 18, 6, 5, 9, 23, 12, 7,

и

8, тогда построенное по ним дерево будет выглядеть следующим образом:

л

17

б

2: 6<17

1: 18>17

и

6

18

3: 5<17,

5<6

4: 9<17,

9>6

5: 23>17,

23>18

Б

5

9

23

7: 7<17, 7>6, 7<9

6: 12<17,

12>6, 12>9

7

12

8: 8<17, 8>6, 8<9, 8>7

8

144

15.5.4. Вставка нового элемента

Для того чтобы вставить новый элемент в дерево, необходимо найти для него место. Для этого, начиная с корня, сравниваем значения узлов (Tree->info) со значением нового элемента (b). Если b < info, то идем по левой ветви, в противном случае – по правой ветви. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это означает, что место под

новый элемент найдено.

Р

Путь поиска места в построенном дереве для числа 11:

11<17

17

6

18

У

11>6

Г

И

5

9

11>9

23

Б

7

12

11< 12 и из узла (12)

нет ветви

а

8

11

Функция

создания

дерева,

люч ми которого

являются целые

положительные числа, может иметь следующий вид:

Tree* Make(Tree *Root)

{

е

Tree *Prev, *t;

т

// Prev родит льк(предыдущий) текущего элемента

int b, find;

о

// Если дерево не создано

if ( Root == NULL )

{

printf("\n Input Root : ");

scanf(“%d”, &b);

Root = List(b);

// Установили указатель на корень

}

л

б

//================иДобавление элементов =================

while(1) {

printf("\n Input Info : ");

scanf(“%d”, &b);

if (b<0) break;

// Признак выхода число < 0

t = Root;

// Текущий указатель на корень

иfind = 0;

// Признак поиска

Б

while ( t && ! find) {

Prev = t;

if( b == t->info)

find = 1;

// Ключи должны быть уникальны

else

if ( b < t -> info ) t = t -> Left; else t = t -> Right;

}

145

	if (!find) {	// Нашли место с адресом Prev
	t = List(b);	// Создаем новый узел
	if ( b < Prev -> info )	// и присоединяем его, либо
	Prev -> Left = t;	// на левую ветвь,
	else Prev -> Right = t;	// либо на правую ветвь
	}
}	// Конец цикла
return Root;
}
Функция List предназначена для создания нового элемента – листа:
Tree* List(int i) {			И
Tree *t = (Tree*) malloc (sizeof(Tree));				Р
t -> info = i;		У
t -> Left = t -> Right = NULL;
		Г
	¼
return t;

}

Участок кода с обращением к функции Create будет иметь следующий вид:

	};					а
struct Tree {						// Декл рация шаблона
	int info;					к	Б
	Tree *Left, *Right;
void main()				т
{					е// Указатель корня
Tree *Root = NULL;
	¼		о
Root = Make(Root);
	¼	ние
	л		узла
15.5.5. Уда
П уда ении узла из дерева возможны три ситуации в зависимости от
ри
того, сколько сыновей (потомков) имеет удаляемый узел.
Б
1.бУдаляемый узел является листом – просто удаляем ссылку на него.
Пр ведем пример схемы удаления листа с ключом key:
				5			5
						Получим
			key		8		NULL	8

146

2. Удаляемый узел имеет только одного потомка, т.е. из удаляемого узла выходит ровно одна ветвь. Пример схемы удаления узла key, имеющего одного сына:

5		5
	Получим
key		7
7	NULL
3. Удаление узла, имеющего		двух сыновей, значительноРсложнее
		У
рассмотренных выше. Если key – удаляемый узел, то его следует заменить
		Г
узлом w, который содержит	либо	наибольший ключ (самыйИправый, у

которого указатель Right равен NULL) в левом поддереве, либо наименьший ключ (самый левый, у которого указатель Left равен NULL) в правом поддереве.

Используя первое условие, находим узел w, который является самым

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

Б

key

Удалить узела(7)

7

к

6

Получим

4

9

е

4

9

т

w

2

6

8

2

5

8

10

10

о

5

и

NULL

NULL

л

В построенном ранее дереве удалим узел key (6). Используем второе

б

самый

левый узел в правом поддереве –

это узел w

услов е, т.е.

щем

(указательиLeft равен NULL):

Б

147

17

17

Левое	key		w		Правое
поддерево	6	18	7	18	поддерево
(Left)					(Right)

5	9	23	5	9	23
	w			8	12
	7	12			11

//Del, Prev_Del – удаляемый элемент и его предыдущийГУ(родительИР);

//R, Prev_R – элемент, на который заменяется удаленный, и его родитель; Del = Root; Б

Prev_Del = NULL;

//===== Поиск удаляемого элемента иаего родителя по ключу key =====

while (Del != NULL && Del -> info != key) { Prev_Del = Del; к

if (Del->info > key) еDel = Del->Left;

ло8 11бelse {

Би

// Ищем самый правый узел в левом поддереве

Prev_R = Del;

R = Del->Left;

while (R->Right != NULL) { Prev_R = R;

R = R->Right;

}

// Нашли элемент для замены R и его родителя Prev_R if( Prev_R == Del)

R->Right = Del->Right;

else {

148

R->Right = Del->Right;

Prev_R->Right = R->Left;

R->Left = Prev_R;

}

}

// Удаляя корень, заменяем его на R

if (Del== Root) Root = R;

else

// Поддерево R присоединяем к родителю удаляемого узла

if (Del->info < Prev_Del->info) Prev_Del->Left = R;

// на левую ветвь

else

Prev_Del->Right = R;

Р

// на правую ветвь

printf("\n Delete element %d \n", Del->info);

И

free(Del);

return Root;

У

}

Участок программы с обращением к данной функции будет иметь вид

¼

Г

printf("\n Input Del Info : ");

Б

scanf(“%d”, &key);

Root = Del(Root, key);

а

¼

к

15.5.6. Алгоритмы обхода

рева

де

Существуют три алгоритма обхода деревьев, которые естественно

следуют из самой структуры дер ва.

1. Обход

слева направо: Left-Root-Right (сначала посещаем левое

о

поддерево, затем – корень и, наконец, правое поддерево).

2. Обход сверху вниз: Root-Left-Right (посещаем корень до поддеревьев).

3. Обход сн зу вверхт: Left-Right-Root (посещаем корень после

поддеревьев).

л

Интересно прос ед ть результаты этих трех обходов на примере

записи форму ы видев

дерева, так как они и позволяют получить различные

формыпиза бси арифметических выражений.

Пусть для операндов А и В выполняется операция сложения. ПривычнаяБ форма записи в виде А+В называется инфиксной. Форма записи, в которой знак операции следует перед операндами +АВ, называется префиксной, если же операция записывается после операндов АВ+ –

постфиксной.

Рассмотрим небольшой пример, пусть задано выражение А+В*С. Так как умножение имеет более высокий приоритет, то данное выражение можно переписать в виде А+(В*С). Для записи выражения в постфиксной форме сначала преобразуем ту часть выражения, которая вычисляется первой, в результате получим: А+(ВС*).

Теперь запишем в постфиксной форме операцию сложения между операндами А и (ВС*): АВС*+.

149

Таким образом, выражение А+В*С в постфиксном виде АВС*+, префиксная форма записи будет иметь вид +*АВС.

Рассмотрим различные обходы дерева на примере формулы: ((a+b/c)*(d–e*f )). Дерево формируется по принципу:

–в корне размещаем операцию, которая выполнится последней;

–далее узлы-операции, операнды – листья дерева.

Обход 1 (Left-Root-Right) дает обычную инфиксную запись выражения (без скобок):

a + b / c * d – e * f .

Р

*

И

+

-

У

a

/

d

*

b

c

e

Г

f

Обход 2 (Root-Left-Right) – префиксную запись выражения (без скобок):

* + a / b c – d * e f .

а

Б

+

к

-

е

*

т

*

о

/

d

a

и

b

c

e

f

О

л

3 (Left-Right-Root) – постфиксную запись выражения:

бход

a b c / + d e f * – * .

и

*

Б

+

-

a

/

d

*

b

c

e

f

15.5.7. Функция просмотра

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

150