淺談二叉查找樹的集合總結(jié)分析
更新時間：2013年05月21日 17:42:59 作者：
本篇文章是談二叉查找樹進行了詳細(xì)的總結(jié)分析，需要的朋友參考下
我們都知道Dictionary<TKey, TValue>查找元素非?？?，其實現(xiàn)原理是：將你TKey的值散列到數(shù)組的指定位置，將TValue的值存入對應(yīng)的位置，
由于取和存用的是同一個算法，所以就很容易定位到TValue的位置，花費的時間基本上就是實現(xiàn)散列算法的時間，跟其中元素的個數(shù)沒有關(guān)系，故取值的時間復(fù)雜度為O(1)。
集合無非都是基于最基礎(chǔ)語法的數(shù)組[],先欲分配，然后向其中添加元素，容量不夠就創(chuàng)建一個2倍容量的數(shù)組，將之前的元素賦值過來，將之前的數(shù)組回收，
但基于散列算法的集合這點上有點不同，他并不是每次創(chuàng)建一個2倍容量的數(shù)組，為了讓元素均勻的分布到數(shù)組上，數(shù)組的容量是這么增長的：3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...
以質(zhì)數(shù)的方式增長。由于每次擴充數(shù)組的容量較小，如果要向其中添加很多元素的話，程序員又沒有預(yù)先分配內(nèi)存，那就會出現(xiàn)多次數(shù)組的創(chuàng)建、復(fù)制和回收。
一直想做個有用的東西出來，讓想用的人用，又能讓自己練練手，于是這次做了一個基于二叉查找樹的集合，我們知道在二叉查找樹中查詢元素的最優(yōu)時間復(fù)雜度是O(logN)即在滿二叉樹的情況下,最壞時間復(fù)雜度是O(n)即除葉子節(jié)點外每個節(jié)點只有一個子節(jié)點,
查找元素它也是很快的哦，而且查找的時候都只是做Int型的比較，而Dictionary<TKey, TValue>是基于一個散列算法，當(dāng)然基于二插查找樹的集合也有自身的缺點：
1：元素必須實現(xiàn)接口IBinaryTree，其屬性CompareValue主要用于比較生成二叉查找樹
2：元素必須是可以new的，即不支持基礎(chǔ)類型int，char，string等
3：每個節(jié)點都有左右兩個子節(jié)點，他們只是起到指針的作用，指向該節(jié)點的子節(jié)點，只需占用額外的少量內(nèi)存
4：基本上都是基于遞歸實現(xiàn)，元素過多的話，會棧溢出
優(yōu)點是常用的一些功能都有，功能如下，練手嗎，但會一直優(yōu)化下去
public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
{
public BinaryTree();
public BinaryTree(IEnumerable<T> list);//將一個數(shù)組構(gòu)造成二插查找樹
public BinaryTree(T root); //指定跟節(jié)點
public int Count { get; }//元素個數(shù)
public T this[IBinaryTree iBinaryTree] { get; }//數(shù)組索引直接訪問元素
public void Add(T t);//添加元素
public void Clear();//清除所有元素
public bool Contains(T iBinaryTree);//是否包含自定元素
public void Dispose();//釋放資源，支持using
public T Find(IBinaryTree iBinaryTree);//查找元素
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的節(jié)點下查找元素
public T FindMax();//最大元素
public T FindMin();//最小元素
public T FindMin(TreeNode<T> node);//在指定的節(jié)點下查找最小元素
public IEnumerator<T> GetEnumerator();//返回所有元素，支持foreach
public TreeNode<T> Remove(T t);//刪除元素
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的節(jié)點下刪除元素
public IEnumerable<T> Sort();//排序（升序）
public IEnumerable<T> ToList();//返回所有元素
}
源碼
namespace Utils
{
/// <summary>
/// 二叉樹接口
/// </summary>
public interface IBinaryTree
{
/// <summary>
/// 用于比較的值
/// </summary>
int CompareValue
{
get;
set;
}
}
public class TreeNode<T> where T : IBinaryTree, new()
{
public TreeNode<T> Left
{
get;
set;
}
public TreeNode<T> Right
{
set;
get;
}
public T Data
{
get;
set;
}
public TreeNode(T t)
{
this.Data = t;
}
public TreeNode()
: this(default(T))
{
}
}
/// <summary>
/// 二插查找樹
/// </summary>
public class BinaryTree<T> : IDisposable,IEnumerable<T> where T : IBinaryTree, new()
{
public BinaryTree()
{
}
public BinaryTree(T root)
{
if (root == null)
{
throw new NullReferenceException("Parameter is null");
}
Add(root);
}
public BinaryTree(IEnumerable<T> list)
{
if (list == null)
{
throw new NullReferenceException("Parameter is null");
}
foreach (var item in list)
{
Add(item);
}
}
//根節(jié)點
private TreeNode<T> root;
//添加節(jié)點（沒有檢查根節(jié)點是否為空，所以設(shè)為private）
private void Add(T t, TreeNode<T> root)
{
if (t == null)
{
return;
}
if (t.CompareValue < root.Data.CompareValue)
{
if (root.Left == null)
{
root.Left = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Left);
}
}
else if (t.CompareValue > root.Data.CompareValue)
{
if (root.Right == null)
{
root.Right = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Right);
}
}
else
{
root.Data = t;
}
}
//添加節(jié)點
public void Add(T t)
{
if (t == null)
{
return;
}
if (this.root == null)
{
this.root = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, this.root);
}
}
//查找指定節(jié)點下的最小節(jié)點
public T FindMin(TreeNode<T> node)
{
if (node == null)
{
return default(T);
}
if (node.Left == null)
{
return node.Data;
}
else
{
return FindMin(node.Left);
}
}
//查找最小節(jié)點
public T FindMin()
{
return FindMin(this.root);
}
//查找最大節(jié)點
private T FindMax(TreeNode<T> node)
{
if (node.Right == null)
{
return node.Data;
}
else
{
return FindMax(node.Right);
}
}
//查找最大節(jié)點
public T FindMax()
{
return FindMax(this.root);
}
//刪除指定節(jié)點下的節(jié)點
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null)
{
return null;
}
if (iBinaryTree == null)
{
return node;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
node.Left = Remove(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
node.Right = Remove(iBinaryTree, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
T tmpNode = FindMin(node.Right);//查找當(dāng)前節(jié)點有子樹的最小節(jié)點
node.Data.CompareValue = tmpNode.CompareValue;//將右子樹的最小節(jié)點取代當(dāng)前要刪除的節(jié)點
node.Right = Remove(tmpNode, node.Right);//這里是亮點，刪除當(dāng)前節(jié)點右子樹的最小節(jié)點
}
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else
{
node = null;
}
if (this.root.Data.CompareValue == iBinaryTree.CompareValue)//處理根節(jié)點
{
this.root = node;
}
}
--Count;
}
return node;
}
//刪除節(jié)點
public TreeNode<T> Remove(T t)
{
if (this.root == null || t==null)
{
return null;
}
return Remove(t, this.root);
}
//查找節(jié)點
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return default(T);
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Find(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Find(iBinaryTree, node.Right);
}
return node.Data;
}
//查找節(jié)點
public T Find(IBinaryTree iBinaryTree)
{
return Find(iBinaryTree, this.root);
}
//是否包含指定元素
private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return false; ;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Right);
}
return iBinaryTree.Equals(node.Data);
}
//是否包含指定元素
public bool Contains(T iBinaryTree)
{
return Contains(iBinaryTree, this.root);
}
//清除所有節(jié)點
public void Clear()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = new TreeNode<T>();
}
//釋放資源
public void Dispose()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = null;
}
//節(jié)點個數(shù)
public int Count
{
private set;
get;
}
//轉(zhuǎn)換成集合
public IEnumerable<T> ToList()
{
IList<T> list = new List<T>(Count);
LCR(this.root,list);
return list;
}
//以前序遍歷的方式將節(jié)點加入集合，用遞歸實現(xiàn)，如果元素很多可能會出現(xiàn)棧溢出
private void LCR(TreeNode<T> node, IList<T> list)
{
if (node == null)
{
return;
}
if (node.Left != null)
{
LCR(node.Left, list);
}
list.Add(node.Data);//添加元素
if (node.Right != null)
{
LCR(node.Right, list);
}
}
//排序
public IEnumerable<T> Sort()
{
return ToList();
}
//返回一個循環(huán)訪問集合的枚舉數(shù)
public IEnumerator<T> GetEnumerator()
{
return this.ToList().GetEnumerator();
}
//返回一個循環(huán)訪問集合的枚舉數(shù)
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public T this[IBinaryTree iBinaryTree]
{
get {
return this.Find(iBinaryTree);
}
}
}
public class Node : IBinaryTree
{
/// <summary>
/// 用于比較的值
/// </summary>
public int CompareValue
{
get;
set;
}
public string Name
{
get;
set;
}
public override string ToString()
{
return string.Format("CompareValue:{0},Name:{1}", this.CompareValue, this.Name);
}
}
}
由于取和存用的是同一個算法，所以就很容易定位到TValue的位置，花費的時間基本上就是實現(xiàn)散列算法的時間，跟其中元素的個數(shù)沒有關(guān)系，故取值的時間復(fù)雜度為O(1)。
集合無非都是基于最基礎(chǔ)語法的數(shù)組[],先欲分配，然后向其中添加元素，容量不夠就創(chuàng)建一個2倍容量的數(shù)組，將之前的元素賦值過來，將之前的數(shù)組回收，
但基于散列算法的集合這點上有點不同，他并不是每次創(chuàng)建一個2倍容量的數(shù)組，為了讓元素均勻的分布到數(shù)組上，數(shù)組的容量是這么增長的：3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103...
以質(zhì)數(shù)的方式增長。由于每次擴充數(shù)組的容量較小，如果要向其中添加很多元素的話，程序員又沒有預(yù)先分配內(nèi)存，那就會出現(xiàn)多次數(shù)組的創(chuàng)建、復(fù)制和回收。
一直想做個有用的東西出來，讓想用的人用，又能讓自己練練手，于是這次做了一個基于二叉查找樹的集合，我們知道在二叉查找樹中查詢元素的最優(yōu)時間復(fù)雜度是O(logN)即在滿二叉樹的情況下,最壞時間復(fù)雜度是O(n)即除葉子節(jié)點外每個節(jié)點只有一個子節(jié)點,
查找元素它也是很快的哦，而且查找的時候都只是做Int型的比較，而Dictionary<TKey, TValue>是基于一個散列算法，當(dāng)然基于二插查找樹的集合也有自身的缺點：
1：元素必須實現(xiàn)接口IBinaryTree，其屬性CompareValue主要用于比較生成二叉查找樹
2：元素必須是可以new的，即不支持基礎(chǔ)類型int，char，string等
3：每個節(jié)點都有左右兩個子節(jié)點，他們只是起到指針的作用，指向該節(jié)點的子節(jié)點，只需占用額外的少量內(nèi)存
4：基本上都是基于遞歸實現(xiàn)，元素過多的話，會棧溢出
優(yōu)點是常用的一些功能都有，功能如下，練手嗎，但會一直優(yōu)化下去
復(fù)制代碼 代碼如下:
public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
{
public BinaryTree();
public BinaryTree(IEnumerable<T> list);//將一個數(shù)組構(gòu)造成二插查找樹
public BinaryTree(T root); //指定跟節(jié)點
public int Count { get; }//元素個數(shù)
public T this[IBinaryTree iBinaryTree] { get; }//數(shù)組索引直接訪問元素
public void Add(T t);//添加元素
public void Clear();//清除所有元素
public bool Contains(T iBinaryTree);//是否包含自定元素
public void Dispose();//釋放資源，支持using
public T Find(IBinaryTree iBinaryTree);//查找元素
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的節(jié)點下查找元素
public T FindMax();//最大元素
public T FindMin();//最小元素
public T FindMin(TreeNode<T> node);//在指定的節(jié)點下查找最小元素
public IEnumerator<T> GetEnumerator();//返回所有元素，支持foreach
public TreeNode<T> Remove(T t);//刪除元素
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的節(jié)點下刪除元素
public IEnumerable<T> Sort();//排序（升序）
public IEnumerable<T> ToList();//返回所有元素
}
復(fù)制代碼 代碼如下:
源碼
namespace Utils
{
/// <summary>
/// 二叉樹接口
/// </summary>
public interface IBinaryTree
{
/// <summary>
/// 用于比較的值
/// </summary>
int CompareValue
{
get;
set;
}
}
public class TreeNode<T> where T : IBinaryTree, new()
{
public TreeNode<T> Left
{
get;
set;
}
public TreeNode<T> Right
{
set;
get;
}
public T Data
{
get;
set;
}
public TreeNode(T t)
{
this.Data = t;
}
public TreeNode()
: this(default(T))
{
}
}
/// <summary>
/// 二插查找樹
/// </summary>
public class BinaryTree<T> : IDisposable,IEnumerable<T> where T : IBinaryTree, new()
{
public BinaryTree()
{
}
public BinaryTree(T root)
{
if (root == null)
{
throw new NullReferenceException("Parameter is null");
}
Add(root);
}
public BinaryTree(IEnumerable<T> list)
{
if (list == null)
{
throw new NullReferenceException("Parameter is null");
}
foreach (var item in list)
{
Add(item);
}
}
//根節(jié)點
private TreeNode<T> root;
//添加節(jié)點（沒有檢查根節(jié)點是否為空，所以設(shè)為private）
private void Add(T t, TreeNode<T> root)
{
if (t == null)
{
return;
}
if (t.CompareValue < root.Data.CompareValue)
{
if (root.Left == null)
{
root.Left = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Left);
}
}
else if (t.CompareValue > root.Data.CompareValue)
{
if (root.Right == null)
{
root.Right = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, root.Right);
}
}
else
{
root.Data = t;
}
}
//添加節(jié)點
public void Add(T t)
{
if (t == null)
{
return;
}
if (this.root == null)
{
this.root = new TreeNode<T>(t);
++Count;
}
else
{
Add(t, this.root);
}
}
//查找指定節(jié)點下的最小節(jié)點
public T FindMin(TreeNode<T> node)
{
if (node == null)
{
return default(T);
}
if (node.Left == null)
{
return node.Data;
}
else
{
return FindMin(node.Left);
}
}
//查找最小節(jié)點
public T FindMin()
{
return FindMin(this.root);
}
//查找最大節(jié)點
private T FindMax(TreeNode<T> node)
{
if (node.Right == null)
{
return node.Data;
}
else
{
return FindMax(node.Right);
}
}
//查找最大節(jié)點
public T FindMax()
{
return FindMax(this.root);
}
//刪除指定節(jié)點下的節(jié)點
public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null)
{
return null;
}
if (iBinaryTree == null)
{
return node;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
node.Left = Remove(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
node.Right = Remove(iBinaryTree, node.Right);
}
else
{
if (node.Left != null && node.Right != null)
{
T tmpNode = FindMin(node.Right);//查找當(dāng)前節(jié)點有子樹的最小節(jié)點
node.Data.CompareValue = tmpNode.CompareValue;//將右子樹的最小節(jié)點取代當(dāng)前要刪除的節(jié)點
node.Right = Remove(tmpNode, node.Right);//這里是亮點，刪除當(dāng)前節(jié)點右子樹的最小節(jié)點
}
else
{
if (node.Left == null)
{
node = node.Right;
}
else if (node.Right == null)
{
node = node.Left;
}
else
{
node = null;
}
if (this.root.Data.CompareValue == iBinaryTree.CompareValue)//處理根節(jié)點
{
this.root = node;
}
}
--Count;
}
return node;
}
//刪除節(jié)點
public TreeNode<T> Remove(T t)
{
if (this.root == null || t==null)
{
return null;
}
return Remove(t, this.root);
}
//查找節(jié)點
public T Find(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return default(T);
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Find(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Find(iBinaryTree, node.Right);
}
return node.Data;
}
//查找節(jié)點
public T Find(IBinaryTree iBinaryTree)
{
return Find(iBinaryTree, this.root);
}
//是否包含指定元素
private bool Contains(IBinaryTree iBinaryTree, TreeNode<T> node)
{
if (node == null || iBinaryTree == null)
{
return false; ;
}
if (iBinaryTree.CompareValue < node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Left);
}
else if (iBinaryTree.CompareValue > node.Data.CompareValue)
{
return Contains(iBinaryTree, node.Right);
}
return iBinaryTree.Equals(node.Data);
}
//是否包含指定元素
public bool Contains(T iBinaryTree)
{
return Contains(iBinaryTree, this.root);
}
//清除所有節(jié)點
public void Clear()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = new TreeNode<T>();
}
//釋放資源
public void Dispose()
{
while (this.Count > 0)
{
Remove(this.root.Data);
}
this.root = null;
}
//節(jié)點個數(shù)
public int Count
{
private set;
get;
}
//轉(zhuǎn)換成集合
public IEnumerable<T> ToList()
{
IList<T> list = new List<T>(Count);
LCR(this.root,list);
return list;
}
//以前序遍歷的方式將節(jié)點加入集合，用遞歸實現(xiàn)，如果元素很多可能會出現(xiàn)棧溢出
private void LCR(TreeNode<T> node, IList<T> list)
{
if (node == null)
{
return;
}
if (node.Left != null)
{
LCR(node.Left, list);
}
list.Add(node.Data);//添加元素
if (node.Right != null)
{
LCR(node.Right, list);
}
}
//排序
public IEnumerable<T> Sort()
{
return ToList();
}
//返回一個循環(huán)訪問集合的枚舉數(shù)
public IEnumerator<T> GetEnumerator()
{
return this.ToList().GetEnumerator();
}
//返回一個循環(huán)訪問集合的枚舉數(shù)
IEnumerator IEnumerable.GetEnumerator()
{
return this.GetEnumerator();
}
public T this[IBinaryTree iBinaryTree]
{
get {
return this.Find(iBinaryTree);
}
}
}
public class Node : IBinaryTree
{
/// <summary>
/// 用于比較的值
/// </summary>
public int CompareValue
{
get;
set;
}
public string Name
{
get;
set;
}
public override string ToString()
{
return string.Format("CompareValue:{0},Name:{1}", this.CompareValue, this.Name);
}
}
}
您可能感興趣的文章:
相關(guān)文章
在現(xiàn)今軟件開發(fā)中，網(wǎng)絡(luò)編程是非常重要的一部分，本文簡要介紹下網(wǎng)絡(luò)編程的概念和實踐,需要的朋友可以參考下2017-01-01
C#使用Gembox.SpreadSheet向Excel寫入數(shù)據(jù)及圖表的實例
下面小編就為大家分享一篇C#使用Gembox.SpreadSheet向Excel寫入數(shù)據(jù)及圖表的實例，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2017-12-12
這篇文章主要介紹了詳析C#的協(xié)變和逆變，在引用類型系統(tǒng)時，協(xié)變、逆變和不變性具有如下定義。?這些示例假定一個名為?Base?的基類和一個名為?Derived的派生類，更多內(nèi)容請需要的小伙伴參考下面文章內(nèi)容2022-01-01
本文主要介紹了.NET?MemoryCache如何清除全部緩存，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-12-12
在運行數(shù)據(jù)表數(shù)據(jù)導(dǎo)出到 EXCEL 數(shù)據(jù)輸出時遇到了一個問題,開發(fā)者設(shè)計了單行細(xì)線下邊框的輸出模板,但是邊框的樣式無法復(fù)制,所以本文給大家介紹了C#解決Excel邊框樣式無法復(fù)制及格式刷功能,需要的朋友可以參考下2024-09-09
C#調(diào)用FFplay實現(xiàn)播放視頻功能
這篇文章主要為大家詳細(xì)介紹了C#如何調(diào)用FFplay實現(xiàn)播放視頻功能,文中的示例代碼講解詳細(xì),具有一定的參考價值,有需要的小伙伴可以跟隨小編一起學(xué)習(xí)一下2023-10-10
C#實現(xiàn)tostring轉(zhuǎn)換成16進制的方法
本文介紹了在C#中將整數(shù)、字節(jié)數(shù)組、字符串轉(zhuǎn)換為十六進制字符串,以及將十六進制字符串轉(zhuǎn)換回整數(shù)的方法,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2025-02-02
這篇文章主要介紹了c# Async streams的使用解析，幫助大家更好的理解和學(xué)習(xí)使用c#，感興趣的朋友可以了解下2021-04-04
本篇文章是對StreamReader與文件亂碼問題的解決方法進行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
WPF的3D功能可以在不編寫任何c#代碼的情況下進行繪制，只需要使用xaml即可完成3D圖形的渲染。本文主要講述了WPF-3D中的關(guān)鍵概念， 以及常用到的命中測試、2d控件如何在3D對象中進行渲染，希望大家有所幫助2023-03-03