啊呀呀，不小心又?jǐn)喔煲粋€月了，我還是認(rèn)真每天學(xué)習(xí)滴，最近還是香瓜，菜瓜，西瓜，羊角蜜不能停口啊，哈哈，二叉樹這一章真是硬茬，難啃啊。

樹和二叉樹

樹的定義

• 樹的深度：樹中節(jié)點的最大層次

• 有序樹 ： 樹中結(jié)點的各子樹從左至右有次序 （ 最左邊的為第一個孩子 ）

• 無序樹 ： 樹中結(jié)點的各子樹無次序 。

• 森林 ： 是 m (m>=0) 棵互不相交的樹的集合, 把根節(jié)點刪除就變成了森林，一棵樹可以看成是一個特殊的森林，給森林中的各子樹加上一個雙親結(jié)點 ， 森林就變成了樹 。

• 樹一定是森林，但是森林不一定是樹。

• 線性結(jié)構(gòu)和樹結(jié)構(gòu)的比較

二叉樹的定義

二叉樹是n（ n>=0 ）個結(jié)點的有限集 ， 它或者是空集 (n=0),
或者由一個根結(jié)點及兩棵互不相交的分別稱作這個根的左子樹和右子樹的二叉樹組成 。

特點:

1. 每個結(jié)點最多有倆孩子 （ 二叉樹中不存在度大于 2 的結(jié)點）

2. 子樹有左右之分，其次序不能顛倒

3. 二叉樹可以是空集合 ，根可以有空的左子樹或空右子樹 。

4. 注意二叉樹不是樹的特殊情況 ， 它們是兩個概念。(二叉樹分左右次序而樹不分)
   

二叉樹的性質(zhì)

性質(zhì)1

在二叉樹的第i層上至多有2^i-1個節(jié)點(i>=1)，至少有1個結(jié)點

性質(zhì)2

深度為k的二叉樹至多有2^k-1個節(jié)點(k>=1), 至少有k個結(jié)點(單支樹)

性質(zhì)3

對任何一顆二叉樹T,如果其葉子數(shù)為n0,度為2的結(jié)點數(shù)為n2,則n0=n2+1

滿二叉樹

一棵深度為k且有2^k-1個結(jié)點的二叉樹稱為滿二叉樹。

特點 ：

1. 每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)（即每層都滿）
2. 葉子節(jié)點全部在最底層
3. 對滿二叉樹結(jié)點位置進(jìn)行編號： 從根結(jié)點開始 ， 自上而
   下 ， 自左而右，每一結(jié)點位置都有元素 。

完全二叉樹（complete binary tree）

定義：深度為k的具有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號為1~n的結(jié)點一一對應(yīng)時，稱為完全二叉樹。

注： 在滿二叉樹中 ， 從最后一個結(jié)點開始 ，連續(xù)去掉任意個結(jié)點 ， 即是一棵完全二叉樹 ．
一定是連續(xù)的去掉 ！ ！ ！

特點：

• 葉子只可能分布在層次最大的兩層上 。
• 對任一結(jié)點 ， 如果其右子樹的最大層次為 i,
  則其左子樹的最大層次必為 i 或 i + 1 。

性質(zhì)4

具有n個結(jié)點的完全二叉樹的深度為$?lo{g}_{2}n?+1$

注：$?x?$稱作x的底，表示不大于x的最大整數(shù)

性質(zhì)5

如果對一棵有n個結(jié)點的完全二叉樹(深度為$?lo{g}_{2}n?$+ 1)的結(jié)點按層序編號(從第一層到$?lo{g}_{2}n?$+ 1層，每層從左到右)，則對任一結(jié)點i(1$\le$i$\le$n),有:

1. 如果 i = 1, 則結(jié)點 i 是一叉樹的根 ， 無雙親 ； 如果 i > 1 ， 則其雙親是結(jié)點 $?i/2?$

2. 如果 2i > n 則結(jié)點i為葉子結(jié)點，無左孩子；否則，其左孩子是結(jié)點 2i.

3. 如果 2i + 1 > n則結(jié)點 i 無右孩子；否則，其右孩 子是結(jié)點 2i + 1 。

性質(zhì)5表明了完全二叉樹中雙親結(jié)點編號和孩子結(jié)點編號之間的關(guān)系。

二叉樹的存儲

順序存儲

按照滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素

// 二叉樹順序存儲表示
#define MAXSIZE 100
Typedef TElemType SqBiTree[MAXSIZE]
SqBiTree bt;

缺點：在右單支樹情況下存儲效率非常低

只適合滿二叉樹和完全二叉樹(結(jié)點關(guān)系蘊含存儲位置)

二叉樹鏈?zhǔn)酱鎯?/h5>

二叉鏈表

用于經(jīng)常找后繼(孩子結(jié)點)

// 二叉鏈表存儲結(jié)構(gòu)
typedef struct BiNode{
	TElemType data;
	struct BiNode *lchild,*rchild;
}BiNode, *BiTree;

在n個結(jié)點的二叉鏈表中，有n+1個空指針域

分析 ： n個結(jié)點的二叉鏈表必有 2n 個鏈域 。 除根結(jié)點外，每個結(jié)點有且僅有一個雙親 ，所以只會有 n - 1 個結(jié)點的鏈域存放指針，指向非空子女結(jié)點 。

空指針數(shù)目 = 2n-(n-1)=n+1

三叉鏈表

用于經(jīng)常查找 前趨(雙親節(jié)點)

遍歷二叉樹

遍歷是順著某條路徑巡防二叉樹中的結(jié)點，每個節(jié)點都僅且訪問一次，最后得到樹中所有結(jié)點的一個線性排列，是樹結(jié)構(gòu)插刪改查，排序的前提，是二叉樹運算的基礎(chǔ)和核心。

遍歷方法

L:遍歷左子樹， D:訪問根節(jié)點， R:遍歷右子樹

若規(guī)定先左后右，則有下面三種算法：(根據(jù)根被訪問的順序)

DLR - 先(根)序遍歷

LDR - 中(根)序遍歷

LRD - 后(根)序遍歷

• 先序遍歷 ABELDHMIJ
• 中序遍歷 ELBAMHIDJ
• 后序遍歷 LEBMIHJDA

小口訣：

先序有根寫根，無根寫左，無左寫右
中序有左寫左，無左寫根，最后寫右
后續(xù)有左寫左，無左寫右，最后寫根

擴(kuò)展：

根據(jù)遍歷序列確定二叉樹

• 若二叉樹中的各結(jié)點的值均不相同，則先序、中序，后序遍歷的結(jié)果都是唯一的。
• 由二叉樹的先序序列+中序序列，或者后續(xù)序列+中序序列 可以確定唯一一棵二叉樹。

已知先序和中序如下，畫出二叉樹：

遍歷的算法實現(xiàn)

先序遍歷

Status PreOrderTraverse(BiTree T){
    if (T==None) return OK; //空樹情況
    else {
        visit(T); //訪問根節(jié)點
        // printf("%d\t", T->data) 訪問根節(jié)點數(shù)據(jù)
        PreOrderTraverse(T->lchild); //遞歸遍歷左子樹
        PreOrderTraverse(T->rchild); //遞歸遍歷右子樹
    }
}

中序遍歷

Stataus InOrderTraverse(BiTree T){
    if (T==None) return OK; // 空二叉樹
    else {
        InOrderTraverse(T->lchild); // 遞歸中序遍歷左子樹
        visit(T); // 訪問根節(jié)點
        InOrderTraverse(T->rchild); // 遞歸中序遍歷右子樹
    }
}

后序遍歷

Stataus PostOrderTraverse(BiTree T){
    if (T==None) return OK; // 空二叉樹
    else {
        PostOrderTraverse(T->lchild); // 遞歸后序遍歷左子樹
        PostOrderTraverse(T->rchild); // 遞歸后序遍歷右子樹
        visit(T); // 訪問根節(jié)點
    }
}

遍歷算法分析

如果上面三種算法去掉輸出語句(visit(T)),那么從遞歸角度看三種算法是完全一樣的，折算中算法訪問路徑是相同的，只是訪問時機(jī)不同。

• 時間復(fù)雜度O(n), 每個結(jié)點只訪問一次
• 空間復(fù)雜度O(n)，棧占用的最大輔助空間

中序遍歷二叉樹非遞歸算法

中序遍歷的非遞歸算法的關(guān)鍵：在中序遍歷過某結(jié)點的整個左子樹后，如何找到該結(jié)點的根以及右子樹。

基本思想：

1. 建立一個棧
2. 根結(jié)點進(jìn)棧，遍歷左子樹
3. 根結(jié)點出棧，輸出根結(jié)點，遍歷右子樹

// 中序遍歷非遞歸算法
Status InOrderTraverse(BiTree T){
    BiTree *p; // 初始化一個指針p
    InitStack(S); // 初始化一個棧
    p=T; // 初始是p指向二叉樹根節(jié)點
    if (T==None) return OK; // 空二叉樹情況
    else {
        while (p || !StackEmpty(S)) { //指針p或者棧不為空時
            if (p) { // 當(dāng)p指向根節(jié)點
                Push(S,p);  // 入棧根節(jié)點
                p=p->lchild; // p指向根的左孩子
            }
            else { // 當(dāng)指針p為空，棧不為空時
                Pop(S,q); // 彈出棧頂元素
                printf("%c\t", q->data); // 輸出根節(jié)點數(shù)據(jù)
                p=q->rchild; // 指針p指向右孩子
            }
        }
        return OK;
    }
}

執(zhí)行過程

二叉樹的層次遍歷

對于一顆二叉樹，從根結(jié)點開始，按從上到下、從左到右的順序訪問每一個結(jié)點 。每一個結(jié)點僅僅訪問一次。

算法設(shè)計思路：使用一個隊列

1. 將根結(jié)點進(jìn)隊

2. 隊不空時循環(huán)：從隊列中出列一個結(jié)點 *p，訪問它；

   a. 若它有左孩子結(jié)點，將左孩子結(jié)點進(jìn)隊，

   b. 若它有右孩子結(jié)點，將右孩子結(jié)點進(jìn)隊。

定義順序循環(huán)隊列:

typedef struct SqQueue {
	BTNode data[MAXSIZE]; // 存放對中元素
	int front, rear; // 隊頭和隊尾指針
}//SqQueue // 順序循環(huán)隊列類型

算法實現(xiàn)

void LevelOrder(BTNode *b) {
    BTNode *p; SqQueue *qu; // 創(chuàng)建臨時指針p和queue的指針qu
    InitQueue(qu); // 初始化循環(huán)隊列
    enQueue(qu,b); // 將指向根節(jié)點的b元素入隊
    while (!QueueEmpty(qu)) { // 隊列不空時
        deQueue(qu, p); // 將隊首元素出隊并賦值給p
        printf("%c", p->data) 
        if (p->lchild!=None) {enQueue(qu,p->lchild)}; // 有左孩子時將其入隊
        if (p->rchild!=None) {enQueue(qu,p->rchild)}; // 有右孩子時將其入隊
    }
}

二叉樹遍歷算法的應(yīng)用

二叉樹的建立

按先序遍歷建立二叉樹的二叉鏈表

• 從鍵盤輸入二叉樹結(jié)點信息，建立二叉樹的存儲結(jié)構(gòu)
• 在建立過程中按照二叉樹先序方法建立(DLR)

// 由先序序列創(chuàng)建二叉樹
// 先序序列 例子：ABC##DE#G##F###
Status CreateBiTree(BiTree &T){
    scanf(&ch); //cin>>ch(C++)
    if (ch == '#') T == NULL;
    else {
        if (!(T=(BiTNode *)malloc(sizeof(BiTNode)))) exit(OVERFLOW); // T=new BiTNode(C++) 分配空間給根結(jié)點
        T->data=ch;  // 根結(jié)點賦值
        CreateBiTree(T->lchild); // 構(gòu)造左子樹
        CreateBiTree(T->rchild); // 構(gòu)造右子樹
    }
    return OK;
}

復(fù)制二叉樹

思想：

1. 如果是空樹，遞歸結(jié)束，
2. 否則，申請新結(jié)點空間，復(fù)制根結(jié)點
3. 遞歸復(fù)制左子樹
4. 遞歸復(fù)制右子樹

// 通過先序遍歷的順序復(fù)制一個二叉樹
int Copy(BiTree T, BiTree &NewT){
    if (T==NULL) { // 空樹則返回0
        NewT=NULL;
        return 0
    }
    else {
        NewT=new BiTNode; // 分配空間給NewT
        NewT->data = T->data; // 根結(jié)點復(fù)制
        Copy(T->lchild, NewT->lchild); // 左子樹復(fù)制
        Copy(T->rchild, NewT->rchild); // 右子樹復(fù)制
    }
}

計算二叉樹深度

如果是空樹，則深度為0，否則，遞歸計算左子樹的深度記為m，遞歸計算右子樹的深度記為n, 二叉樹的深度則為m與n的較大者加1。

// 計算二叉樹的深度
int Depth(BiTree T){
    if (T==NULL) return 0; // 空樹情況
    else {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if (m > n) return (m+1);
        else return (n+1);
    }
}

計算二叉樹結(jié)點總數(shù)

如果是空樹，則結(jié)點個數(shù)為0，否則，結(jié)點個數(shù)為左子樹的結(jié)點個數(shù) + 右子樹的結(jié)點個數(shù)再 + 1

// 計算二叉樹結(jié)點總數(shù)
int NodeCount(BiTree T){
    if (T==NULL) return 0;
    else {
        return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
    }
}

計算二叉樹葉子結(jié)點個數(shù)

如果是空樹，則葉子結(jié)點個數(shù)為 0 ，否則，為左子樹的葉子結(jié)點個數(shù) + 右子樹的葉子結(jié)點個數(shù)

// 計算二叉樹葉子結(jié)點個數(shù)
int LeafCount(BiTree T){
    if (T==NULL) return 0; // 空樹情況
    if (T->lchild==NULL & T->rchild=NULL) return 1; // 無孩子的結(jié)點為葉子結(jié)點
    else {
        return LeafCount(T->lchild) + LeafCount(T->rchild);
    }
}

線索二叉樹

利用二叉鏈表中的空指針域(無左/右孩子):

• 如果某個結(jié)點的左孩子為空，則將空的左孩子指針域改為指向其前驅(qū)，如果某結(jié)點的右孩子為空，則將空的右孩子指針域改為指向其后繼這種改變指向的指針稱為"線索".

• 加上了線索的二叉樹稱為線索二叉樹 (Threaded Binary Tree)

• 對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫線索化

為了區(qū)分lrchild和rchild指針到底指向孩子還是指向前趨后繼的指針，對二叉鏈表每個結(jié)點新增兩個標(biāo)志域ltag,rtag，并約定：

值為0，則指針指向孩子，值為1則指向前趨/后繼

結(jié)點結(jié)構(gòu)：

typedef struct BiThrNode{
    int data;
    int ltag,rtag;
    struct BiThrNode *lchild, *rchild;
} BiThrNode, *BiThrTree;

先序線索二叉樹：

中序線索二叉樹：

后序線索二叉樹：

樹和森林

定義

樹的存儲結(jié)構(gòu)

雙親表示法

特點：找雙親容易，找孩子難

C的類型描述：

• 結(jié)點結(jié)構(gòu)：

  typedef struct PTNode {
      TElemType data;
      int parent; // 雙親位置域
  }PTNode;
  

• 樹結(jié)構(gòu)：

  # define MAX_TREE_SIZE 100
  typedef struct {
      PTNode nodes[MAX_TREE_SIZE];
      int r,n; // 根結(jié)點的位置和結(jié)點個數(shù)
  }PTree;
  

孩子鏈表

特點：找孩子容易，找雙親難

把每個結(jié)點的孩子結(jié)點排列起來，看成是一個線性表，用單鏈表存儲，則n個結(jié)點有n個孩子鏈表（葉子的孩子鏈表為空表）。而n個頭
指針又組成一個線性表，用順序表（含n個元素的結(jié)構(gòu)數(shù)組）存儲。

進(jìn)化一下，加上雙親位置，變成帶雙親的孩子鏈表

孩子兄弟表示法(二叉鏈表表示法)

實現(xiàn) ： 用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點。

缺點：不好找雙親

typedef struct CSNode {
    ElemType data;
    struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;

樹和二叉樹的轉(zhuǎn)換

由于樹和二叉樹都可以用二叉鏈表作存儲結(jié)構(gòu)，則以二叉鏈表作媒介可以導(dǎo)出樹與二叉樹之間的一個對應(yīng)關(guān)系。

將樹轉(zhuǎn)換為二叉樹

1. 加線：在兄弟之間加一連線
2. 抹線：對每個結(jié)點，除了其左孩子外，去除其根節(jié)點與其余孩子之間的關(guān)系
3. 旋轉(zhuǎn)：以樹的根結(jié)點為軸心，將整樹順時針轉(zhuǎn)45度

==>樹變二叉樹：兄弟相連留長子

將二叉樹轉(zhuǎn)化為樹

1. 加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子
的右孩子。。。沿分支找到的所有右孩子，都與p的雙親用線連起來
2. 抹線：抹掉原二叉樹中雙親與右孩子之間的連線．
3. 調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)

==>二叉樹變樹：左孩右右連雙親，去掉原來右孩線

森林和二叉樹的轉(zhuǎn)換

森林轉(zhuǎn)二叉樹(二叉樹與多棵樹之間的關(guān)系)

1. 將各棵樹分別換成二叉樹
2. 將每棵樹的根結(jié)點用線相連
3. 以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)

==>森林變二叉樹：樹變二叉根相連

二叉樹轉(zhuǎn)森林

1. 抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹
2. 還原：將孤立的二叉樹還原成樹

==> 二叉樹變森林：去掉全部右孩線，孤立二叉再還原

樹的遍歷

1. 三種遍歷方式：

   • 先根（次序）遍歷：若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹

   • 后根（次序）遍歷：若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點

   • 按層次遍歷：若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。
     

2. 森林的遍歷

   

   

   

   對森林的先序遍歷可以看成依次對每棵子樹的先序遍歷然后拼在一起；

   對森林的中序遍歷可以看成依次對每棵子樹的后序遍歷然后拼在一起。

   

哈夫曼樹

David Albert Huffman - 哈夫曼編碼聞名

基本概念

• 路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的路徑。

• 結(jié)點的路徑長度：兩結(jié)點間路徑上的分支數(shù)。

• 樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和。記作： TL

• 結(jié)點數(shù)目相同的二叉樹中，完全二叉樹是路徑長度最短的二叉樹。

• 權(quán)(weight)：將樹中結(jié)點賦給一個有著某種含義的數(shù)值(eg.占比)，則這個數(shù)值稱為該結(jié)點的權(quán)。

• 結(jié)點的帶權(quán)路徑長度：從根結(jié)點到該結(jié)點之間的路徑長度與該結(jié)點的權(quán)的乘積。

• 樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和。

  

  

• 哈夫曼樹：最優(yōu)樹 - 帶權(quán)路徑長度(WPL)最短的樹

• 哈夫曼樹：最優(yōu)二叉樹 - 帶權(quán)路徑長度(WPL)最短的二叉樹

• 構(gòu)造哈夫曼樹算法在1952年提出，稱為哈夫曼算法

  

哈夫曼算法過程（構(gòu)造哈夫曼樹的方法）

1. 根據(jù)n個給定的權(quán)值{w1,w2…,wn} 構(gòu)成棵二叉樹的森林 F={T1, T2, …,Tn},其中Ti只有一個帶權(quán)為Wi的根結(jié)點。
2. 在F中選取兩棵根結(jié)點的權(quán)值最小的樹作為左右子樹，構(gòu)造一棵新的
   二叉樹 ，且設(shè)置新的二叉樹的根結(jié)點的權(quán)值為其左右子樹上根結(jié)點的權(quán)值之和。
3. 在 F 中刪除這兩棵樹，同時將新得到的二叉樹加入森林中。
4. 重復(fù)（2）和（3），直到森林中只有一棵樹為止，這棵樹即為哈夫曼樹。

? 口訣：

構(gòu)造森林全是根

選用兩小造新樹

刪除兩小添新人

重復(fù)2、3剩單根

• 包含 n 個葉子結(jié)點的哈夫曼樹中共有 2n-1 個結(jié)點。

• 包含 n 棵樹的森林要經(jīng)過 n-1 次合并才能形成哈夫曼樹，共產(chǎn)生 n-1 個新結(jié)點，且這 n-1 個新結(jié)點都是具有兩個孩子的分支結(jié)點，所以總共產(chǎn)生 n+n-1=2n-1個結(jié)點

• 哈夫曼樹的結(jié)點的度數(shù)為 0 或 2，沒有度為 1 的結(jié)點。（兩小造新人）

哈夫曼算法存儲

• 順序存儲結(jié)構(gòu) – 一維結(jié)構(gòu)數(shù)組 HuffmanTree H;

• 結(jié)點類型定義：

  typedef struct {
      int weight;
      int parent, lch, rch;
  }HTNode, *HuffmanTree;
  

  

  Note: 哈夫曼樹中共有 2n-1 個結(jié)點,不使用 0 下標(biāo)，數(shù)組大小為2n

  

哈夫曼算法實現(xiàn)

1. 初始化 HT[1…2n-1]：lch=rch=parent=O;

2. 輸入初始 n 個葉子結(jié)點：置 HT[1…n] 的 weight 值；

3. 進(jìn)行以下 n-1 次合并，依次產(chǎn)生 n-1 個結(jié)點 HT[i], i=n+1…2n-1：

   1. 在 HT[1…i-1] 中選兩個未被選過（ 從parent == 0 的結(jié)點中選 ）的 weight 最小的兩個結(jié)點 HT[s1]] 和 HT[s2], s1,s2為兩個最小結(jié)點下標(biāo)；
   2. 修改 HT[s1] 和 HT[s2] 的 parent 值： HT[s1].parent=i; HT[s2].parent=i;
   3. 修改新產(chǎn)生的 HT[i]：
      • HT[i].weight=HT[s1].weight + HT[s2].weight
      • HT[i].lch=s1; HT[i].rch=s2;

   // 哈夫曼樹的構(gòu)造 算法5.10
   void CreateHuffmanTree (HuffmanTree HT, int n) {
       if (n<=1) return;
       m=2*n-1; // 數(shù)組共2n-1個元素
       HT=new HuffmanTree[m+1]; // 下標(biāo)0不用，HT[m]表示根節(jié)點
       for (i=1;i<=m;i++) { //初始化將所有元素的左右孩子及雙親置為0
           HT[i].lch=0; HT[i].rch=0; HT[i].parent=0;
       } 
       
       for (i=1;i<=n;i++) { // 輸入前n個元素的weight值
           cin>>HT[i].weight;
       }
       
       for (i=n+1;i<=m;i++) { // 合并產(chǎn)生n-1個結(jié)點
       	Select(HT, i-1, s1, s2); // 在HK[k](1<=k<=i-1)中選擇兩個其雙親域為0，且權(quán)值最小的點，并返回他們在HT中的序號s1,s2
       	HT[s1].parent=i; HT[s2].parent=i; // 給s1,s2加上parent，相當(dāng)于從F表中刪除s1,s2
       	HT[i].lch=s1; HT[i].rch=s2; // s1,s2設(shè)為左右孩子
       	HT[i].weight=HT[s1].weight+HT[s2].weight;  // 新結(jié)點的權(quán)值為左右孩子之和
   	}
           
   }
   

哈夫曼編碼

什么是哈夫曼編碼

將文字轉(zhuǎn)換成0和1的電文進(jìn)行發(fā)送，哈夫曼編碼可以得到一種前綴碼使得電文總長最短。

方法：

1. 統(tǒng)字符集中每個字符在電文中出現(xiàn)的平均概率（概率越大，要求編碼越短）。
2. 利用哈夫曼樹的特點：權(quán)越大的葉子離根越近；將每個字符的概率值作為權(quán)值，構(gòu)造哈夫曼樹。則概率越大的結(jié)點，路徑越短。
3. 在哈夫曼樹的每個分支上標(biāo)上 0 或 1：結(jié)點的左分支標(biāo) 0 ，右分支標(biāo) 1， 把從根到每個葉子的路徑上的標(biāo)號連接起來，作為該葉子代表的字符的編碼。

自問自答：

1. 為什么哈夫曼編碼能夠保證是前綴編碼？

   ANS: 因為沒有一片樹葉是另一片樹葉的祖先，所以每個葉結(jié)點的編碼就不可能是其它葉結(jié)點編碼的前綴。

2. 為什么哈夫曼編碼能夠保證字符編碼總長最短 ？

   ANS:因為哈夫曼樹的帶權(quán)路徑長度最短，故字符編碼的總長最短 。

性質(zhì) 1 哈夫曼編碼是前綴碼

性質(zhì) 2 哈夫曼編碼是最優(yōu)前綴碼

哈夫曼編碼算法

// 哈夫曼編碼
void CreateHuffmanCode(HuffmanTree HT, HuffmanCode &HC, int n) {
    // 從葉子到根逆向求每個字符的哈夫曼編碼，存儲到編碼表HC中
    HC = new char*[n+1]; // 分配n個字符編碼的頭指針矢量
    cd = new char[n]; // 分配臨時存放編碼的動態(tài)數(shù)組空間
    cd[n-1] = "\0"; // 臨時表的最后一位不用設(shè)為結(jié)束符
    
    for (i=1;i<=n;++i) { // 逐個字符求哈夫曼編碼
        start=n-1; c=i; f=HT[i].parent; 
        while (f!=0) { // 從葉子結(jié)點開始向上回溯，直到根節(jié)點
            --start; // 每回溯一次 start的值向前指一個位置
            if (HT[f].lch == c) cd[start]="0"; // 結(jié)點c是f的左孩子，生成代碼0
            else cd[start]="1"; // 結(jié)點c是f的右孩子，生成代碼1
            c=f; f=HT[f].parent; // 向上回溯(從parent節(jié)點繼續(xù)找)
        } // 求出了第i個字符的編碼了
        HC[i]=new char[n-start]; // 為第i個字符的編碼分配空間
        strcpy(HC[i], &cd[start]); // 將求得的編碼從臨時空間cd復(fù)制到HC當(dāng)前行中
    }
    delete cd; // 釋放臨時空間
} // CreateHuffmanCode

應(yīng)用舉例

TO BE CONTINUED…文章來源地址http://www.zghlxwxcb.cn/news/detail-576767.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)與算法基礎(chǔ)（青島大學(xué)-王卓）(6)的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！