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

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

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

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

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

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

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

ЛАБОРАТОРНАЯ РАБОТА 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 с.