1、二叉树排序
二叉树排序是构建在二叉排序树（Binary Sort Tree）上的算法，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树。二叉树排序需要先生成一个二叉排序树，再使用中序遍历输出所有数据。
1.1 算法描述
二叉树排序是构建在二叉排序树（Binary Sort Tree）上的算法，二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
左、右子树也分别为二叉排序树。
二叉树排序需要先生成一个二叉排序树，再使用中序遍历输出所有数据。
1.2 图片演示
1.3 代码实现
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();
}
}
二叉树排序算法的时间复杂度为：O(n*logn) 。
