哈夫曼樹定義為：給定n個權值作為n個葉子結點，構造一棵二叉樹，若帶權路徑長度達到最小，稱這樣的二叉樹為最優(yōu)二叉樹，也稱為哈夫曼樹(Huffman tree)。
1、那么什么是權值？什么是路徑長度？什么是帶權路徑長度呢？
權值：哈夫曼樹的權值是自己定義的，他的物理意義表示數據出現的次數、頻率。可以用樹的每個結點數據域data存放一個特定的數表示它的值。

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

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

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

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

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

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

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

3、哈夫曼樹的應用：哈夫曼編碼（前綴編碼）
哈夫曼編碼

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

字符集的不同編碼方案

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

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

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

4、哈夫曼樹的實現

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

哈夫曼樹結點的結構為：| 數據 | weight | lChild | rChild | parent |

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

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

    public class HuffmanTree
    {
        private Node[] data; //結點數組
        private int leafNum; //葉子結點數目
        //索引器
        public Node this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //葉子結點數目屬性
        public int LeafNum
        {
            get
            {
                return leafNum;
            }
            set
            {
                leafNum = value;
            }
        }
        //構造器
        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個葉子結點，建立哈夫曼樹
            for (int i = leafNum; i < length; i++)
            {
                //在全部結點中找權值最小的兩個結點
                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é)選自網絡上的資料、