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

題目鏈接：傳送門

題面

描述

在這里插入圖片描述

輸入

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

輸出

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

樣例輸入

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行的代碼，如果完全一樣，你就等著原地去世吧！

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/198352.html

標籤：python

上一篇：中綴運算式轉后綴運算式演算法

下一篇：LeetCode動態規劃一：基本框架

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

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

題面

描述

輸入

輸出

樣例輸入

樣例輸出

題解

題意

思路決議及對應代碼

建樹

從左到右遍歷葉子結點

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

給每個節點設定深度

遍歷

逐個實作題目要求

用括號表示法建樹

輸入陣列v和u

從左到右輸出非葉子結點

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

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

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

代碼實作

最終代碼

關于代碼完善的思路

輸入陣列`v`和`u`