欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

淺談二叉查找樹的集合總結(jié)分析

 更新時(shí)間：2013年05月21日 17:42:59   作者：  
本篇文章是談二叉查找樹進(jìn)行了詳細(xì)的總結(jié)分析，需要的朋友參考下
我們都知道Dictionary<TKey, TValue>查找元素非常快，其實(shí)現(xiàn)原理是：將你TKey的值散列到數(shù)組的指定位置，將TValue的值存入對(duì)應(yīng)的位置，
由于取和存用的是同一個(gè)算法，所以就很容易定位到TValue的位置，花費(fèi)的時(shí)間基本上就是實(shí)現(xiàn)散列算法的時(shí)間，跟其中元素的個(gè)數(shù)沒有關(guān)系，故取值的時(shí)間復(fù)雜度為O(1)。
集合無非都是基于最基礎(chǔ)語(yǔ)法的數(shù)組[],先欲分配，然后向其中添加元素，容量不夠就創(chuàng)建一個(gè)2倍容量的數(shù)組，將之前的元素賦值過來，將之前的數(shù)組回收，
但基于散列算法的集合這點(diǎn)上有點(diǎn)不同，他并不是每次創(chuàng)建一個(gè)2倍容量的數(shù)組，為了讓元素均勻的分布到數(shù)組上，數(shù)組的容量是這么增長(zhǎng)的：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ù)的方式增長(zhǎng)。由于每次擴(kuò)充數(shù)組的容量較小，如果要向其中添加很多元素的話，程序員又沒有預(yù)先分配內(nèi)存，那就會(huì)出現(xiàn)多次數(shù)組的創(chuàng)建、復(fù)制和回收。
一直想做個(gè)有用的東西出來，讓想用的人用，又能讓自己練練手，于是這次做了一個(gè)基于二叉查找樹的集合，我們知道在二叉查找樹中查詢?cè)氐淖顑?yōu)時(shí)間復(fù)雜度是O(logN)即在滿二叉樹的情況下,最壞時(shí)間復(fù)雜度是O(n)即除葉子節(jié)點(diǎn)外每個(gè)節(jié)點(diǎn)只有一個(gè)子節(jié)點(diǎn),
查找元素它也是很快的哦，而且查找的時(shí)候都只是做Int型的比較，而Dictionary<TKey, TValue>是基于一個(gè)散列算法，當(dāng)然基于二插查找樹的集合也有自身的缺點(diǎn)：
1：元素必須實(shí)現(xiàn)接口IBinaryTree，其屬性CompareValue主要用于比較生成二叉查找樹
2：元素必須是可以new的，即不支持基礎(chǔ)類型int，char，string等
3：每個(gè)節(jié)點(diǎn)都有左右兩個(gè)子節(jié)點(diǎn)，他們只是起到指針的作用，指向該節(jié)點(diǎn)的子節(jié)點(diǎn)，只需占用額外的少量?jī)?nèi)存
4：基本上都是基于遞歸實(shí)現(xiàn)，元素過多的話，會(huì)棧溢出
優(yōu)點(diǎn)是常用的一些功能都有，功能如下，練手嗎，但會(huì)一直優(yōu)化下去
復(fù)制代碼 代碼如下:

public class BinaryTree<T> : IDisposable, IEnumerable<T>, IEnumerable where T :IBinaryTree, new()
    {
        public BinaryTree();
        public BinaryTree(IEnumerable<T> list);//將一個(gè)數(shù)組構(gòu)造成二插查找樹
        public BinaryTree(T root); //指定跟節(jié)點(diǎn)
        public int Count { get; }//元素個(gè)數(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é)點(diǎn)下查找元素
        public T FindMax();//最大元素
        public T FindMin();//最小元素
        public T FindMin(TreeNode<T> node);//在指定的節(jié)點(diǎn)下查找最小元素
        public IEnumerator<T> GetEnumerator();//返回所有元素，支持foreach
        public TreeNode<T> Remove(T t);//刪除元素
        public TreeNode<T> Remove(IBinaryTree iBinaryTree, TreeNode<T> node);//在指定的節(jié)點(diǎn)下刪除元素
        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é)點(diǎn)
        private TreeNode<T> root;
        //添加節(jié)點(diǎn)（沒有檢查根節(jié)點(diǎn)是否為空，所以設(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é)點(diǎn)
        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é)點(diǎn)下的最小節(jié)點(diǎn)
        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é)點(diǎn)
        public T FindMin()
        {
            return FindMin(this.root);
        }
        //查找最大節(jié)點(diǎn)
        private T FindMax(TreeNode<T> node)
        {
            if (node.Right == null)
            {
                return node.Data;
            }
            else
            {
                return FindMax(node.Right);
            }
        }
        //查找最大節(jié)點(diǎn)
        public T FindMax()
        {
            return FindMax(this.root);
        }
        //刪除指定節(jié)點(diǎn)下的節(jié)點(diǎn)
        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é)點(diǎn)有子樹的最小節(jié)點(diǎn)
                    node.Data.CompareValue = tmpNode.CompareValue;//將右子樹的最小節(jié)點(diǎn)取代當(dāng)前要?jiǎng)h除的節(jié)點(diǎn)
                    node.Right = Remove(tmpNode, node.Right);//這里是亮點(diǎn)，刪除當(dāng)前節(jié)點(diǎn)右子樹的最小節(jié)點(diǎn)
                }
                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é)點(diǎn)
                    {
                        this.root = node;
                    }
                }
                --Count;
            }
            return node;
        }
        //刪除節(jié)點(diǎn)
        public TreeNode<T> Remove(T t)
        {
            if (this.root == null || t==null)
            {
                return null;
            }
            return Remove(t, this.root);
        }
        //查找節(jié)點(diǎn)
        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é)點(diǎn)
        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é)點(diǎn)
        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é)點(diǎn)個(gè)數(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é)點(diǎn)加入集合，用遞歸實(shí)現(xiàn)，如果元素很多可能會(huì)出現(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();
        }
        //返回一個(gè)循環(huán)訪問集合的枚舉數(shù)
        public IEnumerator<T> GetEnumerator()
        {
            return this.ToList().GetEnumerator();
        }
        //返回一個(gè)循環(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)文章

最新評(píng)論