Деревья

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

·

· · ·

· · · · · ·

Дерево состоит из элементов, называемых узлами (вершинами). Узлы соединены между собой направленными дугами. В случае X ® Y вершина X называется предшественником (родителем), а Y – преемником (сыном). Дерево имеет единственный узел – корень, у которого нет предшественников. Любой другой узел имеет ровно одного предшественника. Узел, не имеющий преемника, называется листом.

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

Для работы с двоичным деревом необходимо уметь:

· построить дерево;

· выполнить поиск элемента с указанным значением в узле;

· удалить заданный элемент;

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

Обычно бинарное дерево строится сразу упорядоченным, то есть узел левого сына имеет значение меньшее, чем значение родителя, а узел правого сына – большее. Например, если поступают числа 17, 18, 6, 5, 9, 23, 12, 7, 8, то построенное по ним дерево будет выглядеть так:

17

6 18

5 9 23

7 12

Для того чтобы вставить новый элемент в дерево, надо найти для него место. Начиная с корня, сравниваются значения узлов (Y) со значением нового элемента (NEW). Если NEW < Y, то идем по левой ветви, иначе – по правой. Когда дойдем до узла, из которого не выходит нужная ветвь для дальнейшего поиска, это значит, что место под новый элемент найдено. Например, выделим путь поиска места для числа 11 в предыдущем дереве:

17

6 18

5 9 23

7 12

8 11

При удалении узла возможны три ситуации:

1) исключаемый узел – лист (надо просто удалить ссылку на данный узел);

2) из исключаемого узла выходит только одна ветвь (надо ссылку у родителя на данный узел изменить на ссылку сына удаляемого узла);

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

Например, построенное выше дерево после удаления узла 6 может стать таким:

17

7 18

5 9 23

8 12

Рассмотрим задачу обхода дерева. Существуют три способа обхода, которые естественно следуют из самой структуры дерева:

1) обход слева направо: A, R, B (сначала посещаем левое поддерево, затем – корень и, наконец, правое поддерево),

2) обход сверху вниз: R, A, B (посещаем корень до поддеревьев),

3) обход снизу вверх: A, B, R (посещаем корень после поддеревьев).

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

Der () – строит дерево из элементов (слов);

Print_Der () – распечатывает дерево в соответствии с обходом слева направо: сначала посещает левое поддерево, затем корень и, наконец, правое поддерево.

Программа:

#include<stdio.h>

#include<alloc.h> /* функции динамического управления */

#include<conio.h>

#include<string.h> /* строковые функции */

#define TREE struct tree /* имя структуры элемента (узла) дерева */

TREE { /* шаблон структуры узла */

char *word; /* указатель на слово */

int count; /* счетчик повторения слов */

TREE *left; /* указатель на левое поддерево */

TREE *right; /* указатель на правое поддерево */

};

TREE *Der (TREE *elem, char *new_word) /*функция включения элемента*/

{ int sr; /* признак сравнения слов */

if (elem==NULL) /* если элемента еще нет, то */

{ elem = (TREE *)malloc(sizeof(TREE)); /* выделить память для элемента */

elem->word = new_word; /* занести в элемент новое слово */

elem->count = 1; /* начальное значение счетчика слов */

elem->left = elem->right = NULL; /* начальные указатели поддеревьев */

}

else /* если элемент уже существует, то */

if ((sr=strcmp(new_word, elem->word))==0) /* если новое и слово элемента совпадают */

elem->count++; /* увеличение счетчика слов в элементе */

else /* иначе, если слова не совпадают */

if (sr<0) /* если новое слово меньше, то */

elem->left = Der(elem->left, new_word); /* строим левое поддерево */

else elem->right = Der(elem->right, new_word); /* иначе – правое */

return elem; /* возврат указателя на элемент */

}

void Print_Der (TREE *elem) /* функция печати элементов дерева */

{

if (elem) /* если элемент существует, то */

{ Print_Der(elem->left); /* печать элементов левых поддеревьев */

printf (" %-20s \tколичество повторений - %d\n",

elem->word, elem->count); /* печать данных самого элемента */

Print_Der(elem->right); /* печать элементов правых поддеревьев */

}

}

void main() /* главная функция */

{ int i=0; /* индексная переменная */

TREE *root=NULL; /* инициирование корня дерева */

char list_word [30][21]; /* список слов */

clrscr(); /* очистка экрана */

puts ("Введите <= 30 слов длиной < 20 символов (конец ввода – 0):");

scanf ("%s", list_word[i]); /* ввод первого слова */

while (list_word [i][0]!= '0') /* цикл ввода слов */

{

root = Der (root, list_word[i]); /* построение дерева от корня */

scanf ("%s", list_word[++i]); /* ввод нового слова */

}

printf ("\nУпорядоченный список:\n");

Print_Der (root); /* печать элементов дерева */

getch(); /* задержка экрана результатов */

}

Результаты программы:

Введите <=30 слов длиной < 20 символов каждое (конец ввода – 0):

Сидоров

Артемьев

Федоров

Петров

Андреев

Федоров

Иванов

Сидоров

Иваницкий

Упорядоченный список:

Андреев количество повторений – 1

Артемьев количество повторений – 1

Иваницкий количество повторений – 1

Иванов количество повторений – 1

Петров количество повторений – 1

Сидоров количество повторений – 2

Федоров количество повторений – 2

Библиографический список

1. Прокушев Л.А. Сравнительное изучение языков Си и Паскаль: Учебно-справочное пособие. С-Пб.: СПбГААП, 1997. 152 с.

2. Касаткин А.И., Вальвачев А.Н. От Turbo C к Borland C++: Справочное пособие. Минск: Вышэйшая школа, 1992. 240 с.

3. Березин Б.И., Березин С.Б. Начальный курс С и С++. М.: Диалог-МИФИ, 2000. 288 с.

ОГЛАВЛЕНИЕ

Общие методические указания........................................................ 1

Работа со структурами данных (STRUCT)...................................... 1

Описание структур и структурных переменных......................................... 1

Вложенные структуры................................................................................ 2

Обращение к полям структуры................................................................ 3

Массивы структурных переменных............................................................. 5

Объявление типов в языке Си....................................................................... 6

Использование структур в функциях........................................................ 10

Использование глобальных данных......................................................... 12

Обработка вложенных структур................................................................. 14

Структуры и поразрядные операции........................................................... 17

Поразрядные операции.............................................................................. 17

Сдвиговые поразрядные операции............................................................. 18

Структуры с битовыми полями................................................................... 19

работа с Объединениями (union)..................................................... 20

работа с Перечислениями (enum).................................................... 22

Работа с файлами................................................................................... 25

Понятие файла и потока ввода-вывода данных в компьютере............. 25

Открытие и закрытие файла................................................................... 26

Потоки стандартного ввода-вывода....................................................... 27

Повторное открытие файла.................................................................... 28

Позиционирование указателя записи-чтения........................................... 28

Функции файлового ввода-вывода........................................................... 29

Посимвольный ввод-вывод.......................................................................... 29

Построчный ввод-вывод............................................................................ 31

Форматированный ввод-вывод данных..................................................... 33

Блоковый ввод-вывод.................................................................................. 36

Работа с динамическими структурами данных.................... 40

Динамическое распределение памяти....................................................... 40

Очередь.......................................................................................................... 41

Стек................................................................................................................ 44

Списки........................................................................................................... 46

Рекурсивные функции................................................................................. 50

Деревья........................................................................................................... 51

Библиографический список………………………………………………………..55