Способы построения и представления деревьев

     }

     return root:

     }

     //   Чтение из файла информации о нарушении

     int. read_fine(ifstream f, Data& data) { f.getline(data.time, l_time);

     if(data.time[0] == '=') return 1;     // Конец списка нарушений

      f,getline(data.type, l_type);

      f >> data.price;

     f.get();

     return 0; // Нарушение считано успешно

     }

     //   Удаление нарушения из списка

     int remove_fine(Node* p. const DataS data) {

     Fine* prev. *pf= p->beg;

     bool found = false;

     while (pf && !found) {        // Цикл no списку нарушений

     if(!strcmp(pf->time, data.time))

     found = true; // Нарушение найдено

     else {

     prev = pf;

     pf = pf->next; // Переход к следующему элементу списка

     }

     }

     if (!found) {

     cout << "Сведения о нарушении отсутствуют." « endl;

       return 1;

     }

     if (pf ==p->beg) // Удаление из начала списка

     p->beg = pf->next; 
else // Удаление из середины или конца списка

     prev->next = pf->next; 
delete pf; // Освобождение памяти из-под элемента 

     if (!p->beg) return 2; //Список пуст

      return 0;

     //   Удаление узла дерева

     Node* remove node(Node* root. Node* p. Node* parent, Dir dir)}

     Node*y_; // Узел, заменяющий удаляемый

     if  (!p->left)     у = p->right;

     else if (!p->right)  у = p->left:

     else у = descent(p):

     if (p ==root) root = y;

     else {

     if (dir == LEFT)  parent->left = y: 
else parent->right = y:

     }

     delete p;

     return root:

     }

     //   Поиск с включением

     Node* search_insert(Node* root, const Data& data, Action action, 
Dir& dir. Node*& parent) { 
Node* p = root;            // Указатель на текущий элемент

     bool found = false;     // Признак успешного поиска 
int cmp;      // Результат сравнения ключей

     parent=0;

     while (p&&!found) {  // Цикл поиска по дереву

     cmp = strcmp(data.number, p->number);

      if  (!cmp) found = true;

      else {

      parent = p:

     if (cmp < 0) { p = p->left; dir = LEFT;}

      else     { p = p->right: dir = RIGHT: }

     }

     }

     if (action != INSERT) return p; 

     // Создание записи о нарушении:

     Fine* pf = new Fine;

     strncpy(pf->time, data.time, l_time);

      strncpy(pf->type. data.type. l_type);

      pf->price = data.price;

      pf->next = 0;

     if (!found) {

      // Создание нового узла:

       p = new Node;

           strncpy(p->number, data.number, l_number);

     p->beg = pf:

     p->left = p->right = 0:

     if (dir == LEFT)    // Присоединение к левому поддереву предка:

     parent->left  = р; 
else // Присоединение к правому поддереву предка:

     parent->right = р;

     }

     else {      // Узел существует, добавление нарушения в список Fine* temp = p->beg;

     while (temp->next) temp = temp->next; // Поиск конца списка

      temp->next = pf;

     }

     return p;

     }

     //   Вывод базы в файл

     void write_dbase(ofstream f, const Node *p) {

     if (P) {

     write_node(f, *p);

      write_dbase (f. p->left);

     write_dbase (f, p->right);

     }

     }

     //  Вывод в файл сведений об а/м

     void write_node(ofstream f, const NodeS node) {

     f << node.number << endl;

     Fine* pf = node.beg;

     while(pf) {

     f << pf->time << endl << pf->type << endl << pf->price << endl;

      pf = pf->next;

     }

     f << "=" « endl;   // Признак окончания сведений об а/м

     } 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

     Заключение 
 

     В данной работе в теоретической части были рассмотрены способы построения и представления деревьев. Более глубоко и подробно были рассмотрены основные операции над деревьями. Рассмотрено понятие «леса», преобразование его в бинарное дерево.

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

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

     

1. Хусаинов  Б.С. «Структуры и алгоритмы обработки  данных»: Учеб.пособие. – Финансы  и статистика, 2004.-464с.:ил.
2. В.В.Подбельский, С.С.Фомин «Язык Си++». – М.: Финансы и статистика, 2003.
3. Павловская Т.А., Щупак Ю.А. С/С++. Структурное программирование (практикум). – Спб.: Пи-тер, 2004.
4. Культин Н. С/С++ в задачах и примерах.. БХВ – Петербург, 2004.
5. Фридман А., Кландер Л. И др. С/С++. Алгоритмы и примеры. М. Бином, 2003.