Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными (бинарными) деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X.
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Для сортировки с помощью дерева исходная сортируемая последовательность представляется в виде структуры данных «дерево».
Например, исходная последовательность имеет вид:
4, 3, 5, 1, 7, 8, 6, 2
Корнем дерева будет начальный элемент последовательности. Далее все элементы, меньшие корневого, располагаются в левом поддереве, все элементы, большие корневого, располагаются в правом поддереве. Причем это правило должно соблюдаться на каждом уровне.
После того, как все элементы размещены в структуре «дерево», необходимо вывести их, используя инфиксную форму обхода.
Реализация сортировки с помощью дерева на Cи
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
64
65
66
67
68
#include <stdio.h>
#include <stdlib.h>
#define SIZE 8
// Структура - узел дерева
struct tnode
{
int field; // поле данных
struct tnode* left; // левый потомок
struct tnode* right; // правый потомок
};
// Вывод узлов дерева (обход в инфиксной форме)
void treeprint(tnode* tree)
{
if (tree != NULL) //Пока не встретится пустой узел
{
treeprint(tree->left); //Рекурсивная функция вывода левого поддерева
printf("%d ", 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 < SIZE; i++)
{
printf("Введите узел %d: ", i + 1);
scanf("%d", &a);
root = addnode(a, root); // размещаем введенный узел на дереве
}
treeprint(root); // выводим элементы дерева, получаем отсортированный массив
printf("\n");
freemem(root); // удаляем выделенную память
system("pause");
return 0;
}
Результат выполнения
