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