Сортировка массива двоичным деревом

Сортировка бинарным деревом

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

Принцип работы алгоритма сортировки бинарным деревом

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

Реализация алгоритма сортировки бинарным деревом

using System; using System.Collections.Generic; namespace TreeSortApp < //простая реализация бинарного дерева public class TreeNode < public TreeNode(int data) < Data = data; >//данные public int Data < get; set; > //левая ветка дерева public TreeNode Left < get; set; > //правая ветка дерева public TreeNode Right < get; set; > //рекурсивное добавление узла в дерево public void Insert(TreeNode node) < if (node.Data < Data) < if (Left == null) < Left = node; >else < Left.Insert(node); >> else < if (Right == null) < Right = node; >else < Right.Insert(node); >> > //преобразование дерева в отсортированный массив public int[] Transform(Listint> elements = null) < if (elements == null) < elements = new Listint>(); > if (Left != null) < Left.Transform(elements); >elements.Add(Data); if (Right != null) < Right.Transform(elements); >return elements.ToArray(); > > class Program < //метод для сортировки с помощью двоичного дерева private static int[] TreeSort(int[] array) < var treeNode = new TreeNode(array[0]); for (int i = 1; i < array.Length; i++) < treeNode.Insert(new TreeNode(array[i])); > return treeNode.Transform(); > static void Main(string[] args) < Console.Write("n hljs-keyword">var n = int.Parse(Console.ReadLine()); var a = new int[n]; var random = new Random(); for (int i = 0; i < a.Length; i++) < a[i] = random.Next(0, 100); > Console.WriteLine("Random Array: ", string.Join(" ", a)); Console.WriteLine("Sorted Array: ", string.Join(" ", TreeSort(a))); > > > 

Источник

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

Сортировка с помощью дерева осуществляется на основе бинарного дерева поиска.

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

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

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

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

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

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

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

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

Реализация сортировки с помощью дерева на C++

#include
using namespace std;
// Структура — узел дерева
struct tnode
int field; // поле данных
struct tnode *left; // левый потомок
struct tnode *right; // правый потомок
>;
// Вывод узлов дерева (обход в инфиксной форме)
void treeprint(tnode *tree)
if (tree != NULL ) < //Пока не встретится пустой узел
treeprint(tree->left); //Рекурсивная функция вывода левого поддерева
cout 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 < 8; i++)
cout cin >> a;
root = addnode(a, root); // размещаем введенный узел на дереве
>
treeprint(root); // выводим элементы дерева, получаем отсортированный массив
freemem(root); // удаляем выделенную память
cin.get(); cin.get();
return 0;
>

Результат выполнения

Комментариев к записи: 3

Источник

Сортировка бинарным деревом

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

Принцип работы алгоритма сортировки бинарным деревом

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

Реализация алгоритма сортировки бинарным деревом

using System; using System.Collections.Generic; namespace TreeSortApp < //простая реализация бинарного дерева public class TreeNode < public TreeNode(int data) < Data = data; >//данные public int Data < get; set; > //левая ветка дерева public TreeNode Left < get; set; > //правая ветка дерева public TreeNode Right < get; set; > //рекурсивное добавление узла в дерево public void Insert(TreeNode node) < if (node.Data < Data) < if (Left == null) < Left = node; >else < Left.Insert(node); >> else < if (Right == null) < Right = node; >else < Right.Insert(node); >> > //преобразование дерева в отсортированный массив public int[] Transform(Listint> elements = null) < if (elements == null) < elements = new Listint>(); > if (Left != null) < Left.Transform(elements); >elements.Add(Data); if (Right != null) < Right.Transform(elements); >return elements.ToArray(); > > class Program < //метод для сортировки с помощью двоичного дерева private static int[] TreeSort(int[] array) < var treeNode = new TreeNode(array[0]); for (int i = 1; i < array.Length; i++) < treeNode.Insert(new TreeNode(array[i])); > return treeNode.Transform(); > static void Main(string[] args) < Console.Write("n hljs-keyword">var n = int.Parse(Console.ReadLine()); var a = new int[n]; var random = new Random(); for (int i = 0; i < a.Length; i++) < a[i] = random.Next(0, 100); > Console.WriteLine("Random Array: ", string.Join(" ", a)); Console.WriteLine("Sorted Array: ", string.Join(" ", TreeSort(a))); > > > 

Источник