Сортировка с помощью дерева

Алгоритмы сортировки и поиска / Сортировка с помощью дерева

 

Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.

Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

  • оба поддерева – левое и правое, являются двоичными деревьями поиска;
  • у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
  • у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.

Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.

Для сортировки с помощью дерева исходная сортируемая  последовательность представляется в виде структуры данных "дерево".

Например, исходная последовательность имеет вид:

4, 3, 5, 1, 7, 8, 6, 2

Корнем дерева будет начальный элемент последовательности. Далее все элементы, меньшие корневого, располагаются в левом поддереве, все элементы, большие корневого, располагаются в правом поддереве. Причем это правило должно соблюдаться на каждом уровне.

После того, как все элементы размещены в структуре "дерево", необходимо вывести их, используя инфиксную форму обхода.
Бинарное дерево

Реализация сортировки с помощью дерева на C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
using namespace std;
// Структура - узел дерева
struct tnode
{
  int field; // поле данных
  struct tnode *left; // левый потомок
  struct tnode *right; // правый потомок
};
// Вывод узлов дерева (обход в инфиксной форме)
void treeprint(tnode *tree)
{
  if (tree != NULL) {      //Пока не встретится пустой узел
    treeprint(tree->left); //Рекурсивная функция вывода левого поддерева
    cout << tree->field << " "; //Отображаем корень дерева
    treeprint(tree->right); //Рекурсивная функция вывода правого поддерева
  }
}
// Добавление узлов в дерево
struct tnode * addnode(int x, tnode *tree) {
  if (tree == NULL) // Если дерева нет, то формируем корень
  {
    tree = new tnode; //память под узел
    tree->field = x; //поле данных
    tree->left = NULL;
    tree->right = NULL; //ветви инициализируем пустотой
  }
  else // иначе
    if (x < tree->field) //Если элемент x меньше корневого, уходим влево
      tree->left = addnode(x, tree->left); //Рекурсивно добавляем элемент
    else //иначе уходим вправо
      tree->right = addnode(x, tree->right); //Рекурсивно добавляем элемент
    return(tree);
}
//Освобождение памяти дерева
void freemem(tnode *tree)
{
  if (tree != NULL)    // если дерево не пустое
  {
    freemem(tree->left); // рекурсивно удаляем левую ветку
    freemem(tree->right); // рекурсивно удаляем правую ветку
    delete tree; // удаляем корень
  }
}
// Тестирование работы
int main()
{
  struct tnode *root = 0;    // Объявляем структуру дерева
  system("chcp 1251");    // переходим на русский язык в консоли
  system("cls");
  int a;            // текущее значение узла
  // В цикле вводим 8 узлов дерева
  for (int i = 0; i< 8; i++)
  {
    cout << "Введите узел " << i + 1 << ": ";
    cin >> a;
    root = addnode(a, root); // размещаем введенный узел на дереве
  }
  treeprint(root);    // выводим элементы дерева, получаем отсортированный массив
  freemem(root);      // удаляем выделенную память
  cin.get(); cin.get();
  return 0;
}


Результат выполнения
Результат сортировки с помощью дерева


Назад: Алгоритмы сортировки и поиска

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *