C#使用集合實(shí)現(xiàn)二叉查找樹(shù)
與鏈表、堆棧和隊(duì)列不一樣,二叉查找樹(shù)不是線(xiàn)性數(shù)據(jù)結(jié)構(gòu),是二維數(shù)據(jù)結(jié)構(gòu)。每個(gè)節(jié)點(diǎn)都包含一個(gè)LeftNode和RightNode,二叉查找樹(shù)把比節(jié)點(diǎn)數(shù)據(jù)項(xiàng)小的數(shù)據(jù)放在LeftNode,把比節(jié)點(diǎn)數(shù)據(jù)項(xiàng)大的數(shù)據(jù)放在RightNode。
關(guān)于節(jié)點(diǎn)的類(lèi)。
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 += " (葉節(jié)點(diǎn)) "; } if (this.LeftNode != null) { nodeString += "左節(jié)點(diǎn):" + this.LeftNode.ToString(); } if (this.RightNode != null) { nodeString += "右節(jié)點(diǎn):" + this.RightNode.ToString(); } nodeString += "]"; return nodeString; } } 以上,把比節(jié)點(diǎn)數(shù)據(jù)項(xiàng)Element小的數(shù)據(jù)所在節(jié)點(diǎn)賦值給LeftNode,把比節(jié)點(diǎn)數(shù)據(jù)項(xiàng)Element大的數(shù)據(jù)所在節(jié)點(diǎn)賦值給RightNode。 創(chuàng)建一個(gè)泛型二叉樹(shù)查找類(lèi),維護(hù)著一個(gè)根節(jié)點(diǎn),并提供各種對(duì)節(jié)點(diǎn)的操作方法。 public class BinarySearchTree<T> { public TreeNode<T> Root { get; set; } public BinarySearchTree() { this.Root = null; } //把某個(gè)數(shù)據(jù)項(xiàng)插入到二叉樹(shù) public void Insert(T x) { this.Root = Insert(x, this.Root); } //把某個(gè)數(shù)據(jù)項(xiàng)從二叉樹(shù)中刪除 public void Remove(T x) { this.Root = Remove(x, this.Root); } //刪除二叉樹(shù)中的最小數(shù)據(jù)項(xiàng) public void RemoveMin() { this.Root = RemoveMin(this.Root); } //獲取二叉樹(shù)中的最小數(shù)據(jù)項(xiàng) public T FindMin() { return ElemntAt(FindMin(this.Root)); } //獲取二叉樹(shù)中的最大數(shù)據(jù)項(xiàng) public T FindMax() { return ElemntAt(FindMax(this.Root)); } //獲取二叉樹(shù)中的某個(gè)數(shù)據(jù)項(xiàng) public T Find(T x) { return ElemntAt(Find(x, this.Root)); } //清空 public void MakeEmpty() { this.Root = null; } //判斷二叉樹(shù)是否為空,是否存在 public bool IsEmpty() { return this.Root == null; } //獲取某個(gè)節(jié)點(diǎn)的數(shù)據(jù)項(xiàng) private T ElemntAt(TreeNode<T> t) { return t == null ? default(T) : t.Element; } /// <summary> /// 查找節(jié)點(diǎn) /// </summary> /// <param name="x">要查找數(shù)據(jù)項(xiàng)</param> /// <param name="t">已存在的節(jié)點(diǎn)</param> /// <returns>返回節(jié)點(diǎn)</returns> private TreeNode<T> Find(T x, TreeNode<T> t) { while (t != null)//當(dāng)沒(méi)有找到匹配數(shù)據(jù)項(xiàng),不斷調(diào)整查找范圍,即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 //如果找到數(shù)據(jù)項(xiàng),就返回當(dāng)前t的值 { return t; } } return null; } //獲取最小的節(jié)點(diǎn), private TreeNode<T> FindMin(TreeNode<T> t) { if (t != null) { while (t.LeftNode != null)//不斷循環(huán)二叉樹(shù)的左半邊樹(shù) { t = t.LeftNode; //不斷設(shè)置t的值 } } return t; } //獲取最大的節(jié)點(diǎn) private TreeNode<T> FindMax(TreeNode<T> t) { if (t != null) { while (t.RightNode != null) { t = t.RightNode; } } return t; } /// <summary> /// 插入節(jié)點(diǎn) /// </summary> /// <param name="x">要插入的數(shù)據(jù)項(xiàng)</param> /// <param name="t">已經(jīng)存在的節(jié)點(diǎn)</param> /// <returns>返回已存在的節(jié)點(diǎn)</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) { //等號(hào)右邊的t.LeftNode是null,因此會(huì)創(chuàng)建一個(gè)TreeNode實(shí)例給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; } //刪除最小的節(jié)點(diǎn) //返回當(dāng)前根節(jié)點(diǎn) protected TreeNode<T> RemoveMin(TreeNode<T> t) { if (t == null) { throw new Exception("節(jié)點(diǎn)不存在~~"); } else if (t.LeftNode != null) { //通過(guò)遞歸不斷設(shè)置t.LeftNode,直到t.LeftNode=null t.LeftNode = RemoveMin(t.LeftNode); return t; } else //當(dāng)t.LeftNode=null的時(shí)候,就把t.RightNode當(dāng)作最小節(jié)點(diǎn)返回 { return t.RightNode; } } //刪除某數(shù)據(jù)項(xiàng),返回當(dāng)前根節(jié)點(diǎn) protected TreeNode<T> Remove(T x, TreeNode<T> t) { if (t == null) { throw new Exception("節(jié)點(diǎn)不存在~~"); } 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(); } }
客戶(hù)端創(chuàng)建二叉查找樹(shù)的實(shí)例,并調(diào)用實(shí)例方法插入隨機(jī)數(shù)據(jù)。
BinarySearchTree<int> intTree = new BinarySearchTree<int>(); Random r = new Random(DateTime.Now.Millisecond); string trace = ""; //插入5個(gè)隨機(jī)數(shù) for (int i = 0; i < 5; i++) { int randomInt = r.Next(1, 500); intTree.Insert(randomInt); trace += randomInt + " "; } Console.WriteLine("最大的節(jié)點(diǎn):" + intTree.FindMax()); Console.WriteLine("最小的節(jié)點(diǎn):" + intTree.FindMin()); Console.WriteLine("根節(jié)點(diǎn):" + intTree.Root.Element); Console.WriteLine("插入節(jié)點(diǎn)的依次順序是:" + trace); Console.WriteLine("打印樹(shù)為:" + intTree); Console.ReadKey();
以上就是這篇文章的全部?jī)?nèi)容了,希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,謝謝大家對(duì)腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請(qǐng)查看下面相關(guān)鏈接
相關(guān)文章
C#在運(yùn)行時(shí)動(dòng)態(tài)創(chuàng)建類(lèi)型的實(shí)現(xiàn)方法
這篇文章主要介紹了C#在運(yùn)行時(shí)動(dòng)態(tài)創(chuàng)建類(lèi)型的實(shí)現(xiàn)方法,主要通過(guò)動(dòng)態(tài)生成C#代碼再編譯成程序集來(lái)實(shí)現(xiàn)動(dòng)態(tài)創(chuàng)建類(lèi)型的,需要的朋友可以參考下2014-09-09C# 在PDF文檔中創(chuàng)建表格的實(shí)現(xiàn)方法
表格能夠一目了然的讓用戶(hù)看到數(shù)據(jù)信息,使信息顯得有條理化,那么在pdf類(lèi)型的文檔中如何來(lái)添加表格并對(duì)表格進(jìn)行格式化操作呢?下面小編給大家?guī)?lái)了C# 在PDF文檔中創(chuàng)建表格的實(shí)現(xiàn)方法,需要的朋友參考下吧2017-12-12使用C#實(shí)現(xiàn)基于TCP和UDP協(xié)議的網(wǎng)絡(luò)通信程序的基本示例
這篇文章主要介紹了使用C#實(shí)現(xiàn)基于TCP和UDP協(xié)議的網(wǎng)絡(luò)通信程序的示例,文中分別編寫(xiě)了基本的服務(wù)器端和客戶(hù)端,代碼十分簡(jiǎn)單,需要的朋友可以參考下2016-04-04C# 無(wú)邊框窗體邊框陰影效果的簡(jiǎn)單實(shí)現(xiàn)
這篇文章介紹了C# 無(wú)邊框窗體邊框陰影效果的簡(jiǎn)單實(shí)現(xiàn),有需要的朋友可以參考一下2013-10-10使用Unity3D實(shí)現(xiàn)選中物體消融特效的方法詳解
消融特效中基Shader?Graph實(shí)現(xiàn)了消融特效,本文將基于?Shader?實(shí)現(xiàn)消融特效,當(dāng)前實(shí)現(xiàn)消融特效的方法主要有?Alpha?測(cè)試消融、clip(或?discard)消融,它們的本質(zhì)都是隨機(jī)丟棄一些片元,以實(shí)現(xiàn)消融效果,文中有詳細(xì)代碼示例,需要的朋友可以參考下2023-10-10