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

//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表示是父树的左/右孩子。
    }