Сортировка с помощью бинарного дерева (Tree_sort)

[Все сортировки]

Теория: Общая информация изложена здесь

Практика: informatics.mccme.ru

Реализация:

В своей реализации эта сортировка использует структуру данных: бинарное дерево, каждый элемент которого можно описать следующим образом:

1. struct tree
2. {
3.   tree* left; // левый сын
4.   tree* right; // правый сын
5.   int value;  // значение
6. };

* This source code was highlighted with Source Code Highlighter.

Само бинарное дерево удобно формировать по мере поступления новых данных, например при считывании данных из файла или с консоли.

Каждый элемент дерева соответствует двум правилам:
1. Значение левого сына строго меньше значения родителя
2. Значение правого сына не меньше значения родителя

При добавлении нового элемента в дерево происходит его просейка вниз, начиная с корня по следующим правилу:
Если новый элемент меньше текущего узла, то перенаправляем его в левое поддерево, иначе в правое. Повторяем этот шаг до тех пор, пока не окажемся в пустом листе дерева. Это и будет место нового элемента.

Проилюстрируем это следующими функциями:

1. void add_to_tree(tree* &node, int value)
2. {
3.   if (node == NULL)
4.   {
5.     node = new tree(value);
6.     return;
7.   }
8.   if (node->value > value)
9.     add_to_tree(node->left,value);
10.   else
11.     add_to_tree(node->right,value);
12. }
13. void input_tree(tree* &root)
14. {
15.   cin>>n;
16.   for (int i=0;i<n;i++)
17.   {
18.     scanf("%d",&value);
19.     add_to_tree(root,value);
20.   }
21. }

* This source code was highlighted with Source Code Highlighter.

После того, как дерево сформировано, осталось вывести ответ.
Если организовать обход по правилу:
левый сын – родитель – правый сын
и последовательно выводить значения родителя, то получим отсортированный массив:

1. void output_tree(tree* node)
2. {
3.   if (node == NULL)
4.     return;
5.   output_tree(node->left);
6.   printf("%d ",node->value);
7.   output_tree(node->right);
8. }

* This source code was highlighted with Source Code Highlighter.

Полный исходник лежит здесь

Как видно на каждый элемент входного массива в дереве тратиться дополнительно 8 байт на указатели на сыновей. Этот дополнительный расход памяти делает этот метод менее привлекательным. Но тем не менее саму идею использования дерева можно применить в других прикладных задачах.