Microbubu的迷你实验室

二叉排序/搜索/查找树及遍历

C# 数据结构与算法
字数统计: 309阅读时长: 1 min
2018/11/09 Share

二叉排序树（搜索/查找树）描述：

  1. 是一个二叉树；
  2. 对于任意一个节点N，其左子树节点的值均小于N节点的值。同理，其右子树节点的值均大于或等于N节点的值。

使用面向对象语言实现二叉树要比过程化的C语言更加简单（递归思想）：

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
43
44
45
46
47
48
49
50
51
52
53
54
55
public class BinaryTree<T> where T:IComparable
{
    private T Data;
    private BinaryTree<T> LeftTree;
    private BinaryTree<T> RightTree;

    public BinaryTree(T val)
    {
        Data = val;
        LeftTree = null;
        RightTree = null;
    }

    //插入元素，生成一个二叉排序树
    public void Insert(T val)
    {
        if (Data.CompareTo(val) > 0)
        {
            if (LeftTree == null)
                LeftTree = new BinaryTree<T>(val);
            else
                LeftTree.Insert(val);
        }
        else
        {
            if (RightTree == null)
                RightTree = new BinaryTree<T>(val);
            else
                RightTree.Insert(val);
        }
    }

    //查找
    public BinaryTree<T> Search(T val)
    {
        if (this == null) return this;
        if (val.CompareTo(this.Data) < 0)
            return this.LeftTree.Search(val);
        else if (val.CompareTo(this.Data) > 0)
            return this.RightTree.Search(val);
        else return this;
    }

    //先序遍历(LDR，左中右)
    public void Traverse()
    {
        if (LeftTree != null)
            LeftTree.Traverse();

        Console.WriteLine(Data.ToString());

        if (RightTree != null)
            RightTree.Traverse();
    }
}

测试:

1
2
3
4
5
6
7
var bTree = new BinaryTree<int>(2);
bTree.Insert(1);
bTree.Insert(4);
bTree.Insert(3);
bTree.Insert(5);
bTree.Traverse();
Console.ReadKey();

这段测试代码生成的二叉排序树如下图：

二叉树

结果:

1
2
3
4
5
1
2
3
4
5

原文作者：Microbubu Groner

原文链接：https://microbubu.github.io/2018/11/09/二叉排序-搜索-查找树及遍历/

发表日期：November 9th 2018, 9:10:07 pm

更新日期：November 13th 2018, 7:43:10 pm

版权声明：本文采用知识共享署名-非商业性使用 4.0 国际许可协议进行许可

CATALOG
Total : 11
2019
2018
PLC Markdown C# 数据结构与算法 OneDrive 图床 .NetCore WebApi PetaPoco 面试题 Python Map Reduce Kotlin 集合 Linux