我们都知道Dictionary<TKey, TValue>查找元素非常快，其实现原理是：将你TKey的值散列到数组的指定位置，将TValue的值存入对应的位置，
由于取和存用的是同一个算法，所以就很容易定位到TValue的位置，花费的时间基本上就是实现散列算法的时间，跟其中元素的个数没有关系， 故取值的时间复杂度为O(1)。 集合无非都是基于最基础语法的数组[],先欲分配，然后向其中添加元素，容量不够就创建一个2倍容量的数组，将之前的元素赋值过来，将之前的数组回收， 但基于散列算法的集合这点上有点不同，他并不是每次创建一个2倍容量的数组，为了让元素均匀的分布到数组上，数组的容量是这么增长的：3,7,11,17,23,29,37,47,59,71,89,107,131,163,197,239,293,353,431,521,631,761,919,1103... 以质数的方式增长。由于每次扩充数组的容量较小，如果要向其中添加很多元素的话，程序员又没有预先分配内存，那就会出现多次数组的创建、复制和回收。 一直想做个有用的东西出来，让想用的人用，又能让自己练练手，于是这次做了一个基于二叉查找树的集合，我们知道在二叉查找树中查询元素的最优时间复杂度是O(logN)即在满二叉树的情况下,最坏时间复杂度是O(n)即除叶子节点外每个节点只有一个子节点, 查找元素它也是很快的哦，而且查找的时候都只是做Int型的比较，而Dictionary<TKey, TValue>是基于一个散列算法，当然基于二插查找树的集合也有自身的缺点： 1：元素必须实现接口IBinaryTree，其属性CompareValue主要用于比较生成二叉查找树 2：元素必须是可以new的，即不支持基础类型int，char，string等 3：每个节点都有左右两个子节点，他们只是起到指针的作用，指向该节点的子节点，只需占用额外的少量内存 4：基本上都是基于递归实现，元素过多的话，会栈溢出，至于原因请看我的 优点是常用的一些功能都有，功能如下，练手吗，但会一直优化下去public class BinaryTree: IDisposable, IEnumerable , IEnumerable where T :IBinaryTree, new() { public BinaryTree(); public BinaryTree(IEnumerable list);//将一个数组构造成二插查找树 public BinaryTree(T root); //指定跟节点 public int Count { get; }//元素个数 public T this[IBinaryTree iBinaryTree] { get; }//数组索引直接访问元素 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 node);//在指定的节点下查找元素 public T FindMax();//最大元素 public T FindMin();//最小元素 public T FindMin(TreeNode node);//在指定的节点下查找最小元素 public IEnumerator GetEnumerator();//返回所有元素，支持foreach public TreeNode Remove(T t);//删除元素 public TreeNode Remove(IBinaryTree iBinaryTree, TreeNode node);//在指定的节点下删除元素 public IEnumerable Sort();//排序（升序） public IEnumerable ToList();//返回所有元素 }
源码 namespace Utils { /// /// 二叉树接口 /// public interface IBinaryTree { /// /// 用于比较的值 /// int CompareValue { get; set; } } public class TreeNode where T : IBinaryTree, new() { public TreeNode Left { get; set; } public TreeNode Right { set; get; } public T Data { get; set; } public TreeNode(T t) { this.Data = t; } public TreeNode() : this(default(T)) { } } /// /// 二插查找树 /// public class BinaryTree : IDisposable,IEnumerable where T : IBinaryTree, new() { public BinaryTree() { } public BinaryTree(T root) { if (root == null) { throw new NullReferenceException("Parameter is null"); } Add(root); } public BinaryTree(IEnumerable list) { if (list == null) { throw new NullReferenceException("Parameter is null"); } foreach (var item in list) { Add(item); } } //根节点 private TreeNode root; //添加节点（没有检查根节点是否为空，所以设为private） private void Add(T t, TreeNode root) { if (t == null) { return; } if (t.CompareValue < root.Data.CompareValue) { if (root.Left == null) { root.Left = new TreeNode (t); ++Count; } else { Add(t, root.Left); } } else if (t.CompareValue > root.Data.CompareValue) { if (root.Right == null) { root.Right = new TreeNode (t); ++Count; } else { Add(t, root.Right); } } else { root.Data = t; } } //添加节点 public void Add(T t) { if (t == null) { return; } if (this.root == null) { this.root = new TreeNode (t); ++Count; } else { Add(t, this.root); } } //查找指定节点下的最小节点 public T FindMin(TreeNode node) { if (node == null) { return default(T); } if (node.Left == null) { return node.Data; } else { return FindMin(node.Left); } } //查找最小节点 public T FindMin() { return FindMin(this.root); } //查找最大节点 private T FindMax(TreeNode node) { if (node.Right == null) { return node.Data; } else { return FindMax(node.Right); } } //查找最大节点 public T FindMax() { return FindMax(this.root); } //删除指定节点下的节点 public TreeNode Remove(IBinaryTree iBinaryTree, TreeNode 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);//查找当前节点有子树的最小节点 node.Data.CompareValue = tmpNode.CompareValue;//将右子树的最小节点取代当前要删除的节点 node.Right = Remove(tmpNode, node.Right);//这里是亮点，删除当前节点右子树的最小节点 } 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)//处理根节点 { this.root = node; } } --Count; } return node; } //删除节点 public TreeNode Remove(T t) { if (this.root == null || t==null) { return null; } return Remove(t, this.root); } //查找节点 public T Find(IBinaryTree iBinaryTree, TreeNode 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; } //查找节点 public T Find(IBinaryTree iBinaryTree) { return Find(iBinaryTree, this.root); } //是否包含指定元素 private bool Contains(IBinaryTree iBinaryTree, TreeNode 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); } //清除所有节点 public void Clear() { while (this.Count > 0) { Remove(this.root.Data); } this.root = new TreeNode (); } //释放资源 public void Dispose() { while (this.Count > 0) { Remove(this.root.Data); } this.root = null; } //节点个数 public int Count { private set; get; } //转换成集合 public IEnumerable ToList() { IList list = new List (Count); LCR(this.root,list); return list; } //以前序遍历的方式将节点加入集合，用递归实现，如果元素很多可能会出现栈溢出 private void LCR(TreeNode node, IList 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 Sort() { return ToList(); } //返回一个循环访问集合的枚举数 public IEnumerator GetEnumerator() { return this.ToList().GetEnumerator(); } //返回一个循环访问集合的枚举数 IEnumerator IEnumerable.GetEnumerator() { return this.GetEnumerator(); } public T this[IBinaryTree iBinaryTree] { get { return this.Find(iBinaryTree); } } } public class Node : IBinaryTree { /// /// 用于比较的值 /// 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); } } }
作者：
博客：