C#语言生成一个二叉排序树

小明爱学习

发布于 2020-01-21 11:17:26

8110

发布于 2020-01-21 11:17:26

相信大家都知道二叉树，今天我们来使用C#语言来生成一个二叉排序树。

我们先来看看二叉排序树的定义（来自百度百科）：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3）左、右子树也分别为二叉排序树；（4）没有键值相等的节点。

二叉排序树，其实很简单，有一个根节点，如果有左节点，左节点必须小于根节点的值；

右节点则必须大于根节点的值，没有相同值的节点，请看下图(图片来源百度百科)：

这里的根节点是8，左子树是3，右子树是10，接下来的数据都是符号一个二叉排序树的规则的，这就是一个二叉排序树。

接下来我们就用代码来实现一个二叉排序树。

我们先新建一个类，名为Tree

using System;
using System.Collections.Generic;
using System.Linq;
using System.Web;

/// <summary>
/// Tree 的摘要说明
/// </summary>
public class Tree
{
    public Tree(int key)
    {
        this.key = key;
        this.LeftTree = null;
        this.RightTree = null;
    }
    public Tree()
    {

    }
    public int key { get; set; }
    public Tree LeftTree { get; set; }
    public Tree RightTree { get; set; }
}

接下来我们来写实现二叉树。

public partial class _Default : System.Web.UI.Page
{
    public Tree root = null;
    protected void Page_Load(object sender, EventArgs e)
    {
        Tree node = new Tree();
        int[] sz = new int[] { 8,5,6,11,10,17,16,15};//构成二叉树的数组
        foreach (var item in sz)
        {
            Insert(item);
        }
        string d = JsonConvert.SerializeObject(root);//序列化二叉树以json形式输出
        Response.Write(d);
    }
    public void Insert(int key)
    {
        Tree node = new Tree(key);
        if (root == null)
        {
            root = node;
        }
        else
        {
            InsertNode(root,node);
        }
    }
    public void InsertNode(Tree node,Tree newNode)
    {
        if (newNode.key < node.key)
        {
            if (node.LeftTree == null)
            {
                node.LeftTree = newNode;
            }
            else
            {
                InsertNode(node.LeftTree,newNode);
            }
        }
        else
        {
            if (node.RightTree == null)
            {
                node.RightTree = newNode;
            }
            else
            {
                InsertNode(node.RightTree, newNode);
            }
        }
    }
}

代码我就不多详述，相信大家都能看懂，我们来看输出的结果吧。