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

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

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

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

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

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

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

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

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

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

Реализация сортировки с помощью дерева
#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;
  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 не будет опубликован. Обязательные поля помечены *