数据结构（C#版）—哈夫曼树

[问题描述]：设一份电文中有不同出现频率的字符，为了提高电文的输入和翻译效率，必须有一套简短而又不会产生歧义的字符代码。试根据哈夫曼算法，对电文中的不同字符，构造出一棵哈夫曼树，对每个字符进行编码。

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using DS.BLL;
namespace HuffTree.CSharp
{
    class Program
    {
        static void Main(string[] args)
        {

            int leafNum = 4;

            int totalNodes = 2 * leafNum - 1;

            int[] weight = new int[] { 3, 4, 1, 2 };

            string[] alphabet = new string[] { "A", "B", "C", "D" };

            //初始化
            HuffmanTree[] huffmanTree = new HuffmanTree[totalNodes].Select(p => new HuffmanTree() { }).ToArray();

            //构建
            HuffmanTreeBLL.Create(huffmanTree, leafNum, weight);

            //哈夫曼编码
            string[] huffmanCode = HuffmanTreeBLL.Coding(huffmanTree, leafNum);
            PrintResult(alphabet, huffmanTree, huffmanCode, leafNum);

            Console.ReadKey();
        }

        private static void PrintResult(string[] alphabet, HuffmanTree[] huffmanTree, string[] huffmanCode, int leafNum)
        {
            if (alphabet.Count() < 1 || huffmanTree.Count() < 1 || huffmanCode.Count() < 1) return;

            for (int i = 0; i < leafNum; i++)
            {
                Console.WriteLine("字符：{0},权重值:{1},哈夫曼编码：{2}", alphabet[i], huffmanTree[i].Weight, huffmanCode[i]);
            }
        }
    }
}

namespace DS.BLL
{

    /// 
    public class HuffmanTreeBLL
    {


        public static HuffmanTree[] Create(HuffmanTree[] huffmanTree, int leafNum, int[] weight)
        {
            //获取哈夫曼树结点总数
            int totalNodes = 2 * leafNum - 1;

            InitLeafNode(huffmanTree, leafNum, weight);

            //构造哈夫曼
            for (int i = leafNum; i < totalNodes; i++)
            {
                //获取权重最小的两个叶子节点的下标
                int minIndex1 = -1;
                int minIndex2 = -1;
                SelectNode(huffmanTree, i, ref minIndex1, ref minIndex2);

                huffmanTree[minIndex1].Parent = i;
                huffmanTree[minIndex2].Parent = i;

                huffmanTree[i].Left = minIndex1;
                huffmanTree[i].Right = minIndex2;
                huffmanTree[i].Weight = huffmanTree[minIndex1].Weight + huffmanTree[minIndex2].Weight;
            }
            return huffmanTree;
        }


        public static string[] Coding(HuffmanTree[] huffmanTree, int leafNum)
        {
            string[] huffmanCode = new string[leafNum];

            //当前节点下标
            int current = 0;
            //父节点下标
            int parent = 0;

            for (int i = 0; i < leafNum; i++)
            {
                string codeTemp = string.Empty;
                current = i;

                //第一次获取最左节点
                parent = huffmanTree[current].Parent;

                while (parent != 0)
                {
                    if (huffmanTree[parent].Left == current) codeTemp += "0";
                    else codeTemp += "1";

                    current = parent;
                    parent = huffmanTree[parent].Parent;
                }
                huffmanCode[i] = new string(codeTemp.Reverse().ToArray());
            }
            return huffmanCode;
        }


        private static void InitLeafNode(HuffmanTree[] huffmanTree, int leafNum, int[] weight)
        {
            if (huffmanTree == null || leafNum < 1 || weight.Count() < 1) return;

            for (int i = 0; i < leafNum; i++)
            {
                huffmanTree[i].Weight = weight[i];
            }
        }

        private static void SelectNode(HuffmanTree[] huffmanTree, int searchNode, ref int minIndex1, ref int minIndex2)
        {
            HuffmanTree minNode1 = null;
            HuffmanTree minNode2 = null;

            for (int i = 0; i < searchNode; i++)
            {
                if (huffmanTree[i].Parent == 0)
                {
                    //如果为null，则表示当前节叶子节点最小
                    if (minNode1 == null)
                    {
                        minIndex1 = i;
                        minNode1 = huffmanTree[i];
                        continue;
                    }

                    if (minNode2 == null)
                    {
                        minIndex2 = i;
                        minNode2 = huffmanTree[i];

                        //交换位置，确保minIndex1为最小
                        if (minNode1.Weight >= minNode2.Weight)
                        {
                            //节点交换
                            var temp = minNode1;
                            minNode1 = minNode2;
                            minNode2 = temp;

                            //交换下标
                            var tempIndex = minIndex1;
                            minIndex1 = minIndex2;
                            minIndex2 = tempIndex;

                            continue;
                        }
                    }

                    if (minNode1 != null && minNode2 != null)
                    {
                        if (huffmanTree[i].Weight < minNode1.Weight)
                        {
                            //将min1临时转存给min2
                            minNode2 = minNode1;
                            minNode1 = huffmanTree[i];

                            //记录在数组中的下标
                            minIndex2 = minIndex1;
                            minIndex1 = i;
                        }
                        else
                        {
                            if (huffmanTree[i].Weight < minNode2.Weight)
                            {
                                minNode2 = huffmanTree[i];
                                minIndex2 = i;
                            }
                        }
                    }
                }
            }
        }
    }


    public class HuffmanTree
    {
        public int Weight { get; set; } //权值

        public int Parent { get; set; } //父节点

        public int Left { get; set; } //左孩子节点

        public int Right { get; set; } //右孩子节点
    }
}