三沣开发知识 购物 网址 游戏 小说 歌词 地图 快照 股票 美女 新闻 笑话 | 汉字 软件 日历 阅读 下载 图书馆 开发 租车 短信 China
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题
autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程 CSS/HTML/Xhtml
html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
站长资讯 .NET新手 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA VisualStudio ASP.NET-MVC .NET控件开发 EntityFramework WinRT-Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动 Html-Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP OracleERP DynamicsCRM K2 BPM 信息安全 企业信息 Android开发 iOS开发 WindowsPhone WindowsMobile 其他手机 敏捷开发 项目管理 软件工程 SQLServer Oracle MySQL NoSQL 其它数据库 Windows7 WindowsServer Linux
  IT知识库 -> .NET新手区 -> 了解集合本质必须要知晓的概念04 -> 正文阅读
 

[.NET新手区]了解集合本质必须要知晓的概念04

了解集合本质必须要知晓的概念04 与链表、堆栈和队列不一样,二叉查找树不是线性数据结构,是二维数据结构。每个节点都包含一个LeftNode和RightNode,二叉查找树把比节点数据项小的数据放在LeftNode,把比节点数据项大的数据放在RightNode。
关于节点的类。

    public class TreeNode<T>


    {


        public T Element { get; set; }


        public TreeNode<T>  LeftNode { get; set; }


        public TreeNode<T>  RightNode { get; set; }


        public TreeNode(T element)


        {


            this.Element = element;


            LeftNode = RightNode = null;


        }


        public override string ToString()


        {


            string nodeString = "[" + this.Element + " ";


            if (this.LeftNode == null && this.RightNode == null)


            {


                nodeString += " (叶节点) ";


            }


            if (this.LeftNode != null)


            {


                nodeString += "左节点:" + this.LeftNode.ToString();


            }


            if (this.RightNode != null)


            {


                nodeString += "右节点:" + this.RightNode.ToString();


            }


            nodeString += "]";


            return nodeString;


        }


    }

以上,把比节点数据项Element小的数据所在节点赋值给LeftNode,把比节点数据项Element大的数据所在节点赋值给RightNode。
创建一个泛型二叉树查找类,维护着一个根节点,并提供各种对节点的操作方法。

    public class BinarySearchTree<T>


    {


        public TreeNode<T> Root { get; set; }


        public BinarySearchTree()


        {


            this.Root = null;


        }


        //把某个数据项插入到二叉树


        public void Insert(T x)


        {


            this.Root = Insert(x, this.Root);


        }


        //把某个数据项从二叉树中删除


        public void Remove(T x)


        {


            this.Root = Remove(x, this.Root);


        }


        //删除二叉树中的最小数据项


        public void RemoveMin()


        {


            this.Root = RemoveMin(this.Root);


        }


        //获取二叉树中的最小数据项


        public T FindMin()


        {


            return ElemntAt(FindMin(this.Root));


        }


        //获取二叉树中的最大数据项


        public T FindMax()


        {


            return ElemntAt(FindMax(this.Root));


        }


        //获取二叉树中的某个数据项


        public T Find(T x)


        {


            return ElemntAt(Find(x, this.Root));


        }


        //清空


        public void MakeEmpty()


        {


            this.Root = null;


        }


        //判断二叉树是否为空,是否存在


        public bool IsEmpty()


        {


            return this.Root == null;


        }


        //获取某个节点的数据项


        private T ElemntAt(TreeNode<T> t)


        {


            return t == null ? default(T) : t.Element;


        }


        /// <summary>


        /// 查找节点


        /// </summary>


        /// <param name="x">要查找数据项</param>


        /// <param name="t">已存在的节点</param>


        /// <returns>返回节点</returns>


        private TreeNode<T> Find(T x, TreeNode<T> t)


        {


            while (t != null)//当没有找到匹配数据项,不断调整查找范围,即t的值


            {


                if ((x as IComparable).CompareTo(t.Element) < 0)


                {


                    t = t.LeftNode;


                }


                else if ((x as IComparable).CompareTo(t.Element) > 0)


                {


                    t = t.RightNode;


                }


                else //如果找到数据项,就返回当前t的值


                {


                    return t;


                }


            }


            return null;


        }


        //获取最小的节点,


        private TreeNode<T> FindMin(TreeNode<T> t)


        {


            if (t != null)


            {


                while (t.LeftNode != null)//不断循环二叉树的左半边树


                {


                    t = t.LeftNode; //不断设置t的值


                }


            }


            return t;


        }


        //获取最大的节点


        private TreeNode<T> FindMax(TreeNode<T> t)


        {


            if (t != null)


            {


                while (t.RightNode != null)


                {


                    t = t.RightNode;


                }


            }


            return t;


        }


        /// <summary>


        /// 插入节点


        /// </summary>


        /// <param name="x">要插入的数据项</param>


        /// <param name="t">已经存在的节点</param>


        /// <returns>返回已存在的节点</returns>


        protected TreeNode<T> Insert(T x, TreeNode<T> t)


        {


            if (t == null)


            {


                t = new TreeNode<T>(x);


            }


            else if ((x as IComparable).CompareTo(t.Element) < 0)


            {


                //等号右边的t.LeftNode是null,因此会创建一个TreeNode实例给t.LeftNode


                t.LeftNode = Insert(x, t.LeftNode);


            }


            else if ((x as IComparable).CompareTo(t.Element) > 0)


            {


                t.RightNode = Insert(x, t.RightNode);


            }


            else


            {


                throw new Exception("插入了相同元素~~");


            }


            return t;


        }


        //删除最小的节点


        //返回当前根节点


        protected TreeNode<T> RemoveMin(TreeNode<T> t)


        {


            if (t == null)


            {


                throw new Exception("节点不存在~~");


            }


            else if (t.LeftNode != null)


            {


                //通过递归不断设置t.LeftNode,直到t.LeftNode=null


                t.LeftNode = RemoveMin(t.LeftNode);


                return t;


            }


            else //当t.LeftNode=null的时候,就把t.RightNode当作最小节点返回


            {


                return t.RightNode;


            }


        }


        //删除某数据项,返回当前根节点


        protected TreeNode<T> Remove(T x, TreeNode<T> t)


        {


            if (t == null)


            {


                throw new Exception("节点不存在~~");


            }


            else if((x as IComparable).CompareTo(t.Element) < 0)


            {


                t.LeftNode = Remove(x, t.LeftNode);


            }


            else if ((x as IComparable).CompareTo(t.Element) > 0)


            {


                t.RightNode = Remove(x, t.RightNode);


            }


            else if (t.LeftNode != null && t.RightNode != null)


            {


                t.Element = FindMin(t.RightNode).Element;


                t.RightNode = RemoveMin(t.RightNode);


            }


            else


            {


                t = (t.LeftNode != null) ? t.LeftNode : t.RightNode;


            }


            return t;


        }


        public override string ToString()


        {


            return this.Root.ToString();


        }


    }

客户端创建二叉查找树的实例,并调用实例方法插入随机数据。

            BinarySearchTree<int> intTree = new BinarySearchTree<int>();


            Random r = new Random(DateTime.Now.Millisecond);


            string trace = "";


            //插入5个随机数


            for (int i = 0; i < 5; i++)


            {


                int randomInt = r.Next(1, 500);


                intTree.Insert(randomInt);


                trace += randomInt + " ";


            }


            Console.WriteLine("最大的节点:" + intTree.FindMax());


            Console.WriteLine("最小的节点:" + intTree.FindMin());


            Console.WriteLine("根节点:" + intTree.Root.Element);


            Console.WriteLine("插入节点的依次顺序是:" + trace);


            Console.WriteLine("打印树为:" + intTree);


            Console.ReadKey();


参考资料:
Binary Search Trees (BSTs) in C#
“了解集合本质必须要知晓的概念”系列包括:
了解集合本质必须要知晓的概念01-链表 了解集合本质必须要知晓的概念02-堆栈 了解集合本质必须要知晓的概念03-队列 了解集合本质必须要知晓的概念04-二叉查找树
  .NET新手区 最新文章
2017年10月21日 CSS常用样式&鼠标样式
EventLog组件读写事件日志
Visual Studio 2017 系统发布部署服务器教程
多线程编程学习笔记
如何在已有项目中引入FineUIMvc
多线程编程学习笔记
WebAPI搭建(二) 让WebAPI 返回JSON格式的
Linq中Take、TakeWhile、Skip、SkipWhile的
[C#] C# 基础回顾
page.ClientScript.RegisterStartupScript
上一篇文章      下一篇文章      查看所有文章
加:2015-03-29 20:35:22  更:2017-05-14 05:18:23 
 
技术频道: 站长资讯 .NET新手区 ASP.NET C# WinForm Silverlight WCF CLR WPF XNA Visual Studio ASP.NET MVC .NET控件开发 Entity Framework WinRT/Metro Java C++ PHP Delphi Python Ruby C语言 Erlang Go Swift Scala R语言 Verilog 其它语言 架构设计 面向对象 设计模式 领域驱动设计 Html/Css JavaScript jQuery HTML5 SharePoint GIS技术 SAP Oracle ERP Dynamics CRM K2 BPM 信息安全 企业信息化其他 Android开发 iOS开发 Windows Phone Windows Mobile 其他手机开发 敏捷开发 项目与团队管理 软件工程其他 SQL Server Oracle MySQL NoSQL 其它数据库 Windows 7 Windows Server Linux
脚本语言: vbs/VBScript DOS/BAT hta htc python perl 游戏相关 VBA 远程脚本 ColdFusion ruby专题 autoit seraphzone PowerShell linux shell Lua Golang Erlang 其它教程
网站开发: CSS/HTML/Xhtml html5 CSS XML/XSLT Dreamweaver教程 经验交流 开发者乐园 Android开发资料
360图书馆 软件开发资料 文字转语音 购物精选 软件下载 美食菜谱 新闻资讯 电影视频 小游戏 Chinese Culture 股票 租车
生肖星座 三丰软件 视频 开发 短信 中国文化 网文精选 搜图网 美图 阅读网 多播 租车 短信 看图 日历 万年历 2017年10日历
2017-10-22 7:16:00
多播视频美女直播
↓电视,电影,美女直播,迅雷资源↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT知识库