C#算法设计排序篇之11-二叉树排序(附带动画演示程序)

二叉树排序是构建在二叉排序树(Binary Sort Tree)上的算法,二叉排序树或者是一棵空树,或者是具有下列性质的二叉树。二叉树排序需要先生成一个二叉排序树,再使用中序遍历输出所有数据。

C#算法设计排序篇之11-二叉树排序(附带动画演示程序)

C#算法设计概述

二叉树排序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

分析

二叉树排序算法的时间复杂度为:O(n*logn)

AlgorithmMan

C#算法设计排序篇之11-二叉树排序(附带动画演示程序)

AlgorithmMan by Iori,AlgorithmMan是使用C#开发的一套用于算法演示的工具。

GitHub下载地址:https://github.com/byteflying/AlgorithmManRelease

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/695

发表评论

登录后才能评论