专栏首页smh的技术文章C#语言生成一个二叉排序树

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

相信大家都知道二叉树,今天我们来使用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);
            }
        }
    }
}

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

这里输出的json形式的二叉树,但是看着有点炸眼,我们用json格式化工具来显示一下吧,

我们来看看我们的原始数组{ 8,5,6,11,10,17,16,15}

首先8是根节点,5小于8,为8的左节点,6还是小于8,还是为左节点,但是左节点已经有值了,就是第二个元素5,所以元素6就分配到节点5的右结点下了,因为6大于5。

到第四个元素11,由于11大于根节点8,由于右节点还没有值,所以11就成了8的右节点。

以此类图就构成了一颗二叉排序树。可看代码中的处理方式。主要是利用递归的方式来构成。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Web.config中httpModules和httpHandlers的相关配置说明

    配置Modules和Handlers的时候,根据不同IIS的版本和应用程序池中不同的托管管道模式,在Web.config中也有不同的配置方式。

    从此null
  • Jquery源码分析:初始化Jquery函数

    今天我们来分析一下jquery的源码,从关于初始化jquery这个函数开始。版本:3.4.1

    从此null
  • IHttpAsyncHandler实现广播功能

    IHttpAsyncHandler实现广播功能原理:第一次页面加载,发送一个请求到服务器,服务器挂起这个请求,等到有数据之后在返回这个请求,就实现了服务器主动推...

    从此null
  • 【php设计模式】组合模式

      是用于把一组相似的对象当作一个单一的对象。组合模式依据树形结构来组合对象,用来表示部分以及整体层次。这种类型的设计模式属于结构型模式,它创建了对象组的树形结...

    码缘
  • 面试问红黑树,我脸都绿了。。

    红黑树是一个平衡的二叉树,但不是一个完美的平衡二叉树。虽然我们希望一个所有查找都能在~lgN次比较内结束,但是这样在动态插入中保持树的完美平衡代价太高,所以,我...

    Java技术栈
  • CreatorPrimer|飞机大战(一)

    前两天在Cocos官方公众号上学习了「大掌教」的Cocos Creator 2.x Camera教程,总算是对摄像机组件有了一个初步的认识,乘热打铁Shawn用...

    张晓衡
  • springBean内部级联

    阅读Bean官方文档的@Bean Methods in @Configuration Classes和@Bean Lite Mode小节,可了解spring对B...

    平凡的学生族
  • python算法与数据结构-二叉树的代码实现(46)

      上一篇我们对数据结构中常用的树做了介绍,本篇博客主要以二叉树为例,讲解一下树的数据结构和代码实现。回顾二叉树:二叉树是每个节点最多有两个子树的树结构。通常子...

    Se7eN_HOU
  • 【Leetcode237】关关的刷题日记 71–Leetcode237.Delete Node in a Linked List

    关关的刷题日记71 – Leetcode 237. Delete Node in a Linked List 题目 Write a function to de...

    WZEARW
  • treeview插件使用:根据子节点选中父节点

      鄙人公司没有专门的前端,所以项目开发中都是前后端一起抡。最近用bootstrap用的比较频繁,发现bootstrap除了框架本身的样式组件外,还提供了多种插...

    用户1615728

扫码关注云+社区

领取腾讯云代金券