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

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

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

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

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

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

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

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

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

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

字符集的不同編碼方案

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

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

下圖就是電文DCBBADD的哈夫曼樹(shù)：

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

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

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

     public class Node
    {
        char c; //存儲(chǔ)的數(shù)據(jù)，為一個(gè)字符
        private double weight; //結(jié)點(diǎn)權(quán)值
        private int lChild; //左孩子結(jié)點(diǎn)
        private int rChild; //右孩子結(jié)點(diǎn)
        private int parent; //父結(jié)點(diǎn)
        //結(jié)點(diǎn)權(quán)值屬性
        public double Weight
        {
            get
            {
                return weight;
            }
            set
            {
                weight = value;
            }
        }
        //左孩子結(jié)點(diǎn)屬性
        public int LChild
        {
            get
            {
                return lChild;
            }
            set
            {
                lChild = value;
            }
        }
        //右孩子結(jié)點(diǎn)屬性
        public int RChild
        {
            get
            {
                return rChild;
            }
            set
            {
                rChild = value;
            }
        }
        //父結(jié)點(diǎn)屬性
        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é)點(diǎn)數(shù)組
        private int leafNum; //葉子結(jié)點(diǎn)數(shù)目
        //索引器
        public Node this[int index]
        {
            get
            {
                return data[index];
            }
            set
            {
                data[index] = value;
            }
        }
        //葉子結(jié)點(diǎn)數(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)建哈夫曼樹(shù)
        public void Create(Node[] datain)
        {
            double minL, minR;
            minL = minR = double.MaxValue;
            int lchild, rchild;
            lchild = rchild = -1;

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

            //處理n個(gè)葉子結(jié)點(diǎn)，建立哈夫曼樹(shù)
            for (int i = leafNum; i < length; i++)
            {
                //在全部結(jié)點(diǎn)中找權(quán)值最小的兩個(gè)結(jié)點(diǎn)
                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ò)上的資料、