Очень важно проследить, как будет выглядеть  результирующее двоичное дерево поиска в каждом случае. Рассмотрим случай 1. Если подлежащий удалению узел n, является левым потомком, то элементы, относящиеся  к правому поддереву n будут меньше, чем у узла р, предка узла n. При удалении узла n его правое поддерево связывается с узлом р и элементы, хранящиеся в новом левом поддереве узла р конечно остаются меньше элемента в узле р. Поскольку никакие другие ссылки не изменяются, то дерево остается двоичным деревом поиска. Аргументы остаются подобными, если узел n является правым потомком, и они тривиальны, если n — корневой узел. Случай 2 объясняется аналогично. В случае 3 элемент v, записанный в узле n, перекрывается следующим большим элементом, хранящимся в узле m (назовем его w), после чего элемент w удаляется из дерева. В получающемся после этого двоичном дереве значения в левом поддереве узла n будут меньше w, поскольку они меньше v. Более того, элементы в правом поддереве узла n больше, чем w, поскольку (1) они больше, чем v, (2) нет ни одного элемента двоичного дерева поиска, лежащего между v и w и (3) из них элемент w был удален.

      Заметим, что в случае 3 узел m должен обязательно  существовать, поскольку правое поддерево  узла n непустое. Более того, рекурсивный вызов для удаления m не может привести к срыву рекурсивного вызова, поскольку если узел m не имел бы левого потомка, то был бы применен случай 1, когда его нужно было бы удалить.

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

      Компонентная  функция remove является общедоступной компонентной функцией для удаления узла, содержащего заданный элемент. Она обращается к собственной компонентной функции _remove, которая выполняет фактическую работу:

      

      Рис. 5 Последовательность операций удаления элемента: (а) и (б) — Случай 1: удаление из двоичного дерева элемента 8; (б) и (в) — Случай 2: удаление элемента 5; (в) и (г) - Случай 3: удаление элемента 3

      template<class T> void SearchTree<T>::remove(Т val)

      {

        _remove(val, root);

      } 

      template<class T>

      void SearchTree<T>::_remove(Т val, TreeNode<T> * &n)

      {

        if (n == NULL)

          return;

        int result = (*cmp) (val, n->val);

        if (result < 0)

          _remove(val, n->_lchild);

        else if (result > 0)

          _remove (val, n->_rchild);

        else {                              // случай 1

          if (n->_lchild == NULL) {

              TreeNode<T> *old = n;

              n = old->_rchild;

              delete old;

            }

          else if (n->_rchild == NULL {     // случай 2

            TreeNode<T> *old = n;

            n = old->_lchild;

              delete old;

          }

          else {                           // случай 3

            TreeNode<T> *m = _findMin(n->_rchild);

              n->val = m->val;

              remove(m->val, n->_rchild);

            }

        }

      }

      Параметр n (типа ссылки) служит в качестве псевдонима для поля ссылки, которое содержит ссылку вниз на текущий узел. При достижении узла, подлежащего удалению (old), n обозначает поле ссылки (в предке узла old), содержащее ссылку вниз на old. Следовательно команда n=old->_rchild заменяет ссылку на old ссылкой на правого потомка узла old.

      Компонентная  функция removeMin удаляет из дерева поиска наименьший элемент и возвращает его:

      template<class Т> Т SearchTree<T>::removeMin (void)

      {

        Т v = findMin();

        remove (v);

        return v;

      }

      Древовидная сортировка — способ сортировки массива элементов — реализуется в виде простой программы, использующей деревья поиска. Идея заключается в занесении всех элементов в дерево поиска и затем в интерактивном удалении наименьшего элемента до тех пор, пока не будут удалены все элементы. Программа heapSort(пирамидальная сортировка) сортирует массив s из n элементов, используя функцию сравнения cmp:

      template<class T> void heapSort (T s[], int n, int(*cmp) (T,T) )

      {

        SearchTree<T> t(cmp);

        for (int i = 0; i < n; i++)

          t.insert(s[i]);

        for (i = 0; i < n; i++)

          s[i) = t.removeMin();

      } 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

     В данной задаче использовались следующие  данные:  

исходные (входные) данные:

struct traine {                    //структура - дерево

    unsigned long time;            //время отправления в секундах

    unsigned short number;        //номер поезда

    char *station;                //имя станции

    traine *left,*right;};        //указатели на левую и правую ветку дерева 

выходные  результаты решения: 

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

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

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

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

     Схема алгоритма отображает последовательность операций в программе.

     Произведено выделение основных этапов в виде подпрограмм, выполняющих следующие действия: 

• ввод исходных данных;
• вывод полученных результатов (поиск удовлетворяющей заявки, вывод всего списка) на экран .

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

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

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

     Программа курсовой работы разработана  в среде  визуального  программирования  С++   и  состоит из исполняемого файла с расширением .cpp.

     Программа выполнена на основе структурного программирования(в виде бинарного дерева)  и содержит следующие процедуры и функции:

struct traine {                    //структура - дерево

   

void show_all(traine *temp){    //функция вывода всего дерева - рекурсивный обход 

void show_number(traine *temp, unsigned short number){ //поиск элемента с нужным номером, с учётом отсортированности дерева

void show_station(traine *temp, char st[50],bool &f){ //переменная f нужна для  определения, был ли найден  хотя бы 1 поезд, т.к. обход производится "втупую", т.к. дерево сортировано  не по имени станции

int main() {    //главная функция 
 
 
 
 
 
 
 
 
 
 
 

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

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

 

     Запуск  программы производится из среды C++ нажатием клавиш F5. При запуске программа сама просит ввести все необходимые данные и сохраняет результаты в текстовый файл. 

Основное  окно программы имеет вид:

Рис. 1 – Основное окно программы

это диалоговое окно-меню, где выбирается необходимая  операция;

При выборе первой операции (ввод данных) программа  будет выглядеть следующим образом:

 

Рис. 2 – Выбор первой операции 
 

При выборе второй операции программа будет выглядеть следующим образом:

Рис. 3 – Выбор второй операции

Рис. 4 – Выбор третьей  операции

Рис. 5 – Выбор  четвертой операции

      Заключение

 

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

     При работе над программой пройдены все  этапы создания программных продуктов. Получены навыки в описании бинарного дерева, разработке алгоритма программы, составлении текста программы и проведении тестирования программы. Использована среда программирования C++. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

 
      

1.  Б.Керниган, Д.Ритчи, А.Фьюер. Язык программирования Си. Задачи по языку Си. М.: Финансы и статистика, 2008.
2. М.Уэйт, С.Прата, Д.Мартин. Язык Си. Руководство для начинающих. - М.: Мир, 1998.
3. М.Болски. Язык программирования Си. Справочник. - М.: Радио и связь, 1998.
4. Л.Хэнкок, М.Кригер. Введение в программирование на языке Си. - М.: Радио и связь, 1990.
5. Р.Берри, Б.Микинз. Язык Си. Введение для программистов. - М.: Финансы и статистика, 1988.
6. S.Dewhurst, K.Stark. Programming in C++. - Prentice Hall, 1989.
7. M.Ellis, B.Stroustrup. The annotated C++ Reference Manual. - Addison-Wesley, 19
8. ТО 04-2008

      Приложение  А

      Листинг программы: 
 

#include <iostream.h>

#include <conio.h>

#include <stdlib.h>

struct traine {                    //структура - дерево

    unsigned long time;            //время отправления в секундах

    unsigned short number;        //номер поезда

    char *station;                //имя станции

    traine *left,*right;};        //указатели на левую и правую  ветку дерева

traine* add(traine *beg, unsigned short number, unsigned long time, char station[50])    //функция добавления элемента в дерево

{

    if (!beg) {                        //если дерево пустое

        traine *temp=new traine;

        temp->number=number;

        temp->time=time;

        temp->station = new char[];

        temp->station=station;

        temp->left=0;

        temp->right=0;

        return temp;

    }                //если дерево не пустое, начинается  рекурсивный вход в него

<