Контрольная по "Программированию бинарных деревьев на языке СС++"

СОДЕРЖАНИЕ

Введение

1 Постановка задачи

1.1 Общая характеристика задачи

1.2 Двоичные деревья

Конструкторы и деструкторы

Поиск

Удаление элементов

2              Разработка алгоритма задачи

2.1 Описание данных, используемых для решения задачи

2.2 Описание схемы программы

3 Кодирование программы

3.1 Описание структуры разрабатываемого пакета

4 Тестирование программы

4.1 Внешний вид программы

Заключение

Список используемой литературы:

Приложение А

Введение

Язык Си, созданный Денисом Ритчи в начале 70-х годов в Bell Laboratory американской корпорации AT&T, является одним из универсальных языков программирования. Язык Си считается языком системного программирования, хотя он удобен и для написания прикладных программ. Среди преимуществ языка Си следует отметить переносимость программ на компьютеры различной архитектуры и из одной операционной системы в другую, лаконичность записи алгоритмов, логическую стройность программ, а также возможность получить программный код, сравнимый по скорости выполнения с программами, написанными на языке ассемблера. Последнее связано с тем, что хотя Си является языком высокого уровня, имеющим полный набор конструкций структурного программирования, он также обладает набором низкоуровневых средств, обеспечивающих доступ к аппаратным средствам компьютера. С 1989 года язык Си регламентируется стандартом Американского института национальных стандартов ANSI С. В настоящее время, кроме стандарта ANSI C разработан международный стандарт ISO C (International Standard Organization C).

1 Постановка задачи

1.1 Общая характеристика задачи

Работа со структурами данных:  программирование В дерева на языке  С/С++

Автоматизированная информационная система на железнодорожном вокзале содержит сведения об отправлении поездов дальнего следования.

Для каждого поезда указывается:

•              номер поезда;

•              станция назначения;

время отправления.

Данные в информационной системе организованы в виде бинарного дерева.

Составить программу, которая:

•              обеспечивает первоначальный ввод данных в информационную систему и формирование двоичного дерева;

•              производит вывод всего дерева;

•              вводит номер поезда и выводит все данные об этом поезде;

•              вводит название станции назначения и выводит данные о всех поездах, следующих до этой станции.

Программа должна обеспечивать диалог с помощью меню и контроль ошибок при вводе.

1.2 Двоичные деревья

Основные понятия

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

Дерево является типичным примером рекурсивно определённой структуры данных, поскольку оно определяется в терминах самого себя.

Рекурсивное определение дерева с базовым типом Т – это:

       либо пустое дерево (не содержащее ни одного узла)

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

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

Классификацию деревьев можно провести по разным признакам.

1. По числу возможных потомков у вершин различают двоичные (бинарные) или недвоичные (сильноветвящиеся) деревья.
   Двоичное дерево: каждая вершина может иметь не более двух потомков.
   Недвоичное дерево: вершины могут иметь любое число потомков.

2. Если в дереве важен порядок следования потомков, то такие деревья называют упорядоченными. Для них вводится понятие левый и правый потомок (для двоичных деревьев) или более левый/правый (для недвоичных деревьев). В этом смысле два следующих простейших упорядоченных дерева с одинаковыми элементами считаются разными:

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

При рассмотрении дерева как структуры данных необходимо четко понимать следующие два момента:

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

Дерево как абстрактная структура данных должна включать следующий набор операций:

       добавление новой вершины

       удаление некоторой вершины

       обход всех вершин дерева

       поиск заданной вершины

Двоичные деревья

Двоичные деревья (ДД) используются наиболее часто и поэтому представляют наибольший практический интерес. Каждая вершина ДД должна иметь два связующих поля для адресации двух своих возможных потомков.

ДД можно реализовать двумя способами:

       на основе массива записей с использованием индексных указателей

       на базе механизма динамического распределения памяти с сохранением в каждой вершине адресов ее потомков (если они есть)

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

struct TREE {
   int Info;
  TREE *Right;
  TREE *Left;
};

Для обработки дерева достаточно знать адрес корневой вершины. Для хранения этого адреса надо ввести ссылочную переменную:
TREE *Root;

Тогда пустое дерево просто определяется установкой  переменной  Root  в  нулевое значение:
Root = NULL;

Реализацию основных операций с ДД удобно начать с процедур обхода. Поскольку дерево является нелинейной структурой, то НЕ существует единственной схемы обхода дерева. Классически выделяют три основных схемы:

       обход в прямом направлении

       симметричный обход

       обход в обратном направлении

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

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

1. Обход в прямом направлении:

o         обработать корневую вершину текущего поддерева

o         перейти к обработке левого поддерева таким же образом

o         обработать правое поддерево таким же образом

2. Симметричный обход:

o         рекурсивно обработать левое поддерево текущего поддерева

o         обработать вершину текущего поддерева

o         рекурсивно обработать правое поддерево

3. Обход в обратном направлении:

o         рекурсивно обработать левое поддерево текущего поддерева

o         рекурсивно обработать правое поддерево

o         затем – вершину текущего поддерева

В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (10 вершин):

Обход в прямом порядке:

1. Выделяем поддерево 0-1-2
2. обрабатываем его корень – вершину 0
3. переходим к левому потомку и выделяем поддерево 1-3-4
4. обрабатываем его корень – вершину 1
5. выделяем левое поддерево 3-*-* (здесь * обозначает пустую ссылку)
6. обрабатываем его корень – вершину 3
7. т.к. левого потомка нет, обрабатываем правое поддерево
8. т.к. правого поддерева нет, возвращаемся к поддереву 1-3-4
9. выделяем поддерево 4-6-7
10. обрабатываем его корень – вершину 4
11. выделяем левое поддерево 6-*-*
12. обрабатываем его корень – вершину 6
13. т.к. левого потомка нет, обрабатываем правое поддерево
14. т.к. правого потомка нет, то возвращаемся к поддереву 4-6-7
15. выделяем правое поддерево 7-*-*
16. обрабатываем его корень – вершину 7
17. т.к. левого поддерева нет, обрабатываем правое поддерево
18. т.к. правого поддерева нет, то возвращаемся к поддереву 4-6-7
19. т.к. поддерево 4-6-7 обработано, то возвращаемся к поддереву 1-3-4
20. т.к. поддерево 1-3-4  обработано, возвращаемся к поддереву 0-1-2
21. выделяем правое поддерево 2-*-5
22. обрабатываем его корень – вершину 2
23. т.к. левого потомка нет, обрабатываем правого потомка
24. выделяем поддерево 5–8–9
25. обрабатываем его корень – вершину 5
26. выделяем левое поддерево 8-*-*
27. обрабатываем его корень – вершину 8
28. т.к. левого поддерева нет, обрабатываем правое поддерево
29. т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9
30. выделяем правое поддерево 9-*-*
31. обрабатываем его корень – вершину 9
32. т.к. левого поддерева нет, обрабатываем правое поддерево
33. т.к. правого поддерева нет, то возвращаемся к поддереву 5-8-9
34. т.к. поддерево 5-8-9 обработано, то возвращаемся к поддереву 2-*-5
35. т.к. поддерево 2-*-5 обработано, то возвращаемся к поддереву 0-1-2
36. т.к. поддерево 0-1-2 полностью обработано, то обход закончен

В итоге получаем следующий порядок обхода вершин: 0-1-3-4-6-7-2-5-8-9

Идеально сбалансированные деревья

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

В этом смысле ИСД полностью оправдывает свое название, поскольку вершины в нем распределяются наиболее равномерно и тем самым ИСД имеет минимально возможную высоту. Более точно, ДД называется идеально сбалансированным, если для каждой вершины число вершин в левом и правом ее поддеревьях отличаются не более чем на единицу. Обратим внимание, что данное условие должно выполняться для всех вершин дерева!

ИСД легко строится, если заранее известно количество вершин N в этом дереве. В этом случае ИСД можно построить с помощью следующего рекурсивного алгоритма:

       взять первую по порядку вершину в качестве корневой

       найти количество вершин в левых и правых поддеревьях:
NL = N div 2; NR = N – NL – 1;

       построить левое поддерево с  NL  вершинами точно таким же образом (пока не получим  NL = 0)

       построить правое поддерево с  NR  вершинами точно таким же образом (пока не получим  NR = 0)

Естественно, что реализация рекурсивного алгоритма наиболее просто выполняется в виде рекурсивной подпрограммы. При этом между этой процедурой и процедурами обхода есть одно принципиальное различие: процедуры обхода лишь используют существующую структуру дерева, не изменяя ее, и поэтому их формальные параметры являются лишь входными, тогда как процедура построения ИСД должна СОЗДАВАТЬ вершины и каждый раз возвращать в вызвавшую ее подпрограмму адрес очередной созданной вершины. Поэтому формальный параметр ссылочного типа должен быть объявлен как параметр-переменная. Кроме того, второй формальный параметр-значение принимает число вершин в текущем строящемся поддереве.

void AddNodes (Node **Сurrent, int aN);
{
  Node *Tmp;
  int NL, NR;
  if (aN==0) /*вершин для размещения нет*/
    Current = NULL; /*формируем пустую ссылку*/
  else
  {
    NL = aN div 2; /*сколько вершин будет слева?*/
    NR = aN – NL – 1; /*сколько вершин будет справа?*/
    Tmp = new Node; /*создаем корень поддерева*/
    AddNodes (&Tmp->Left, NL); /*уходим на создание левого поддерева*/
    AddNodes (&Tmp->Right, NR); /*уходим на создание правого поддерева*/
    Current = Tmp; /*возвращаем адрес созданного корня*/
  }
}

Запуск процесса построения как обычно выполняется из главной программы с помощью вызова  AddNodes(&Root, N). В этом вызове фактический параметр N обязательно должен иметь конкретное значение, например – заданное пользователем количество вершин в строящемся ИСД. Однако, первый фактический параметр Root, являясь выходным,  получит свое значение лишь после отработки всех рекурсивных вызовов, при возврате в главную программу.

Для понимания работы приведенной процедуры целесообразно вручную расписать шаги ее работы для простейшего дерева из трех вершин. Пусть элементами дерева являются символы  A, B, C. В результате работы мы должны получить:
Root = A,  A->Left = B,  A->Right = C,
B->Left = NULL,  B->Right = NULL,
C->Left = NULL,  C->Right = NULL.