Сортировка с помощью двоичного дерева (сортировка двоичным деревом, сортировка деревом, древесная сортировка, сортировка с помощью бинарного дерева, англ. tree sort) — универсальный алгоритм сортировки, заключающийся в построении двоичного дерева поиска по ключам массива (списка), с последующей сборкой результирующего массива путём обхода узлов построенного дерева в необходимом порядке следования ключей. Данная сортировка является оптимальной при получении данных путём непосредственного чтения из потока (например, файла, сокета или консоли).
Алгоритм
- Построение двоичного дерева.
- Сборка результирующего массива путём обхода узлов в необходимом порядке следования ключей.
Эффективность
Процедура добавления объекта в бинарное дерево имеет среднюю алгоритмическую сложность порядка 
При физическом развёртывании древовидной структуры в памяти требуется не менее чем 
Примеры реализации
program project1;
type
TData = integer;
TTree = ^Tree;
Tree = record
Data : TData;
Left, Right : TTree;
end;
procedure AddToTree(var T : TTree; aData : TData);
begin
If T=nil then begin
New(T);
T^.Data:=aData;
T^.Left:=nil; T^.Right:=nil;
end else If T^.Data>=aData then AddToTree(T^.Right,aData)
else AddToTree(T^.Left,aData);
end;
procedure PrintTr(T : TTree);
begin
If T = nil then exit;
PrintTr(T^.Left);
write(T^.Data:4);
PrintTr(T^.Right);
end;
function HightTr(aTree : TTree) : integer;
var MaxL : integer;
procedure Uroven(aTree : TTree; L : integer);
begin
if aTree = nil then exit;
If L > MaxL then MaxL := L;
Uroven(aTree^.Left,L+1);
Uroven(aTree^.Right,L+1);
end;
begin
MaxL := 0;
Uroven(aTree,0);
HightTr := MaxL;
end;
var
n, i : integer;
a : TData;
T : TTree;
begin
write('Number of Nodes in tree : '); readln(n);
T := nil; randomize;
for i := 1 to n do begin
a := random(51)-25;
write(a:4);
AddToTree(T,a);
end;
writeln(#10,#13,'Infix Order :');
PrintTr(T);
writeln;
writeln('Hight Tree : ',HightTr(T));
readln;
end.
Пример создания бинарного дерева и сортировки на языке Java:
// Скомпилируйте и введите java TreeSort
class Tree {
public Tree left; // левое и правое поддеревья и ключ
public Tree right;
public int key;
public Tree(int k) { // конструктор с инициализацией ключа
key = k;
}
/* insert (добавление нового поддерева (ключа))
сравнить ключ добавляемого поддерева (К) с ключом корневого узла (X).
Если K>=X, рекурсивно добавить новое дерево в правое поддерево.
Если K<X, рекурсивно добавить новое дерево в левое поддерево.
Если поддерева нет, то вставить на это место новое дерево
*/
public void insert( Tree aTree) {
if ( aTree.key < key )
if ( left != null ) left.insert( aTree );
else left = aTree;
else
if ( right != null ) right.insert( aTree );
else right = aTree;
}
/* traverse (обход)
Рекурсивно обойти левое поддерево.
Применить функцию f (печать) к корневому узлу.
Рекурсивно обойти правое поддерево.
*/
public void traverse(TreeVisitor visitor) {
if ( left != null)
left.traverse( visitor );
visitor.visit(this);
if ( right != null )
right.traverse( visitor );
}
}
interface TreeVisitor {
public void visit(Tree node);
};
class KeyPrinter implements TreeVisitor {
public void visit(Tree node) {
System.out.println( " " + node.key );
}
};
class TreeSort {
public static void main(String args[]) {
Tree myTree;
myTree = new Tree( 7 ); // создать дерево (с ключом)
myTree.insert( new Tree( 5 ) ); // присоединять поддеревья
myTree.insert( new Tree( 9 ) );
myTree.traverse(new KeyPrinter());
}
}