程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 哈夫曼樹與哈夫曼編碼詳解及C++模板實現

哈夫曼樹與哈夫曼編碼詳解及C++模板實現

編輯：關於C++

哈夫曼樹又稱最優二叉樹，是帶權路徑長度最短的樹，可用來構造最優編碼，用於信息傳輸、數據壓縮等方面，是一種應用廣泛的二叉樹。
這裡寫圖片描述

幾個相關的基本概念：

1.路徑：從樹中一個結點到另一個結點之間的分支序列構成兩個節點間的路徑
2.路徑長度：路徑上的分支的條數稱為路徑長度
3.樹的路徑長度：從樹根到每個結點的路徑長度之和稱為樹的路徑長度
4.結點的權：給樹中結點賦予一個數值，該數值稱為結點的權
5.帶權路徑長度：結點到樹根間的路徑長度與結點的權的乘積，稱為該結點的帶權路徑長度
6.樹的帶權路徑長度：樹中所有葉子結點的帶權路徑長度之和，通常記為WPL
7.最優二叉樹：在葉子個數n以及各葉子的權值確定的條件下，樹的帶權路徑長度WPL值最下的二叉樹稱為最優二叉樹。

哈夫曼樹的建立

由哈夫曼最早給出的建立最優二叉樹的帶有一般規律的算法，俗稱哈夫曼算法。描述如下：
1):初始化：根據給定的n個權值(Ｗ1,Ｗ2,…，Ｗn)，構造n棵二叉樹的森林集合F={Ｔ1,Ｔ2,…,Ｔn}，其中每棵二叉樹Ｔi只有一個權值為Ｗi的根節點，左右子樹均為空。

2):找最小樹並構造新樹：在森林集合F中選取兩棵根的權值最小的樹做為左右子樹構造一棵新的二叉樹，新的二叉樹的根結點為新增加的結點，其權值為左右子樹的權值之和。

3):刪除與插入：在森林集合F中刪除已選取的兩棵根的權值最小的樹，同時將新構造的二叉樹加入到森林集合F中。

4):重復2)和3)步驟，直至森林集合F中只含一棵樹為止，這顆樹便是哈夫曼樹，即最優二叉樹。由於2)和3)步驟每重復一次，刪除掉兩棵樹，增加一棵樹，所以2)和3)步驟重復n-1次即可獲得哈夫曼樹。

下圖展示了有4個葉子且權值分別為{9,6,3,1}的一棵最優二叉樹的建立過程。

這裡寫圖片描述

C++類模板構造哈夫曼樹

哈夫曼樹的節點結構

/*哈夫曼樹的節點定義*/
template 
struct HuffmanNode
{
    //初始化
    HuffmanNode(T k,HuffmanNode* l,HuffmanNode* r):key(k),lchild(l),rchild(r),flag(0) {}

    T key;                  //節點權值
    HuffmanNode* lchild; //節點左孩
    HuffmanNode* rchild; //節點右孩
    int flag;               //標志　判斷是否從森林中刪除
};

哈夫曼樹的抽象數據類型

template 
class Huffman
{
public:
    void preOrder();        //前序遍歷哈夫曼樹
    void inOrder();         //中序遍歷哈夫曼樹
    void postOrder();       //後序遍歷哈夫曼樹

    void creat(T a[],int size); //創建哈夫曼樹
    void destory();             //銷毀哈夫曼樹
    void print();               //打印哈夫曼樹

    void my_sort(int size);
    Huffman():root(NULL) {}
    ~Huffman(){
        destory(root);
    }
private:
    void preOrder(HuffmanNode* pnode);   //前序遍歷二叉樹
    void inOrder(HuffmanNode* pnode);    //中序遍歷二叉樹
    void postOrder(HuffmanNode* pnode);  //後序遍歷二叉樹
    void print(HuffmanNode* pnode);      //打印二叉樹
    void destory(HuffmanNode* pnode);    //銷毀二叉樹

    HuffmanNode* root;           　//哈夫曼樹根節點
    HuffmanNode* forest[MAXSIZE];　//用數組來存儲森林中樹的根節點
};

具體實現

/*自寫排序*/
template 
void Huffman::my_sort(int size)
{
    for(int i=0;ikey > forest[j]->key)
            {
                swap(forest[i],forest[j]);
            }
            else
                continue;
        }
    }
};

/*創建哈夫曼樹*/
template 
void Huffman::creat(T a[],int size)
{
    int j,k=0;
    /*每個節點都作為一個森林*/
    for(int i=0; i* ptr = new HuffmanNode(a[i],NULL,NULL);
        forest[i] = ptr; //雙向隊列尾部加入一個元素
    }
    for(int i=0; iflag!=1 && forest[j+1]->flag != 1)
            {
                /*構建新節點*/
                HuffmanNode* node = new HuffmanNode(forest[j]->key + forest[j+1]->key,forest[j],forest[j+1]);  
                /*新節點加入森林中*/
                forest[size+k] = node;
                k++;
                /*刪除兩棵權值最小的樹*/
                forest[j]->flag = 1;
                forest[j+1]->flag = 1;
                break;
            }
            else
                continue;
        }
    }
    root  = forest[size+k-1];
};

/*前序遍歷哈夫曼樹*/
template 
void Huffman::preOrder(HuffmanNode* pnode)
{
    if(pnode != NULL)
    {
        cout << pnode -> key;
        preOrder(pnode->lchild);
        preOrder(pnode->rchild);
    }
};
template 
void Huffman::preOrder()
{
    preOrder(root);
};

/*中序遍歷哈夫曼樹*/
template 
void Huffman::inOrder(HuffmanNode* pnode)
{
    if(pnode != NULL)
    {
        inOrder(pnode->lchild);
        cout << pnode -> key;
        inOrder(pnode->rchild);
    }
};
template 
void Huffman::inOrder()
{
    inOrder(root);
};

/*後序遍歷哈夫曼樹*/
template 
void Huffman::postOrder(HuffmanNode* pnode)
{
    if(pnode != NULL)
    {
        postOrder(pnode->lchild);
        postOrder(pnode->rchild);
        cout << pnode -> key;
    }
};
template 
void Huffman::postOrder()
{
    postOrder(root);
};

/*打印哈夫曼樹*/
template 
void Huffman::print(HuffmanNode* pnode)
{
    if(pnode != NULL)
    {
        cout << "當前結點：" << pnode -> key << ".";
        if(pnode -> lchild != NULL)
            cout << "它的左孩子結點為：" << pnode->lchild->key << ".";
        else
            cout << "它沒有左孩子.";
        if(pnode -> rchild != NULL)
            cout << "它的右孩子結點為：" << pnode->rchild->key << ".";
        else
            cout << "它沒有右孩子.";
        cout << endl;
        print(pnode->lchild);
        print(pnode->rchild);
    }
};
template 
void Huffman::print()
{
    print(root);  
};

/*銷毀哈夫曼樹*/
template 
void Huffman::destory(HuffmanNode* pnode)
{
    if( pnode!= NULL)    
    {
        destory(pnode->lchild);
        destory(pnode->rchild);
        delete pnode;
        pnode = NULL;
    }
};
template 
void Huffman::destory()
{
    destory(root);
};

哈夫曼樹代碼測試

int main()
{
    Huffman huff;
    int a[] = {10,20,30,40};
    huff.creat(a,4);
    huff.print();
    return 0;
}

輸出結果：

當前結點：100.它的左孩子結點為：40.它的右孩子結點為：60.
當前結點：40.它沒有左孩子.它沒有右孩子.
當前結點：60.它的左孩子結點為：30.它的右孩子結點為：30.
當前結點：30.它沒有左孩子.它沒有右孩子.
當前結點：30.它的左孩子結點為：10.它的右孩子結點為：20.
當前結點：10.它沒有左孩子.它沒有右孩子.
當前結點：20.它沒有左孩子.它沒有右孩子.

昨天下午就開始寫了，本來使用deque雙向隊列來存儲森林中樹的根節點，結果在排序找出權值最小的兩棵樹的時候遇到了麻煩，換了幾種方式都是編譯錯誤，折磨了幾個小時。後來選擇用數組來存儲，今天下午試著寫了一下，總算整出來了，還有待優化，分享一下吧，整個思路過程都有注釋，下來在慢慢改。下面看哈夫曼編碼。