СОДЕРЖАНИЕ 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

      Введение

 

      Язык  Си, созданный Денисом Ритчи в  начале 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. Обход в прямом направлении:
• обработать корневую вершину текущего поддерева
• перейти к обработке левого поддерева таким же образом
• обработать правое поддерево таким же образом
2. Симметричный обход:
• рекурсивно обработать левое поддерево текущего поддерева
• обработать вершину текущего поддерева
• рекурсивно обработать правое поддерево
3. Обход в обратном направлении:
• рекурсивно обработать левое поддерево текущего поддерева
• рекурсивно обработать правое поддерево
• затем – вершину текущего поддерева

      

      В качестве примера по шагам рассмотрим обход следующего ДД с числовыми компонентами (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; /*возвращаем адрес созданного корня*/ 
  } 
}