Сортування бінарним деревом

Сортування бінарним деревом (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(List<int> elements = null)
        {
            if (elements == null)
            {
                elements = new List<int>();
            }

            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 = ");
            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("Вхідний масив: {0}", string.Join(" ", a));

            Console.WriteLine("Впорядкований масив: {0}", string.Join(" ", TreeSort(a)));
        }
    }
}