C#使用集合實(shí)現(xiàn)二叉查找樹
更新時(shí)間：2022年08月22日 08:34:42 作者：Darren?Ji
這篇文章介紹了C#使用集合實(shí)現(xiàn)二叉查找樹的方法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下
與鏈表、堆棧和隊(duì)列不一樣，二叉查找樹不是線性數(shù)據(jù)結(jié)構(gòu)，是二維數(shù)據(jù)結(jié)構(gòu)。每個節(jié)點(diǎn)都包含一個LeftNode和RightNode，二叉查找樹把比節(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)的類。
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)建一個泛型二叉樹查找類，維護(hù)著一個根節(jié)點(diǎn)，并提供各種對節(jié)點(diǎn)的操作方法。
public class BinarySearchTree<T>
{
public TreeNode<T> Root { get; set; }
public BinarySearchTree()
{
this.Root = null;
}
//把某個數(shù)據(jù)項(xiàng)插入到二叉樹
public void Insert(T x)
{
this.Root = Insert(x, this.Root);
}
//把某個數(shù)據(jù)項(xiàng)從二叉樹中刪除
public void Remove(T x)
{
this.Root = Remove(x, this.Root);
}
//刪除二叉樹中的最小數(shù)據(jù)項(xiàng)
public void RemoveMin()
{
this.Root = RemoveMin(this.Root);
}
//獲取二叉樹中的最小數(shù)據(jù)項(xiàng)
public T FindMin()
{
return ElemntAt(FindMin(this.Root));
}
//獲取二叉樹中的最大數(shù)據(jù)項(xiàng)
public T FindMax()
{
return ElemntAt(FindMax(this.Root));
}
//獲取二叉樹中的某個數(shù)據(jù)項(xiàng)
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é)點(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)沒有找到匹配數(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)二叉樹的左半邊樹
{
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)
{
//等號右邊的t.LeftNode是null，因此會創(chuàng)建一個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)
{
//通過遞歸不斷設(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();
}
}客戶端創(chuàng)建二叉查找樹的實(shí)例，并調(diào)用實(shí)例方法插入隨機(jī)數(shù)據(jù)。
BinarySearchTree<int> intTree = new BinarySearchTree<int>();
Random r = new Random(DateTime.Now.Millisecond);
string trace = "";
//插入5個隨機(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("打印樹為：" + intTree);
Console.ReadKey();
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，謝謝大家對腳本之家的支持。如果你想了解更多相關(guān)內(nèi)容請查看下面相關(guān)鏈接
相關(guān)文章
這篇文章主要為大家詳細(xì)介紹了C#調(diào)用exe文件的相關(guān)方法,文中的示例代碼講解詳細(xì),具有一定的借鑒價(jià)值,有需要的小伙伴可以參考一下2024-04-04
在WPF中合并兩個ObservableCollection集合
這篇文章介紹了在WPF中合并兩個ObservableCollection集合的方法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-06-06
本教程指導(dǎo)如何自定義繪制一個帶有手自動旋轉(zhuǎn)功能的按鈕和帶有標(biāo)題的面板,教程提供詳細(xì)的步驟,方便用戶自定義界面布局,感興趣的朋友跟隨小編一起看看吧2024-09-09
C#實(shí)現(xiàn)不同窗體之間傳遞參數(shù)
這篇文章主要介紹了C#實(shí)現(xiàn)不同窗體之間傳遞參數(shù)問題，具有很好的參考價(jià)值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
下面小編就為大家?guī)硪黄獪\談C# 序列化與反序列化幾種格式的轉(zhuǎn)換。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-08-08
這篇文章主要為大家詳細(xì)介紹了C#超市收銀系統(tǒng)設(shè)計(jì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2017-06-06
這篇文章給大家講解了下作為程序員如何統(tǒng)計(jì)自己寫過的代碼的行數(shù)，這個也是證明自己程序員能力的一個表現(xiàn)，一起來看下。2017-12-12
這篇文章介紹了C#文件操作、讀取文件、Debug/Trace類的用法，文中通過示例代碼介紹的非常詳細(xì)。對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-03-03
這篇文章主要介紹了C#超實(shí)用代碼段合集,涉及C#針對圖標(biāo)、數(shù)學(xué)運(yùn)算、拼音、日期、時(shí)間及文件夾等的相關(guān)操作技巧,需要的朋友可以參考下2015-11-11
C#獲取Windows進(jìn)程監(jiān)聽的TCP/UDP端口實(shí)例
本文介紹了C#獲取Windows下某進(jìn)程監(jiān)聽的TCP/UDP端口的方法，希望對您有所幫助。2013-11-11