
二叉树排序(Binary Tree Sort)
二叉树排序是构建在二叉排序树(Binary Sort Tree)上的算法,二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
- 若左子树不空,则左子树上所有结点的值均小于或等于它的根结点的值;
- 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
- 左、右子树也分别为二叉排序树。
二叉树排序需要先生成一个二叉排序树,再使用中序遍历输出所有数据。
示例
public class BinarySortTreeNode { public int Key { get; set; } public BinarySortTreeNode Left { get; set; } public BinarySortTreeNode Right { get; set; } public BinarySortTreeNode(int key) { Key = key; } public void Insert(int key) { var tree = new BinarySortTreeNode(key); if (tree.Key <= Key) { if (Left == null) { Left = tree; } else { Left.Insert(key); } } else { if (Right == null) { Right = tree; } else { Right.Insert(key); } } } /// <summary> /// 中序遍历 /// </summary> public void InorderTraversal() { Left?.InorderTraversal(); Console.Write($"{Key} "); Right?.InorderTraversal(); } }
public class Program { public static void Main(string[] args) { int[] array = { 43, 69, 11, 72, 28, 21, 56, 80, 48, 94, 32, 8 }; BinaryTreeSort(array); Console.ReadKey(); } public static void BinaryTreeSort(int[] array) { var binarySortTreeNode = new BinarySortTreeNode(array[0]); for (int i = 1; i < array.Length; i++) { binarySortTreeNode.Insert(array[i]); } binarySortTreeNode.InorderTraversal(); } }
以上是二叉树排序算法的一种实现,以下是这个案例的输出结果:
8 11 21 28 32 43 48 56 69 72 80 94
分析
二叉树排序算法的时间复杂度为: 。
AlgorithmMan

AlgorithmMan by Iori,AlgorithmMan是使用C#开发的一套用于算法演示的工具。
GitHub下载地址:https://github.com/byteflying/AlgorithmManRelease
Dark Mode

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/695。