前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >C#笔记:哈夫曼树和编码

C#笔记:哈夫曼树和编码

作者头像
超级大猪
发布2019-11-22 09:46:56
6330
发布2019-11-22 09:46:56
举报
文章被收录于专栏:大猪的笔记
代码语言:javascript
复制
//QQ真坑爹,用它记笔记居然遗失了我的笔记。
class Program
    {
        static void Main(string[] args)
        {
            List<Node> lstNode = new List<Node>();
            lstNode.Add(new Node() { val = "a", frequency = 2 });
            lstNode.Add(new Node() { val = "b", frequency = 3 });
            lstNode.Add(new Node() { val = "c", frequency = 7 });
            lstNode.Add(new Node() { val = "d", frequency = 15 });
            lstNode.Add(new Node() { val = "e", frequency = 4 });
            lstNode.Add(new Node() { val = "f", frequency = 6 });
            HuffmanTree ht = new HuffmanTree();
            var tree = ht.BuildTree(lstNode);
            Console.WriteLine(ht.GetHuffmanCode("b", tree));
            Console.WriteLine(ht.WPL(tree));
        }
    }
    public class HuffmanTree
    {
        /// <summary>
        /// 返回一棵树中所有有值的节点。最后一个位置保存哈夫曼树(顶节点)。
        /// </summary>
        /// <param name="list">传入的叶子</param>
        /// <returns>构造的树,包含所有有值的叶子和树(最后一个位置)</returns>
        public List<Node> BuildTree(List<Node> list)
        {
            List<Node> result = new List<Node>();
            list.Sort(new NodeComparer());//首先排序
            while (list.Count > 1)
            {
                //选取最小的两个节点
                Node tempLeft = list[0];
                Node tempRight = list[1];
                Node union = new Node();
                union.leftChild = tempLeft;
                union.rightChild = tempRight;
                union.frequency = tempLeft.frequency + tempRight.frequency;
                tempLeft.parent = union;
                tempLeft.ChildType = 0;
                tempRight.parent = union;
                tempRight.ChildType = 1;
                list.Remove(tempLeft);
                list.Remove(tempRight);
                InsertList(union, list);
                if (!string.IsNullOrEmpty(tempLeft.val))
                {
                    result.Add(tempLeft);
                }
                if (!string.IsNullOrEmpty(tempRight.val))
                {
                    result.Add(tempRight);
                }
            }
            result.Add(list[0]);
            return result;
        }
        //把新增的节点插入适当的位置。因为原来的数组是有序的。插入排序节省效率。
        void InsertList(Node n, List<Node> list)
        {
            int posistion = list.Count;
            //从后往前扫描,因为新增的节点的值一般来说是比较大的。而数组已经有序。
            while (true)
            {
                --posistion;
                if (posistion == -1)//这说明扫描完整个列表了。它自己是最小的节点,或者树中只有它一个节点。插入到头。
                {
                    break;
                }
                if (list[posistion].frequency < n.frequency)//插入适当的位置。
                {
                    break;
                }
            }
            list.Insert(posistion + 1, n);
        }
        public string GetHuffmanCode(string val, List<Node> list)
        {
            Node resultNode = null;
            string result = "";
            foreach (var item in list)
            {
                if (item.val != null && item.val == val)
                {
                    resultNode = item;
                    break;
                }
            }
            Stack<int> stackPath = new Stack<int>();
            if (resultNode != null)
            {
                while (resultNode.parent != null)
                {
                    stackPath.Push(resultNode.ChildType);
                    resultNode = resultNode.parent;
                }
            }
            while (stackPath.Count != 0)
            {
                result += stackPath.Pop();
            }
            return result;
        }
        /// <summary>
        /// 返回带权路径
        /// </summary>
        /// <param name="tree">生成的树</param>
        /// <returns>此树的带权路径</returns>
        public int WPL(List<Node> tree)
        {
            int result = 0;
            Node tempNode = null;
            foreach (var item in tree)
            {
                tempNode = item;
                int tempFrequency = item.frequency;
                if (item.val != null)
                {
                    int temp = 0;
                    while (tempNode.parent != null)
                    {
                        temp++;
                        tempNode = tempNode.parent;
                    }
                    result += temp * tempFrequency;
                }
            }
            return result;
        }
        //这个是用来排序的辅助方法。用frequency排序。和list.sort()配合使用。
        class NodeComparer : IComparer<Node>
        {
            public int Compare(Node x, Node y)
            {
                return x.frequency.CompareTo(y.frequency);
            }
        }
    }
    public class Node
    {
        public string val;
        public int frequency;
        public Node leftChild;
        public Node rightChild;
        public Node parent;
        public int ChildType;//用0和1表示是父树的左/右孩子。
    }
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2015-02-16 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档