題解——二叉樹哈夫曼編碼的實作

題目鏈接：傳送門

題面

描述

輸入

第一行：采用括號表示法的樹字串
第二行：每個葉子結點的結點值（用單個小寫字母表示，用空格分隔）
第三行：每個葉子結點的結點值（用整數表示，用空格分隔）

輸出

第一行：按從左到右輸出所有非葉子結點
第二行：按從左到右輸出所有非葉子結點對應的權值
第三行：按從左到右輸出每個葉子結點
第四行：按從左到右輸出每個葉子結點的哈夫曼編碼

樣例輸入

A(B(D(F,G),E),C)
a b c d
1 2 3 4

樣例輸出

D B A
3 6 10
F G E C
000 001 01 1

題解

事先說明一下，我做這個題是在老師講哈夫曼樹之前，所以代碼邏輯混亂、思維白給，不能代表敬愛的潘老師的教學內容，因為時間比較緊，所以這次只能挑幾個題出一下題解，其他的等考完試再補上，應一位神秘同學的要求，先寫這個題的題解，而我又沒時間按正規思路寫一遍了，所以只能硬著頭皮講當時做題時候的思路，

這個思路比較基礎，是完全建立在之前學的樹的基本功能至上的，所以就算你完全沒懂哈夫曼樹是什么，只要你能看懂題意，應該就能看懂下面的代碼（雖然它真的有點長）

另外，由于它跟哈夫曼樹幾乎完全沒關系，所以即使它提交結果是AC，但我不敢保證它的正確性，不過就算不對，下面的思路也不失為對樹的基礎知識的一種靈活運用~~（強行狡辯）~~

題意

根據題意，每個“哈夫曼樹”的結點都是這樣的：

• 含有一個標號，是單個大寫字母：A、B、C、D、E、F、G
• 含有一個結點值，是單個小寫字母，其中
  • 葉子結點的結點值來源于陣列v
  • 非葉子結點的結點值為-
• 含有一個權值，是一個整數，其中
  • 葉子結點的權值來源于陣列w
  • 從輸入輸出樣例可以看出，非葉子結點的權值等于左右孩子的權值的和

再來看題目要求：

任務1. 需要一個常用的括號運算式建樹函式
任務2. 需要一個從左到右遍歷葉子結點的方法
任務3. 需要一個由子結點的權值計算父節點權值的方法
任務4. 需要一個計算哈夫曼編碼的方法，并運用與任務2相同的方法遍歷輸出

哈夫曼編碼是什么？

我們可以從樣例輸出的規律里，觀察哈夫曼編碼的規則，我再把圖放一遍：

樣例告訴我們：

• F結點對應哈夫曼編碼000，從根結點開始找它的話，依次是：A的左孩子為B、B的左孩子為D、D的左孩子為F

• G結點對應哈夫曼編碼001，從根結點開始找它，依次是：A的左孩子為B、B的左孩子為D、D的右孩子為G

• E結點對應哈夫曼編碼01，從根結點開始找它，它依次是：A的左孩子為B、B的右孩子為E

• G結點對應哈夫曼編碼1，從根結點開始找它，直接就是A的右孩子為D

發現了嗎？只要找到從根結點到它的路徑，然后按照左孩子-0、右孩子-1的規則寫，就可以得到哈夫曼編碼了

同時，從樣例中可以看出，我們需要一種從左到右、從下到上的遍歷方法，來完成這個題的任務

思路決議及對應代碼

建樹

用括號運算式建樹的方法屬于二叉樹的基本操作，可以參考我之前的博客，里面有蠻詳細的講解，這里直接給代碼

二叉樹基礎操作部分：資料結構與演算法——二叉樹

void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st; //STL的堆疊，型別為BTNode的指標
    bt=NULL; //根結點初始化為空
    int k; //用k記錄左右兒子，1為左，2為右
    BTNode *p=NULL; //用p存盤讀取到的字符
    int len=strlen(str); //字串str的長度為len
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1; //k計為左兒子
            st.push(p); //入堆疊
            continue;
        }
        else if(str[i]==')'){
            st.pop(); //出堆疊
            continue; //繼續往后看
        }
        else if(str[i]==','){
            k=2; //k計為右兒子
            continue;
        }
        else{
            p=new BTNode(); //為p申請空間
            p->data=str[i]; //賦值
            p->lc=p->rc=NULL;
            if(bt==NULL) //如果bt為空，代表p為最開始的根結點
                bt=p;
            else
                if(k==1) //之前讀取到左括號，說明p是左孩子
                    st.top()->lc=p;
                else if(k==2) //之前讀取到逗號，說明p是右孩子
                    st.top()->rc=p;
        }
    }
}

從左到右遍歷葉子結點

一看到從左到右，我們就可以聯想到先序遍歷，但先序遍歷是遍歷整棵樹，無法做到只遍歷葉子結點，怎么處理呢？

~~有句古話說的好，既然打不過，就加入他們吧，~~既然的確無法做到，那我們就干脆讓它痛痛快快地遍歷完整棵樹，然后只從中利用對我們有用的部分，在每次訪問結點的時候，都判斷一下它是不是葉結點，如果不是就繼續正常遍歷，如果是就拿出來用，由于我們將會多次用到從左到右的葉子結點序列，所以干脆把它們的地址存起來，用的時候直接找陣列即可

BTNode *saveLeaf[100];
int h=0; //作為saveLeaf的下標
void findLeaf(BTNode* bt){ //找葉子結點的函式findLeaf，基于先序遍歷
    if(bt!=NULL){
        if(bt->lc==NULL&&bt->rc==NULL){
            saveLeaf[h]=bt;
            h++;
            return;
        }
        findLeaf(bt->lc);
        findLeaf(bt->rc);
    }
}

只要執行一遍這個函式，我們就可以得到一個裝有從左到右的葉子結點的指標陣列，

從左到右、從下到上遍歷整棵樹

直接遍歷我們不會，所以我們借鑒一下上個問題的解決方案：加入他們

我們做這樣一個假設——假設我們可以在訪問每個節點的時候，方便地知道它是第幾層的節點，那么我們就可以多次進行先序遍歷，第一次先序遍歷只解決最后一層的問題，第二次先序遍歷只解決倒數第二層的問題，以此類推，假設樹的深度為dep，那么我們只要進行dep次先序遍歷，就可以實作從下到上、從左到右地遍歷整棵樹，

這樣，我們的任務又被拆成了兩個小任務：

• 怎么樣get每個節點的深度
• 怎么樣具體實作上面的遍歷

給每個節點設定深度

我們在結點的結構中加入一項——當前節點深度dep，然后專門寫一個函式來給每個結點的dep賦值，

到此，結點的結構完整了，我們給出它的樣子：

struct BTNode{
    char data; //存大寫字母
    int q=-1; //存權值
    char c; //存小寫字母（如果有）
    int dep=1; //深度
    BTNode *lc,*rc; //左右孩子
};

賦值函式giveDep這樣寫：

void giveDep(BTNode *bt, int dep){
    if(bt!=NULL){
        bt->dep=dep; //賦值
        dep++; //因為即將訪問孩子結點，所以深度要在父節點的基礎上+1
        giveDep(bt->lc, dep);
        giveDep(bt->rc, dep);
    }
}

這樣的話，在主函式中只要執行：

giveDep(bt,1); //設根結點深度為1

就可以實作給每個節點的dep賦值了

遍歷

首先我們微微修改一下先序遍歷，使它能識別出我們指定的層數，也就是說我們需要給函式新增一個引數Dep，然后每次訪問結點的時候都把當前節點的dep和我們傳入的Dep比較，所以為了一直能這么判斷，傳入的引數Dep在遞回程序中是不可以變的，

void PreOrder2(BTNode *bt,int Dep){
    if (bt!=NULL){
        if(bt->dep==Dep) //判斷層數是不是我們想要的
            cout<<bt->data;
        PreOrder2(bt->lc,Dep);
        PreOrder2(bt->rc,Dep);
    }
}

如此，假設樹的深度為th，那么我們只要依次讓第二個引數為th、th-1、…、1，就可以實作我們的目的了，

樹的深度可以通過基本操作函式BTHeight得到，講解見基礎篇，這里直接給出代碼：

int BTHeight(BTNode *bt){
    int lch, rch; //左子樹深度lch和右子樹深度rch
    if(bt==NULL) return 0; //如果是空的，就說明沒有長度，回傳0
    else{
        lch=BTHeight(bt->lc); //左子樹的深度
        rch=BTHeight(bt->rc); //右子樹的深度
        if(lch>rch)return lch+1;
        else return rch+1;
    }
}

在主函式中，我們這樣寫：

int h=BTHeight(bt);
for(int i=h;i>0;i--)
    PreOrder(bt,i);

完事兒

逐個實作題目要求

上面寫過的函式，我就直接呼叫了啊

用括號表示法建樹

BTNode *bt;
cin>>str;
CreateBTree(bt,str);

輸入陣列v和u

方法不唯一，我的辦法是先通過基本操作函式LeafCount獲得葉子結點的個數n，再精確地輸入n個字符/數

int n=LeafCount(bt);
for(int i=0;i<n;i++)
    cin>>v[i];
for(int i=0;i<n;i++)
    cin>>u[i];

其中基本操作函式LeafCount的講解見基礎篇，這里直接給出代碼

int LeafCount(BTNode *bt){
    int num1,num2;
    if(bt==NULL)
        return 0;
    else if(bt->lc==NULL&&bt->rc==NULL)
        return 1;
    else{
        num1=LeafCount(bt->lc);
        num2=LeafCount(bt->rc);
        return num1+num2;
    }
}

從左到右輸出非葉子結點

因為要找的是“非葉子結點”，所以我們只要基于上面的PreOrder2函式，給它添加一個判斷函式是不是葉子結點的功能，就可以實作這一步的任務，因為非葉子結點也用了兩次，所以我們干脆也把它們存起來，

BTNode *saveNotLeaf[100]; //用于存盤
int hn=0; //下標
void findNotLeaf(BTNode *bt,int Dep){
    if (bt!=NULL){
        if(bt->dep==Dep&&(bt->lc!=NULL||bt->rc!=NULL)){
            saveNotLeaf[hn]=bt;
            hn++;
        }
        findNotLeaf(bt->lc,Dep);
        findNotLeaf(bt->rc,Dep);
    }
}

在主函式中，記得要先給每個節點的dep賦值

giveDep(bt,1);  //賦值函式，還記得吧？
int th=BTHeight(bt);
for(int i=th;i>0;i--)
    findNotLeaf(bt,i);
cout<<endl;

從左到右輸出所有非葉子結點的權值

要有權值才可以輸出呀，所以我們寫一個函式計算所有節點的權值，計算權值的規則還記得吧？不記得的話就上去看看

一點都不復雜，因為有th層，執行一次先序遍歷，可以求出每個有權結點的父節點權值，我們只要走th次先序遍歷，就一定可以算出每個節點的權值

void giveQ(BTNode *&bt){
    if(bt!=NULL&&bt->lc!=NULL&&bt->rc!=NULL){
        bt->q=bt->lc->q+bt->rc->q;
        //cout<<bt->data<<" - "<<bt->q<<endl;
        giveQ(bt->lc);
        giveQ(bt->rc);
    }
}

需要注意的是，我們要先把葉子結點的權值設定好，再執行giveQ函式，主函式里：

findLeaf(bt);//找到所有的葉子結點
for(int i=0;i<h;i++)
    saveLeaf[i]->q=u[i]; //給葉子結點賦權
for(int i=0;i<th;i++) //執行th次
    giveQ(bt);
for(int i=0;i<hn;i++)
    cout<<saveNotLeaf[i]->q<<" "; //直接呼叫上一問保存好的陣列
cout<<endl;

從左到右輸出每個葉子結點

由于在上一問里已經執行過findLeaf函式，這一問直接輸出即可

for(int i=0;i<h;i++)
    cout<<saveLeaf[i]->data<<" ";
cout<<endl;

至此我們已經完成了三行輸出，就差一行了，加油！

輸出每個葉子結點的哈夫曼編碼

得先把哈夫曼編碼計算出來，才能輸出，

計算規則沒忘吧？

我們用堆疊的結構來實作哈夫曼編碼的計算，思路是這樣的：

• 根據下一步訪問的結點，將對應編碼入堆疊：
  • 訪問左孩子，則0入堆疊；
  • 訪問右孩子，則1入堆疊；
• 如果找到對應結點的編碼，結束
• 如果沒找到，當前堆疊頂編碼出堆疊

我們以找結點G的哈夫曼編碼為例

• 訪問B，0入堆疊；
• 訪問D，0入堆疊；
• 訪問F，0入堆疊；
• F無法繼續訪問且沒找到G，當前堆疊頂元素0出堆疊；
• 訪問G，1入堆疊；
• 找到G，當前堆疊內序列001即為G的哈夫曼編碼，輸出結果

代碼實作

void printSTA(stack<int> s){ //用來倒序輸出堆疊的函式
    int a[100],h=0;
    while (!s.empty())
        a[h++]=s.top(),s.pop();
    for(int i=h-1;i>=0;i--)
        cout<<a[i];
    cout<<" ";
}

stack<int> ans; //堆疊，需要頭檔案<stack>
void printHFM(BTNode *bt,char tag){
    if(bt!=NULL){
        if(bt->lc==NULL&&bt->rc==NULL&&bt->data!=tag){
            return;
        }
        if(bt->data==tag){
            printSTA(ans); //輸出
            return;
        }
        ans.push(0);
        printHFM(bt->lc,tag);
        ans.pop(); //0出堆疊
        ans.push(1);
        printHFM(bt->rc,tag);
        ans.pop(); //1出堆疊
    }
}

主函式內：

for(int i=0;i<h;i++)
    printHFM(bt,saveLeaf[i]->data);

大功告成！

最終代碼

#include <iostream>
#include <stack>
#include <cstring>
using namespace std;
struct BTNode{
    char data;
    int q=-1;
    char c;
    int dep=1;
    BTNode *lc,*rc;
};
char str[100],v[100];
int u[100];
void CreateBTree(BTNode *&bt,char *str){
    stack<BTNode*> st;
    bt=NULL;
    int k;
    BTNode *p=NULL;
    int len=strlen(str);
    for(int i=0;i<len;i++){
        if(str[i]=='('){
            k=1;
            st.push(p);
            continue;
        }
        else if(str[i]==')'){
            st.pop();
            continue;
        }
        else if(str[i]==','){
            k=2;
            continue;
        }
        else{
            p=new BTNode();
            p->data=str[i];
            p->lc=p->rc=NULL;
            if(bt==NULL)
                bt=p;
            else
            if(k==1)
                st.top()->lc=p;
            else if(k==2)
                st.top()->rc=p;
        }
    }
}

BTNode *saveLeaf[100];
int h=0; //作為saveLeaf的下標
void findLeaf(BTNode* bt){
    if(bt!=NULL){
        if(bt->lc==NULL&&bt->rc==NULL){
            saveLeaf[h]=bt;
            h++;
            return;
        }
        findLeaf(bt->lc);
        findLeaf(bt->rc);
    }
}
void giveDep(BTNode *bt,int dep){
    if(bt!=NULL){
        bt->dep=dep;
        dep++;
        giveDep(bt->lc,dep);
        giveDep(bt->rc,dep);
    }
}
BTNode *saveNotLeaf[100];
int hn=0; //下標
void findNotLeaf(BTNode *bt,int Dep){
    if (bt!=NULL){
        if(bt->dep==Dep&&(bt->lc!=NULL||bt->rc!=NULL)){
            saveNotLeaf[hn]=bt;
            hn++;
        }
        findNotLeaf(bt->lc,Dep);
        findNotLeaf(bt->rc,Dep);
    }
}

int LeafCount(BTNode *bt){
    int num1,num2;
    if(bt==NULL)
        return 0;
    else if(bt->lc==NULL&&bt->rc==NULL)
        return 1;
    else{
        num1=LeafCount(bt->lc);
        num2=LeafCount(bt->rc);
        return num1+num2;
    }
}

int BTHeight(BTNode *bt){
    int lch, rch; //左子樹深度lch和右子樹深度rch
    if(bt==NULL) return 0; //如果是空的，就說明沒有長度，回傳0
    else{
        lch=BTHeight(bt->lc); //左子樹的深度
        rch=BTHeight(bt->rc); //右子樹的深度
        if(lch>rch)return lch+1;
        else return rch+1;
    }
}

void giveQ(BTNode *&bt){
    if(bt!=NULL&&bt->lc!=NULL&&bt->rc!=NULL){
        bt->q=bt->lc->q+bt->rc->q;
        giveQ(bt->lc);
        giveQ(bt->rc);
    }
}
void printSTA(stack<int> s){ //用來倒序輸出堆疊的函式
    int a[100],h=0;
    while (!s.empty())
        a[h++]=s.top(),s.pop();
    for(int i=h-1;i>=0;i--)
        cout<<a[i];
    cout<<" ";
}

stack<int> ans; //堆疊，需要頭檔案<stack>
void printHFM(BTNode *bt,char tag){
    if(bt!=NULL){
        if(bt->lc==NULL&&bt->rc==NULL&&bt->data!=tag){
            return;
        }
        if(bt->data==tag){
            printSTA(ans); //輸出
            return;
        }
        ans.push(0);
        printHFM(bt->lc,tag);
        ans.pop(); //0出堆疊
        ans.push(1);
        printHFM(bt->rc,tag);
        ans.pop(); //1出堆疊
    }
}

void DestoryBTree(BTNode *&bt){
    if(bt!=NULL){
        DestoryBTree(bt->lc);
        DestoryBTree(bt->rc);
        delete bt;
    }
}

int main()
{
    BTNode *bt=new BTNode();
    cin>>str;
    CreateBTree(bt,str);
    int n=LeafCount(bt);
    for(int i=0;i<n;i++)
        cin>>v[i];
    for(int i=0;i<n;i++)
        cin>>u[i];

    giveDep(bt,1);
    int th=BTHeight(bt);
    for(int i=th;i>0;i--)
        findNotLeaf(bt,i);
    for(int i=0;i<hn;i++)
        cout<<saveNotLeaf[i]->data<<" ";
    cout<<endl;

    findLeaf(bt);
    for(int i=0;i<h;i++)
        saveLeaf[i]->q=u[i];
    for(int i=0;i<th;i++)
        giveQ(bt);
    for(int i=0;i<hn;i++)
        cout<<saveNotLeaf[i]->q<<" ";
    cout<<endl;

    for(int i=0;i<h;i++)
        cout<<saveLeaf[i]->data<<" ";
    cout<<endl;

    for(int i=0;i<h;i++)
        printHFM(bt,saveLeaf[i]->data);

    DestoryBTree(bt);
    return 0;
}

關于代碼完善的思路

別看字數多、代碼多，但其實也沒那么難

這個思路其實是簡化版，只考慮了除葉子結點外，每個節點都有左右孩子的情況，更改其中的幾個非葉結點判斷（比如權值計算函式），就可以把范圍擴展到“每個節點不一定都有右孩子，但必須有左孩子”；如果想擴展到全適用，只要在建樹時假設它有，然后在處理時加一步判斷，或通過給予優先級的方法處理即可，

我提交過上面的解法，也成功AC了，咱們對二叉樹的要求不高，和我的解法難度類似的題一般不會考察，所以核心目的還是通過這種拐著彎兒的思路，更加熟練地運用二叉樹的基本操作，

最后提醒一句：**上面的總結代碼一定不要直接抄！**一共187行的代碼，如果完全一樣，你就等著原地去世吧！