(精华)2020年8月28日 数据结构与算法解析(二叉树排序)

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();
    }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

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();
    }

}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
 

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

文章来源: codeboy.blog.csdn.net，作者：愚公搬代码，版权归原作者所有，如需转载，请联系作者。

原文链接：codeboy.blog.csdn.net/article/details/108279119