哈夫曼樹定義為：給定n個權(quán)值作為n個葉子結(jié)點，構(gòu)造一棵二叉樹，若帶權(quán)路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權(quán)值？什么是路徑長度？什么是帶權(quán)路徑長度呢？
權(quán)值：哈夫曼樹的權(quán)值是自己定義的，他的物理意義表示數(shù)據(jù)出現(xiàn)的次數(shù)、頻率?？梢杂脴涞拿總€結(jié)點數(shù)據(jù)域data存放一個特定的數(shù)表示它的值。

路徑長度：在一棵樹中，從一個結(jié)點往下可以達到的孩子或子孫結(jié)點之間的通路，稱為路徑。通路中分支的數(shù)目稱為路徑長度。若規(guī)定根結(jié)點的層數(shù)為1，則從根結(jié)點到第L層結(jié)點的路徑長度為L-1。

結(jié)點的帶權(quán)路徑長度為：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。  樹中所有葉子節(jié)點的帶權(quán)路徑長度之和，WPL=sigma(w*l)

2、哈夫曼樹的構(gòu)造過程。（結(jié)合圖例）
假設(shè)有n個權(quán)值，則構(gòu)造出的哈夫曼樹有n個葉子結(jié)點。 n個權(quán)值分別設(shè)為 w1、w2、…、wn，則哈夫曼樹的構(gòu)造規(guī)則為：

　　(1) 將w1、w2、…，wn看成是有n 棵樹的森林(每棵樹僅有一個結(jié)點)；

　　(2) 在森林中選出兩個根結(jié)點的權(quán)值最小的樹合并，作為一棵新樹的左、右子樹，且新樹的根結(jié)點權(quán)值為其左、右子樹根結(jié)點權(quán)值之和；

　　(3)從森林中刪除選取的兩棵樹，并將新樹加入森林；

　　(4)重復(fù)(2)、(3)步，直到森林中只剩一棵樹為止，該樹即為所求得的哈夫曼樹

3、哈夫曼樹的應(yīng)用：哈夫曼編碼（前綴編碼）
哈夫曼編碼

在數(shù)據(jù)通信中，通常需要把要傳送的文字轉(zhuǎn)換為由二進制字符0和1組成的二進制串，這個過程被稱之為編碼(Encoding)。例如，假設(shè)要傳送的電文為DCBBADD，電文中只有A、B、C、D四種字符，若這四個字符采用表(a)所示的編碼方案，則電文的代碼為11100101001111，代碼總長度為14。若采用表(b) 所示的編碼方案，則電文的代碼為0110101011100，代碼總長度為13。

字符集的不同編碼方案

哈夫曼樹可用于構(gòu)造總長度最短的編碼方案。具體構(gòu)造方法如下：
設(shè)需要編碼的字符集為{d1,d2,…,dn}，各個字符在電文中出現(xiàn)的次數(shù)或頻率集合為{w1,w2,…,wn}。以d1,d2,…,dn作為葉子結(jié)點，以w1,w2,…,wn作為相應(yīng)葉子結(jié)點的權(quán)值來構(gòu)造一棵哈夫曼樹。規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結(jié)點到葉子結(jié)點所經(jīng)過的路徑分支組成的0和1的序列便為該結(jié)點對應(yīng)字符的編碼就是哈夫曼編碼(Huffman Encoding)。

在建立不等長編碼中，必須使任何一個字符的編碼都不是另一個編碼的前綴，這樣才能保證譯碼的唯一性。例如，若字符A的編碼是00，字符B的編碼是001，那么字符A的編碼就成了字符B的編碼的后綴。這樣，對于代碼串001001，在譯碼時就無法判定是將前兩位碼00譯成字符A還是將前三位碼001譯成B。這樣的編碼被稱之為具有二義性的編碼，二義性編碼是不唯一的。而在哈夫曼樹中，每個字符結(jié)點都是葉子結(jié)點，它們不可能在根結(jié)點到其它字符結(jié)點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。

下圖就是電文DCBBADD的哈夫曼樹：

4、哈夫曼樹的實現(xiàn)

由哈夫曼樹的構(gòu)造算法可知，用一個數(shù)組存放原來的n個葉子結(jié)點和構(gòu)造過程中臨時生成的結(jié)點，數(shù)組的大小為2n-1。所以，哈夫曼樹類HuffmanTree中有兩個成員字段：data數(shù)組用于存放結(jié)點，leafNum表示哈夫曼樹葉子結(jié)點的數(shù)目。結(jié)點有四個域，一個域weight，用于存放該結(jié)點的權(quán)值；一個域lChild，用于存放該結(jié)點的左孩子結(jié)點在數(shù)組中的序號；一個域rChild，用于存放該結(jié)點的右孩子結(jié)點在數(shù)組中的序號；一個域parent，用于判定該結(jié)點是否已加入哈夫曼樹中。

哈夫曼樹結(jié)點的結(jié)構(gòu)為：| 數(shù)據(jù) | weight | lChild | rChild | parent |

     public class Node
    {
        char c; //存儲的數(shù)據(jù)，為一個字符
        private double weight; //結(jié)點權(quán)值
        private int lChild; //左孩子結(jié)點
        private int rChild; //右孩子結(jié)點
        private int parent; //父結(jié)點
        //結(jié)點權(quán)值屬性
        public double Weight
        {
            get
            {
                return weight;
            }
            set
            {
                weight = value;
            }
        }
        //左孩子結(jié)點屬性
        public int LChild
        {
            get
            {
                return lChild;
            }
            set
            {
                lChild = value;
            }
        }
        //右孩子結(jié)點屬性
        public int RChild
        {
            get
            {
                return rChild;
            }
            set
            {
                rChild = value;
            }
        }
        //父結(jié)點屬性
        public int Parent
        {
            get
            {
                return parent;
            }
            set
            {
                parent = value;
            }
        }
        //構(gòu)造器
        public Node()
        {
            weight = 0;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }
        //構(gòu)造器
        public Node(double weitht)
        {
            this.weight = weitht;
            lChild = -1;
            rChild = -1;
            parent = -1;
        }

        //構(gòu)造器
        public Node(int w, int lc, int rc, int p)
        {
            weight = w;
            lChild = lc;
            rChild = rc;
            parent = p;
        }
    }

    public class HuffmanTree
    {
        private Node[] data; //結(jié)點數(shù)組
        private int leafNum; //葉子結(jié)點數(shù)目
        //索引器
        public Node this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //葉子結(jié)點數(shù)目屬性
        public int LeafNum
        {
            get
            {
                return leafNum;
            }
            set
            {
                leafNum = value;
            }
        }
        //構(gòu)造器
        public HuffmanTree(int n)
        {
            data = new Node[2 * n - 1];
            leafNum = n;
        }
        //創(chuàng)建哈夫曼樹
        public void Create(Node[] datain)
        {
            double minL, minR;
            minL = minR = double.MaxValue;
            int lchild, rchild;
            lchild = rchild = -1;

            int length = data.Length;
            //初始化哈夫曼樹
            for (int i = 0; i < length; i++)
                data[i] = new Node();
            for (int i = 0; i < datain.Length; i++)
                data[i] = datain[i];

            //處理n個葉子結(jié)點，建立哈夫曼樹
            for (int i = leafNum; i < length; i++)
            {
                //在全部結(jié)點中找權(quán)值最小的兩個結(jié)點
                for (int j = 0; j < i; j++)
                {
                    if (data[j].Parent == -1)
                    {
                        if (data[j].Weight < minL)
                        {
                            minR = minL;
                            minL = data[j].Weight;
                            rchild = lchild;
                            lchild = j;
                        }
                        else if (data[j].Weight < minR)
                        {
                            minR = data[j].Weight;
                            rchild = j;
                        }
                    }
                }
                data[lchild].Parent = data[rchild].Parent = i;
                data[i].Weight = minL + minR;
                data[i].LChild = lchild;
                data[i].RChild = rchild;
            }
        }
    }

    class Program
    {
        static void Main(string[] args)
        {
            HuffmanTree tree = new HuffmanTree(5);
            Node[] nodes = new Node[] { new Node(1), new Node(2), new Node(2.5d), new Node(3), new Node(2.6d) };
            tree.Create(nodes);

            Console.ReadLine();
        }
    }

/////////////////////////////節(jié)選自網(wǎng)絡(luò)上的資料、