CShap 哈夫曼树 源代码

以下是C#语言的哈夫曼树源代码：

using System;
using System.Collections.Generic;

namespace HuffmanTree
{
    class Program
    {
        static void Main(string[] args)
        {
            string str = "This is a test string";
            Dictionary<char, int> freq = new Dictionary<char, int>();

            // 统计字符出现的频率
            foreach (char c in str)
            {
                if (freq.ContainsKey(c))
                {
                    freq[c]++;
                }
                else
                {
                    freq[c] = 1;
                }
            }

            // 构建哈夫曼树
            HuffmanTree huffman = new HuffmanTree(freq);

            // 打印哈夫曼编码
            Dictionary<char, string> codes = huffman.GetCodes();
            foreach (KeyValuePair<char, string> pair in codes)
            {
                Console.WriteLine("{0}: {1}", pair.Key, pair.Value);
            }
        }
    }

    class HuffmanTree
    {
        private Node root;

        public HuffmanTree(Dictionary<char, int> freq)
        {
            // 创建叶子节点
            List<Node> nodes = new List<Node>();
            foreach (KeyValuePair<char, int> pair in freq)
            {
                nodes.Add(new Node(pair.Key, pair.Value));
            }

            // 构建哈夫曼树
            while (nodes.Count > 1)
            {
                // 按照频率从小到大排序
                nodes.Sort();

                // 取出频率最小的两个节点
                Node left = nodes[0];
                Node right = nodes[1];

                // 创建新节点
                Node parent = new Node('\0', left.Frequency + right.Frequency);
                parent.Left = left;
                parent.Right = right;

                // 将新节点加入列表中
                nodes.Remove(left);
                nodes.Remove(right);
                nodes.Add(parent);
            }

            // 根据哈夫曼树构建编码
            if (nodes.Count == 1)
            {
                root = nodes[0];
                root.GenerateCodes("");
            }
        }

        public Dictionary<char, string> GetCodes()
        {
            Dictionary<char, string> codes = new Dictionary<char, string>();
            if (root != null)
            {
                root.GenerateCodes("", codes);
            }
            return codes;
        }

        class Node : IComparable<Node>
        {
            public char Symbol { get; set; }
            public int Frequency { get; set; }
            public Node Left { get; set; }
            public Node Right { get; set; }
            public string Code { get; set; }

            public Node(char symbol, int frequency)
            {
                Symbol = symbol;
                Frequency = frequency;
            }

            public int CompareTo(Node other)
            {
                return Frequency.CompareTo(other.Frequency);
            }

            public void GenerateCodes(string code)
            {
                if (Left == null && Right == null)
                {
                    Code = code;
                }
                else
                {
                    Left.GenerateCodes(code + "0");
                    Right.GenerateCodes(code + "1");
                }
            }

            public void GenerateCodes(string code, Dictionary<char, string> codes)
            {
                if (Left == null && Right == null)
                {
                    codes[Symbol] = code;
                }
                else
                {
                    Left.GenerateCodes(code + "0", codes);
                    Right.GenerateCodes(code + "1", codes);
                }
            }
        }
    }
}