Организация дерева поиска. Определение структуры элемента – точки на плоскости

Страницы работы

Содержание работы

Министерство образования и науки РФ

Федеральное агентство по образованию

Государственное образовательное учреждение высшего профессионального образования

 «Комсомольский-на-Амуре Государственный Технический Университет»

Факультет компьютерных технологий

Кафедра МОП ЭВМ

ЛАБОРАТОРНАЯ РАБОТА 3

по курсу «Структуры и алгоритмы обработки данных»

Выполнил:                                                                                                         Казаков М.Ю

Проверил:                                                                                                          Хусаинов А.А.

Вариант:                                                                                                            6

Комсомольск-на-Амуре

2006

Задание:     

Организовать дерево поиска. Определить структуру элемента – точка на плоскости   (x, y) и написать подпрограммы добавления, удаления и чтения элемента. Написать тестовую программу.

Алгоритм работы программы:

Структура элемента:

struct treesearch
{
  int x, y;                    // Информационная часть – координаты x и y
  treesearch *left, *right;    // Указатели на левое и правое поддерево
};

Для добавления элемента в дерево определена подпрограмма                                 treesearch *insert(treesearch *root, int x, int y), которая

- если root == NULL, то выделяет память под новый узел дерева и устанавливает его информационную часть root->x = x и root->y = y;

- если x <= root->x, то вызывает себя для левого поддерева;

- если x > root->x, то вызывает себя для правого поддерева.

Для поиска элемента определена подпрограмма                                                treesearch *find(treesearch *root, int x, int y), которая

- если root->x = x и root->y = y возвращает root;

- если x <= root->x, то вызывает себя для левого поддерева;

- если x > root->x, то вызывает себя для правого поддерева.

Для удаления элемента определена подпрограмма                                            treesearch *remove(treesearch *root, int x, int y), которая ищет элемент (x, y) в дереве. Если такого элемента нет, то возвращается 0, иначе если y найденного элемента нет левого поддерева, то вместо узла root ставится узел root->right, а если левое поддерево есть, то спускаемся по его правой ветви до тех пор пока это возможно. В итоге получим указатель newroot на максимальный элемент в правом поддереве. Устанавливаем       newroot->right = root->right и root = root->left.

Текст программы:

#include <iostream.h>
#include <conio.h>
 
 
struct treesearch
{
  int x, y;
  treesearch *left, *right;
};
 
 
treesearch *insert(treesearch *root, int x, int y)
{
 
  if (root)
  {
    if (root->x >= x) root->left = insert(root->left, x, y);
    else root->right = insert(root->right, x, y);
  }
  else
  {
    root = new treesearch;
    root->left = root->right = NULL;
    root->x = x; root->y = y;
  }
  return root;
}
 
treesearch *find(treesearch *root, int x, int y)
{
  if (root)
  {
    if (root->x == x && root->y == y) return root;
    else if (root->x >= x) return find(root->left, x, y);
    else return find(root->right, x, y);
  }
  return 0;
}
 
 
void sym(treesearch *root)
{
  if (root != NULL)
  {
    sym(root->left);
    cout << root->x << " " << root->y << "     ";
    sym(root->right);
  }
}
 
void str(treesearch *root)
{
  if (root != NULL)
  {
    cout << root->x << " " << root->y << "     ";
    str(root->left);
    str(root->right);
  }
}
 
void rev(treesearch *root)
{
  if (root != NULL)
  {
    str(root->left);
    str(root->right);
    cout << root->x << " " << root->y << "     ";
  }
}
 
 
 
treesearch *remove(treesearch *root, int x, int y)
{
  if (root)
  {
    if (root->x == x && root->y == y)
    {
      treesearch *newroot;
      if (root->left)
      {
        newroot = root->left;
        while (newroot->right) newroot = newroot->right;
        newroot->right = root->right;
        treesearch *t = root->left;
        delete root;
        return t;
      }
      else
      {
        newroot = root->right;
        delete root;
        return newroot;
      }
    }
    else if (root->x >= x)
      root->left = remove(root->left, x, y);
    else
      root->right = remove(root->right, x, y);
    return root;
  }
  else return 0;
}
 
void main()
{
  clrscr();
  int i, j;
 
  treesearch *root = NULL;
 
  root = insert(root, 10, 38); root = insert(root, 21, 53);
  root = insert(root, 32, 32); root = insert(root, 23, 32);
  root = insert(root, 22, 32); root = insert(root, 15, 65);
  root = insert(root, 56, 34); root = insert(root, 53, 56);
 
  cout << "Симметричный обход:" << endl;          sym(root);
  cout << endl << "Прямой обход:" << endl;        str(root);
  cout << endl << "Обратный обход:" << endl;      rev(root);
  cout << endl;
 
  if (find(root, 22, 32)) cout << "Элемент 22 32 есть в дереве" << endl;
  else cout << "Элемента 22 32 нет в дереве" << endl;
  if (find(root, 30, 30)) cout << "Элемент 30 30 есть в дереве" << endl;
  else cout << "Элемента 30 30 нет в дереве" << endl;
 
  i = 22; j = 32; cout << endl << "Удаляем элемент: " << i << " " << j;
  root = remove(root, i, j);
  cout << endl << "Симметричный обход:" << endl; sym(root);
 
  i = 10; j = 38; cout << endl << endl << "Удаляем элемент: " << i << " " << j;
  root = remove(root, i, j);
  cout << endl << "Симметричный обход:" << endl; sym(root);
 
 
 
  cout << endl;
}
 
 
 
 
 
 

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

                         

Список использованных источников:

1.  Хусаинов А.А., Михайлова Н.Н. Структуры и алгоритмы обработки данных: Учеб. пособие. – Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т, 2002. – 89 с.

Похожие материалы

Информация о работе