浅谈二叉查找树的集合总结分析

我们都知道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<t> : idisposable, ienumerable<t>, ienumerable where t :ibinarytree, new()
    {
        public binarytree();
        public binarytree(ienumerable<t> 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<t> node);//在指定的节点下查找元素
        public t findmax();//最大元素
        public t findmin();//最小元素
        public t findmin(treenode<t> node);//在指定的节点下查找最小元素
        public ienumerator<t> getenumerator();//返回所有元素，支持foreach
        public treenode<t> remove(t t);//删除元素
        public treenode<t> remove(ibinarytree ibinarytree, treenode<t> node);//在指定的节点下删除元素
        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);
            }
        }
        //根节点
        private treenode<t> root;
        //添加节点（没有检查根节点是否为空，所以设为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;
            }
        }
        //添加节点
        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);
            }
        }
        //查找指定节点下的最小节点
        public t findmin(treenode<t> 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<t> node)
        {
            if (node.right == null)
            {
                return node.data;
            }
            else
            {
                return findmax(node.right);
            }
        }
        //查找最大节点
        public t findmax()
        {
            return findmax(this.root);
        }
        //删除指定节点下的节点
        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);//查找当前节点有子树的最小节点
                    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<t> remove(t t)
        {
            if (this.root == null || t==null)
            {
                return null;
            }
            return remove(t, this.root);
        }
        //查找节点
        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;
        }
        //查找节点
        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);
        }
        //清除所有节点
        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;
        }
        //节点个数
        public int count
        {
            private set;
            get;
        }
        //转换成集合
        public ienumerable<t> tolist()
        {
            ilist<t> list = new list<t>(count);
            lcr(this.root,list);
            return list;
        }
        //以前序遍历的方式将节点加入集合，用递归实现，如果元素很多可能会出现栈溢出
        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();
        }
        //返回一个循环访问集合的枚举数
        public ienumerator<t> 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
    {
        /// <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);
        }
    }
}