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

  При добавлении в дерево нового элемента его последовательно сравнивают
с нижестоящими узлами, таким образом вставляя на место.
  Если элемент >= корня - он идет в правое поддерево, сравниваем его уже
с правым сыном, иначе - он идет в левое поддерево, сравниваем с левым,
и так далее, пока есть сыновья, с которыми можно сравнить.

 Вот процесс построения дерева из последовательности 44 55 12 42 94 18 06 67:
   44      44         44          44          44
            \        /  \        /  \        /  \
            55      12  55      12  55      12  55
                                  \           \   \ 
                                   42        42   94

(**) 44              44         (*) 44
    /  \            /  \           /  \
   12  55          12  55         12   55
     \   \        /  \   \       /  \   \ 
     42  94      06  42  94     06  42   94
     /               /              /    / 
   18             18             18    67

 Дерево может быть и более-менее ровным, как на (*), может и иметь всего
две основные ветви (**), а если входная последовательность уже отсортирована,
то дерево выродится в линейный список.

Если мы будем рекурсивно обходить дерево по правилу
"левый сын - родитель - правый сын", то, записывая все 
встречающиеся элементы в массив, мы получим упорядоченное 
в порядке возрастания множество. Hа этом и основана идея сортировки деревом.	

Более подробно правило обхода можно сформулировать как
  обойти левое поддерево - вывести корень - обойти правое поддерево,
где рекурсивная процедура 'обойти' вызывает себя еще раз, если сталкивается
с узлом-родителем и выдает очередной элемент, если у узла нет сыновей.

/*********** сортировка с помощью двоичного дерева *************/
#include <stdio.h>
#include <stdlib.h>

typedef struct tree
  {
    int a;              // данные
    struct tree *left;  // левый  сын
    struct tree *right; // правый сын
  } TREE;

TREE *add_to_tree(TREE *root, int new_value)
{
   if (root==NULL)  // если нет сыновей - создаем новый элемент
     {
        root = (TREE*)malloc(sizeof(TREE));
        root->a = new_value;
        root->left = root->right = 0;
        return root;
     }
   if (root->a < new_value)          // добавлем ветвь
     root->right = add_to_tree(root->right, new_value);
   else
     root->left  = add_to_tree(root->left,  new_value);
   return root;
}

void tree_to_array(TREE *root, int a[]) // процедура заполнения массива
  {
    static max2=0;                      // счетчик элементов нового массива
    if (root==NULL) return;             // условие окончания - нет сыновей
    tree_to_array(root->left, a);       // обход левого поддерева
    a[max2++] = root->a;
    tree_to_array(root->right, a);      // обход правого поддерева
    free(root);
  }

void sort_tree(int a[], int elem_total)        // собственно сортировка
{
   TREE *root;
   int i;

   root = NULL;
   for (i=0; i<elem_total; i++)        // проход массива и заполнение дерева
      root = add_to_tree(root, a[i]);
   tree_to_array(root, a);             // заполнение массива
}
  /* тестовая программа */
void main() {
   int i;
   /* Это будем сортировать */
   int a[14]={ 0,7,8,3,52,14,16,18,15,13,42,30,35,26 };

   sort_tree(a, 14);
   
   printf("sorted array:\n");
   for (i=0;i<14;i++) printf("%d ",a[i]);   
}
 								   
   Общее быстродействие метода O(nlogn). Поведение неестественно,
 устойчивости, вообще говоря, нет.

  Основной недостаток этого метода - большие требования к памяти
под дерево. Очевидно, нужно n места под ключи и, кроме того, память
на 2 указателя для каждого из них.

 Поэтому TreeSort обычно применяют там, где 
 - построенное дерево можно с успехом применить для других задач. 
 - данные уже построены в 'дерево'.                     } не тратится
 - данные можно считывать непосредственно в дерево.     }  лишняя
 Hапример, при потоковом вводе с консоли или из файла.  }  память
     
   Кроме того, ее элементы иногда используются в смежных задачах.
   
> Другое описание метода 'древесной сортровки' можно найти, например,
> у H. Вирта в книге 'Алгоритмы + Структуры Данных = Программы'.

   Основное различие - строится не представление данных в виде дерева,
а 'дерево выбора'. С помощью n/2 сравнений можно определить
наименьший элемент из каждой пары, при помощи следующих n/4 -
наименьший из каждой пары таких наименьших ключей и т.д
   При этом за n-1 сравнений мы можем построить дерево выбора, как 
показано для чисел 44 55 12 42 94 18 06 67:
               
                      06         Это HЕ двоичное дерево в смысле, 
                     /  \           определенном выше.
                    /    \       И это HЕ пирамида, используемая в HeapSort 
                   /      \                
                  /        \                
                 /          \            
                /            \
               12            06       Hа втором шаге мы спускаемся по 
              / \            / \       пути, указанному наименьшим ключом
             /   \          /   \      и исключаем его, последовательно 
            /     \        /     \      заменяя либо на 'дыру' (или ключ 
          44      12     18      06     'бесконечность'(БЕСК), либо на элемент,
         /  \    /  \    / \     / \     находящийся на противоположной
        44  55  12  42  94 18   06 67     ветви промежуточного узла:

     взяли ключ 06 сверху      опять выбрали наименьший с учетом, что любой
             БЕСК                              12           ключ < БЕСК.                
             /  \                             /  \                      
            /    \                           /    \     
           /      \                         /      \                 
          /        \                       /        \                
         /          \                     /          \            
        /            \                   /            \
       12            БЕСК               12            18        
      / \            / \               / \            / \        
     /   \          /   \             /   \          /   \       
    /     \        /     \           /     \        /     \       
  44      12     18     БЕСК       44      12     18      67     
 /  \    /  \    / \     / \      /  \    /  \    / \     / \   
44  55  12  42  94 18 БЕСК 67    44  55  12  42  94 18 БЕСК 67    

  Очевидно, требуется n операций на создание первоначального дерева,
 а затем n шагов, каждый по log n сравнений для выбора нового наименьшего.
                               2 		
  Такой вариант TreeSort довольно сильно отличается от изложенного выше.
Этот алгоритм еще называют 'выбор с замещением' и его можно неплохо 
применять в тех же случаях, что и выше. 

При этом он может быть даже выгоднее предыдущего метода,
хотя бы потому, что не нужно запоминать позицию, на которой мы остановились
при обходе дерева, т.е можно взять верхний элемент -> восстановить дерево ->
проделать некоторые операции -> взять следующий элемент и т.п.  
Обходить же дерево удобно сразу целиком, либо какую-то его большую часть.
Кроме того, самой структура дерева выбора также может быть полезна.
   
   Однако, нужно учесть, что памяти для дерева выбора нужно на
2n-1 элементов (элемент = ключ + указатели), в отличие от n элементов для 
простого дерева. 
   
  Пример использования выбора с замещением можно увидеть в
многофазной сортировке (см соответствующий вопрос). Элементы обоих 
'древесных' сортировок также используются в смежных