目錄 第五章 ：樹和二叉樹

第一節(jié)：樹的定義及相關術語

1.1 定義
1.2 特點
1.3 形式化
1.4 相關術語
1.5 樹的基本操作

第二節(jié)：二叉樹

2.1 基本概念
2.2 存儲結(jié)構
2.3 二叉樹基本操作
2.4 二叉樹的遍歷

第三節(jié)：樹與森林

3.1 樹的存儲
3.2 樹挡鞍、森林與二叉樹的相互轉(zhuǎn)換
3.3 樹和森林的遍歷

第四節(jié)：最優(yōu)二叉樹——哈夫曼樹

4.1 基本概念
4.2 哈夫曼樹的構造算法
4.3 哈夫曼編碼
4.4 哈夫曼編碼算法實現(xiàn)

本章小結(jié)

第五章 ：樹和二叉樹

樹和圖是兩種重要的非線性結(jié)構灵份。線性結(jié)構中結(jié)點具有唯一前驅(qū)和唯一后繼的關系肮街，而非線性結(jié)構中結(jié)點之間的關系不再具有這種唯一性筋粗。

其中截珍，樹形結(jié)構中結(jié)點間的關系是前驅(qū)唯一而后繼不唯一凛捏，即元素之間是一對多的關系；在圖結(jié)構中結(jié)點之間的關系是前驅(qū)烦磁、后繼均不唯一养匈，因此也就無所謂前驅(qū)、后繼了都伪。

直觀地看呕乎，樹形結(jié)構既有分支關系，又具有層次關系陨晶，它非常類似于自然界中的樹猬仁。樹形結(jié)構在現(xiàn)實世界中廣泛存在，如：家譜先誉、行政組織機構等都用樹形表示湿刽。計算機領域的DOS和Windows操作系統(tǒng)中對磁盤文件的管理就采用了樹形目錄結(jié)構；在數(shù)據(jù)庫中褐耳，樹形結(jié)構也是數(shù)據(jù)的重要組織形式之一诈闺。

第一節(jié)：樹的定義及相關術語

1.1 定義

樹（tree）是n（n>=0）個結(jié)點的有限集合。當n=0時铃芦，該集合滿足以下條件：

（1）有且只有一個特殊的結(jié)點稱為樹的根（root）雅镊，根結(jié)點沒有直接前驅(qū)結(jié)點，但有零個或多個直接后繼結(jié)點刃滓。

（2）跟結(jié)點之外的其余n-1個結(jié)點被分成m(m>0)個互相不相交的集合T1漓穿、T2、···注盈、Tm，其中每一個集合Ti（1<=i<=m）本身又是一棵樹叙赚。樹T1老客，T2，···震叮，Tm稱為根節(jié)點的子樹胧砰。

*可以看出，在樹的定義中用了遞歸概念苇瓣，即用樹來定義樹尉间。因此，樹形結(jié)構的算法也常常使用遞歸方法。

1.2 特點

（1）樹的根結(jié)點沒有直接前驅(qū)哲嘲，除根結(jié)點之外的所有結(jié)點有且只有一個直接前驅(qū)贪薪。

（2）樹中所有結(jié)點可以有零個或多個直接后繼。

1.3 形式化

樹的形式化二元組為：T = （D眠副，R）画切。其中，D為樹T中結(jié)點的集合囱怕；R為樹中結(jié)點之間關系的集合霍弹。當樹T為空時，D為空娃弓；當樹T不為空樹時典格，有：D = {Root U Df }，Root為樹T的根結(jié)點台丛，Df為樹T的根Root的子樹集合耍缴。

當樹T的結(jié)點個數(shù)n<=1時，R為空齐佳；當樹T 中結(jié)點個數(shù)n>1時有：R={<Root,ri>,i=1,2,···私恬，m}。其中炼吴，Root為樹T的根節(jié)點本鸣，ri 是樹T的根結(jié)點Root的子樹Ti 的根結(jié)點。

下圖是一顆具有9個結(jié)點（ABCDEFGHI）的數(shù)T：

image.png

二元組：T = ({A硅蹦，B荣德，C，D童芹，E涮瞻，F(xiàn)，G假褪，H署咽，I },{<A,B> ,<A ,C>,<B,D>,<B,E>,<B,F>,<C,G>,<E,H>,<E,I>})

其中，以<A,B>為例生音，A是B的直接前驅(qū)宁否，B是A的直接后繼，也稱為樹的一條分支缀遍。

結(jié)點A為樹T的根結(jié)點慕匠，除根結(jié)點A之外的其余結(jié)點分為兩個不相交的集合：T1 = { B,D,E,F,H,I} 和 T2={C,G}。它們倆構成了結(jié)點A的兩棵子樹域醇，T1和T2本身也是一棵樹台谊，例如子樹T1的根結(jié)點為B,其余結(jié)點又分為三個不相交的集合即構成了結(jié)點B的三棵子樹蓉媳。

1.4 相關術語

（1）結(jié)點：包含一個數(shù)據(jù)元素及若干指向其他結(jié)點的分支信息的數(shù)據(jù)結(jié)構。

（2）結(jié)點的度：結(jié)點所擁有的子樹的個數(shù)稱為該結(jié)點的度锅铅。

（3）葉子結(jié)點：度為0的結(jié)點稱為葉子結(jié)點酪呻，或者稱為終端結(jié)點。

（4）分支結(jié)點：度不為0的結(jié)點稱為分支結(jié)點狠角，或者稱為非終端結(jié)點号杠。一棵樹的結(jié)點除葉子結(jié)點外，其余的結(jié)點都是分支結(jié)點丰歌。

（5）孩子結(jié)點姨蟋、雙親結(jié)點、兄弟結(jié)點：樹中一個結(jié)點的子樹的根結(jié)點稱為這個結(jié)點的孩子結(jié)點立帖，這個結(jié)點稱為孩子結(jié)點的雙親結(jié)點眼溶。具有同一個雙親結(jié)點的孩子結(jié)點互稱為兄弟結(jié)點。

（6）路徑晓勇、路徑長度：設n1堂飞，n2，···绑咱，nk為一棵樹的結(jié)點序列绰筛，若結(jié)點ni是ni+i的雙親結(jié)點（1<=i <k）,則把n1，n2描融，···铝噩，nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1窿克。

（7）祖先骏庸、子孫：在樹中，如果有一條路徑從結(jié)點M到結(jié)點N年叮，那么M就稱為N的祖先具被，而N稱為M的子孫。

（8）結(jié)點的層次：規(guī)定樹的根結(jié)點的層數(shù)為1只损，其余結(jié)點的層數(shù)等于它的雙親結(jié)點層數(shù)加1一姿。

（9）樹的深度（高度）：樹中所有結(jié)點的層次的最大數(shù)稱為樹的深度。

（10）樹的度：樹中所有結(jié)點度的最大值稱為該樹的度跃惫。

（11）有序樹和無序樹：如果一棵樹中結(jié)點的各子樹從左到右是有次序的叮叹，即若交互了某結(jié)點各子樹的相應位置，則構成不同的樹辈挂，稱這棵樹為有序樹；反之裹粤，則稱為無序樹终蒂。

（12）森林：m（m>=0）棵不想交的樹的集合稱為森林蜂林。自然界中樹和森林是不同的概念，但在數(shù)據(jù)結(jié)構中拇泣，樹和森林只有很小的差別噪叙。任何一棵樹，刪去根結(jié)點就變成了森林霉翔；反之睁蕾，給森林增加一個統(tǒng)一的根結(jié)點，森林就變成一棵樹债朵。

1.5 樹的基本操作

通常有以下幾種：

1. Initiate(t）：初始化一棵樹t子眶。
2. Root(x)：求結(jié)點x所在樹的根結(jié)點。
3. Parent(t,x) ：求樹t中結(jié)點x的雙親結(jié)點序芦。
4. Child(t,x,i)：求樹t中結(jié)點x的第i個孩子結(jié)點臭杰。
5. RightSibling(t,x）:求樹t中結(jié)點x右邊的第一個兄弟結(jié)點，也稱右兄弟結(jié)點谚中。
6. Insert(t,x,i,s)：把以s為根結(jié)點的樹插入到樹t中作為結(jié)點x的第i棵子樹渴杆。
7. Delete(t,x,i)：在樹t中刪除結(jié)點x的第i棵子樹。
8. Traverse(t)：是樹的遍歷操作宪塔，即按某種方式訪問樹t中的每個結(jié)點磁奖，且使每個結(jié)點只被訪問一次。遍歷操作是非線性結(jié)構中非常常用的基本操作某筐，許多對樹的操作都是借助該操作實現(xiàn)的比搭。

第二節(jié)：二叉樹

二叉樹是一種簡單又非常重要的樹形結(jié)構。由于任何數(shù)都可以轉(zhuǎn)換為二叉樹進行處理来吩，而二叉樹又有許多好的性質(zhì)敢辩，非常適合于計算機處理，因此二叉樹也是數(shù)據(jù)結(jié)構研究的重點弟疆。

2.1 基本概念

二叉樹（Binary Tree）是有n個結(jié)點的有限集合戚长，該集合或者為空、或者由一個稱為根（Root）的結(jié)點及兩個不相交怠苔、被分別稱為根結(jié)點的左子樹和右子樹的二叉樹組成同廉。當集合為空時，稱該二叉樹為空二叉樹柑司。一顆二叉樹中每個結(jié)點只能含有0迫肖、1或2個孩子結(jié)點，而且孩子節(jié)點分左攒驰、右孩子蟆湖。

滿二叉樹：在一棵二叉樹中，如果所有分支結(jié)點都存在左子樹和右子樹玻粪，并且所有葉子結(jié)點都在同一層上隅津，這樣的一棵二叉樹稱為滿二叉樹诬垂。

完全二叉樹：一棵深度為k的有n個結(jié)點的二叉樹，對樹中的結(jié)點按從上至下伦仍、從左到右的順序進行編號结窘，如果編號為i(i<=n)的結(jié)點與滿二叉樹中編號為i的結(jié)點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹充蓝。其特點是:葉子結(jié)點只能出現(xiàn)在最下層和次下層隧枫，且最下層的葉子結(jié)點在樹的左部。顯然谓苟，一棵滿二叉樹必定是一棵完全二叉樹官脓，而完全二叉樹未必是滿二叉樹。

2.2 存儲結(jié)構

（1）順序存儲結(jié)構：用一組連續(xù)的存儲單元存放二叉樹中的結(jié)點娜谊。一般按照二叉樹結(jié)點從上至下确买、從左到右的順序存儲。對于一般的二叉樹纱皆，如果仍按從上至小湾趾、從左到右的順序?qū)渲械慕Y(jié)點順序存儲在一維數(shù)組中，則數(shù)組元素下標之間的關系不能反映二叉樹中結(jié)點之間的邏輯關系派草，只有添加一些并不存在的空結(jié)點搀缠，使之成為一棵完全二叉樹的形式，然后用一維數(shù)組順序存儲近迁。顯然艺普，這種存儲對于需增加許多空結(jié)點才能將一棵二叉樹改造成為一棵完全二叉樹的存儲時，會造成空間的大量浪費鉴竭，不宜用順序存儲結(jié)構歧譬。

（2）鏈式存儲結(jié)構：用鏈式結(jié)構來表示一棵二叉樹，即用鏈指針來指示其元素的邏輯關系搏存。

二叉鏈表存儲瑰步，每個結(jié)點由三個域組成，除了數(shù)據(jù)域外璧眠，還有兩個指針域缩焦，分別用來給出該結(jié)點左孩子和右孩子所在的鏈結(jié)點的存儲地址。其中责静，data域存放結(jié)點的數(shù)據(jù)信息袁滥；Lchild 與Rchild分別存放指向左孩子和右孩子的指針，指針域為空為^/NULL灾螃。

image.png

2.3 二叉樹基本操作

1题翻、Initiate(bt）：建立一棵空二叉樹。

2腰鬼、Create（x嵌赠，lbt靴拱，rbt）：生成一棵x為根結(jié)點的樹，以lbt猾普、rbt為子樹。

3本谜、InsertL（bt初家，x，parent）：將結(jié)點x插入到樹bt中作為parent結(jié)點的左孩子結(jié)點乌助。如果parent已經(jīng)有左孩子溜在，則將x作為左孩子結(jié)點的左孩子結(jié)點。

4他托、InsertR（bt掖肋，x，parent）：插入到右孩子結(jié)點赏参。于上同理志笼。

5、DeleteL（bt把篓，parent）：在二叉樹bt中刪除結(jié)點parent的左子樹纫溃。

6、DeleteR（bt韧掩，parent）：在二叉樹bt中刪除結(jié)點parent的右子樹紊浩。

7、Search（bt疗锐，x）：在二叉樹bt中查找數(shù)據(jù)元素x坊谁。

8、Traverse（bt）：按某種方式遍歷二叉樹bt中的全部結(jié)點滑臊。

2.4 二叉樹的遍歷

遍歷操作可以使非線性結(jié)構線性化口芍。由二叉樹定義可知，一棵二叉樹由根結(jié)點及其左子樹和右子樹三部分組成简珠。因此阶界，只需依次遍歷這三部分即可遍歷整個二叉樹。若以D聋庵、L膘融、R分別表示根、左祭玉、右氧映，且以從左到右的順序遍歷為：（先）前序DLR、中序LDR脱货、后序LRD岛都。

（1）先序遍歷：先訪問根結(jié)點律姨，然后遍歷根結(jié)點的左子樹，最后遍歷根結(jié)點的右子樹臼疫。

1择份、遞歸算法如下：

void PreOrder(BiTree bt) {
    if(bt ==null) return;
    Visit(bt ->data); //得到值
    PreOrder(bt->Lchild); //先左
    PreOrder(bt->Rchild);//再右
}

按先序所得到的結(jié)點序列為：ABDGCEF

2、非遞歸算法：要在遍歷左子樹之前保存右子樹根結(jié)點的地址指針烫堤，以便在完成左子樹的遍歷后荣赶，取出右子樹根結(jié)點的地址，去遍歷這棵右子樹鸽斟。同樣在遍歷左子樹的左子樹之前拔创，也要先保存左子樹的右子樹根結(jié)點的地址，以此類推富蓄∈Ｔ铮可見，這些地址的保存和取出符合后進先出的原則立倍，所以設置一個輔助作用的棧來保存右子樹根結(jié)點的地址灭红。這個輔助棧保存所有經(jīng)過的結(jié)點指針，包括空的根指針和空的孩子指針口注。算法如下：

void PreOrderNonRec(BiTree bt) {
    Stack s;//鏈表結(jié)點地址
    BiTree p;
    Init_Stack(&s);//初始化棧s
    
    Push_Stack(&s,bt);//根結(jié)點的地址bt入棧s比伏，包括空的二叉樹
 
    while(!Empty_Stack(s)){//棧s非空執(zhí)行循序體
 
        p =Top_Stack(s);//取棧頂元素
        while(p!=NULL){
            Visit( p->data);
            Push_Stack(&s,p->Lchild);//向左走到盡頭，空左孩子指針也入棧
            p = Top_Stack(s);//取棧頂元素
        }
        Pop_Stack(&s);//空指針退棧疆导，棧中不可能有兩個連續(xù)空指針
        if(!Empty_stack(s)){
            p =Pop_Stack(&s);
            Push_stack(&s,p->Rchild);//向右走一步赁项，右孩子地址入棧
        }
    }
}    

（2）中序遍歷：先遍歷根據(jù)的左子樹，再訪問根結(jié)點澈段，最后遍歷根結(jié)點的右子樹悠菜。

1、遞歸算法：

void InOrder(BiTree bt) {
    if(bt ==NULL) return;
    InOrder(bt -> Lchild);
    Visit(bt ->data);
    InOrder(bt ->Rchild);
}

按中序遍歷所得到的結(jié)點序列為：DGBAECF

2败富、非遞歸算法：

void InOrderNonRec(BiTree bt){
    Stack s;//設棧類型為Stack
    BiTree p;
    Init_Stack(&s,bt);//初始化棧s
    Push_Stack(&s,bt);//根結(jié)點的指針bt入棧s
    
    while(!Empty_Stack(s)){
        p =Top_Stack(s);
 
        while(p!=NULL){
            Push_Stack(&s,p->Lchild);//向左走到盡頭悔醋，空左孩子指針也入棧
            p =Top_Stack(s);
        }
        p = Pop_Stack(&s);//空指針退棧
        if(!Empty_Stack(s)){
            p =Pop_Stack(&S);
            Visit(p ->data);//訪問當前根結(jié)點
            Push_Stack(&s,p->Rchild);//向右一步，右孩子指針入棧
        }
    }
}

(3）后序遍歷：先遍歷根結(jié)點的左子樹兽叮，再遍歷根結(jié)點的右子樹芬骄，最后訪問根結(jié)點。

1鹦聪、遞歸排序算法：

void PostOrder(BiTree bt){
    if(bt == NULL) return;
    PostOrder(bt ->Lchild);
    PostOrder(bt ->Rchild);
    Visit（bt ->data）;
}

2账阻、非遞歸排序算法：

void PostOrderNonRec(BiTree bt){
    Stack s;
    BiTree p,q;
    Init_Stack(&s);
    p =bt;
    do{
        while(p){//向左走到盡頭，左孩子指針入棧
            Push_Stack(&s,p);
            p = p->Lchild;
        }
        q =NULL;
        while(!Empty_Stack(s)){        
            p=Top_Stack(s);
            if(p->Rchild =NULL)||(p->Rchild ==q)){
                visit(p ->data);        
                q = p ;
                Pop_Stack(&s);
            }else{
                p =p->Rchild;
                break;
            }
        }
    }while(!Empty_Stack(s));
}

（4）層次遍歷：是指從二叉樹的第一次根結(jié)點開始泽本，從上至下逐層遍歷淘太，在同一層中，則按從左到右的順序?qū)Y(jié)點逐個訪問。得到的結(jié)果序列為：ABCDEFG蒲牧。因此撇贺，在進行層次遍歷時，對一層結(jié)點訪問完后冰抢，再按照它們的訪問次序?qū)Ω鱾€結(jié)點的左孩子和右孩子順序訪問松嘶，這樣一層一層進行，先遇到的結(jié)點先訪問挎扰，這與隊列的操作原則比較吻合喘蟆。因此，在進行層次遍歷時鼓鲁，可設置一個隊列結(jié)構，遍歷從二叉樹的根結(jié)點開始港谊，首先將根結(jié)點指針入隊列骇吭，然后從隊頭取出一個元素，每取出一個元素先訪問該元素所指的結(jié)點歧寺，若該元素所指的結(jié)點左右孩子指針非空燥狰，則將該元素所指結(jié)點的非空左孩子指針和右孩子指針順序入隊。若隊列非空斜筐，重復以上過程龙致，當隊列為空時，二叉樹的層次遍歷結(jié)束顷链。在下面算法中目代，二叉樹以二叉鏈表存儲，一維數(shù)組Queue[MAXNODE]用以實現(xiàn)隊列嗤练，變量front和rear分別表示當前隊列首元素和隊列尾元素在數(shù)組中的位置榛了。

void LevelOrder(BiTree bt){
    BiTree Queue[MAXNODE];
    int front,rear;
    
    if(bt ==NULL )return;
    
    front =1; 
    //隊列初始化    
    rear = 0;
    queue[rear] =bt;//根結(jié)點入隊
    while(front!=rear){
        front++;
        Visit(queue[front] ->data);//訪問隊首結(jié)點的數(shù)據(jù)域
        if(queue[front]->Lchild!=NULL）{
            rear++;
            queue[rear] = queue[front]->Lchild;
        }
        if(queue[front] -> Rchild!=NULL){
            rear++;
            queue[rear] = queue[front] -> Rchild;
        }
    }
}

第三節(jié)：樹與森林

3.1 樹的存儲

在計算機中，樹的存儲有很多種方式煞抬，即可以采用順序存儲結(jié)構霜大，又可以采用鏈式存儲結(jié)構，但無論采用何種存儲方式革答，都要求存儲結(jié)構不但能存儲各結(jié)點本身的數(shù)據(jù)信息战坤，還要能唯一地反映樹中各結(jié)點之間的邏輯關系。

1残拐、雙親表示法：由樹的定義可以知道途茫，樹中除根結(jié)點外的每個結(jié)點都有唯一的一個雙親結(jié)點，根據(jù)這一特性溪食，可用一組連續(xù)的存儲空間即一維數(shù)組存儲樹中的各個結(jié)點慈省，數(shù)組中的一個元素表示樹中的一個結(jié)點，數(shù)組元素為結(jié)構體類型，其中包括結(jié)點本身的信息及結(jié)構體類型边败，其中包括結(jié)點本身的信息及該結(jié)點的雙親結(jié)點在數(shù)組中的序號袱衷，樹的這種存儲方法稱為雙親表示法。存儲結(jié)構如下：

#define MAXNODE 100
typedef struct{
    elemtype data;
    int parent;
}NodeType;
NodeType t[MAXNODE];

如下圖所示笑窜，樹a的雙親表示b致燥。其中b圖中用parent域的值為-1表示該結(jié)點無雙親結(jié)點，即該結(jié)點是一個根結(jié)點排截。

image.png

樹的雙親表示法對于實現(xiàn)Parent（t嫌蚤，x）操作和Root（x）操作很方便，但若求某結(jié)點的孩子結(jié)點断傲，即實現(xiàn)Child（t脱吱，x，i）操作時认罩，則需要查詢整個數(shù)組箱蝠。此外，這種存儲方式不能反映各兄弟結(jié)點之間的關系垦垂，所以實現(xiàn)RightSibling（t宦搬，x）操作也比較困難。在實際中劫拗，如果需要實現(xiàn)這些操作间校，可在結(jié)點結(jié)構中增設存放第一個孩子的域和存放右兄弟的域，就能較方便地實現(xiàn)上述操作了页慷。

2憔足、孩子表示法：

image.png

如上圖，其主體是一個與結(jié)點個數(shù)一樣大小的一維數(shù)組酒繁，數(shù)組的每一個元素都由兩個域組成：一個域用來存放結(jié)點本身的信息四瘫，另一個用來存放指針(該指針指向由該結(jié)點孩子組成的單鏈表的首位置)。單鏈表的基本結(jié)構也由兩個域組成：一個存放孩子結(jié)點在一維數(shù)組中的序號欲逃，另一個是指針域找蜜，指向下一個孩子。顯然稳析，在孩子表示法中查找雙親比較困難洗做，查找孩子卻十分方便，故適用于對孩子操作多的應用彰居。孩子表示法的存儲結(jié)構可描述如下：

#define MAXNODE 100
typedef struct ChildNode{
    int childcode;
    struct ChildNode *nextchild;
}
typedef struct{
    elemtype data;
    struct ChildNode *firstchild;
}NodeType;
NodeType t[MAXNODE];

3诚纸、孩子兄弟表示法：

在樹中，每個結(jié)點除其信息域外陈惰，再增加兩個分別指向該結(jié)點的第一個孩子結(jié)點和右兄弟結(jié)點的指針畦徘。在這種存儲結(jié)構下，樹中結(jié)點的存儲結(jié)構可描述如下：

typedef struct TreeNode{
    elemtype data;
    struct TreeNode *firstchild;
    struct TreeNode *nextsibling;
 }NodeType;
 
//定義一棵樹
NodeType *t;

image.png

如上圖所示，該存儲結(jié)構與二叉樹的二叉鏈表結(jié)構非常相似井辆，而且事實上关筒，如果剔除了字面上的含義，其實質(zhì)是一樣的杯缺。因此樹、森林與二叉樹的轉(zhuǎn)換才得以方便地實現(xiàn)萍肆。

3.2 樹袍榆、森林與二叉樹的相互轉(zhuǎn)換

從樹的孩子兄弟表示法所示，如果設定一定的規(guī)則塘揣，就可用二叉樹結(jié)構表示樹包雀、森林，這樣對樹的操作實現(xiàn)就可以借助二叉樹存儲亲铡，利用二叉樹上的操作來實現(xiàn)才写。

1、樹轉(zhuǎn)換為二叉樹：

對于一棵無序樹奴愉，樹中結(jié)點的各孩子結(jié)點的次序是無關緊要的，而二叉樹中結(jié)點的左右孩子結(jié)點是有區(qū)別的铁孵。為避免發(fā)生混淆锭硼，約定樹中每一個結(jié)點的孩子結(jié)點按從左到右的次序順序編號。將一棵樹轉(zhuǎn)換為二叉樹的方法是：

• 樹中所有相鄰兄弟之間加一條連線蜕劝；
• 對樹中每個結(jié)點檀头，只保留它與第一個孩子結(jié)點之間的連線，刪去它與其他孩子結(jié)點之間的連線岖沛；
• 以樹的根結(jié)點為軸心暑始，將整棵樹順時針轉(zhuǎn)動一定的角度，使之結(jié)構層次分明婴削。

可以證明廊镜，樹這樣的轉(zhuǎn)換所構成的二叉樹是唯一的。轉(zhuǎn)換示意圖如下：

image.png

由上面的轉(zhuǎn)換可以看出嗤朴，在二叉樹中衡楞，左分支上的各結(jié)點在原來的樹中是父子關系，而右分支上的各結(jié)點在原來的樹中是兄弟關系。由于樹的根結(jié)點沒有兄弟眨业，所以變換后的二叉樹的根結(jié)點的右孩子必為空慷暂。

事實上，一棵樹采用孩子兄弟表示法所建立的存儲結(jié)構與它所對應的二叉樹的二叉鏈表存儲結(jié)構是完全相同的。

2筑舅、森林轉(zhuǎn)換為二叉樹：

由森林的概念可知，森林是若干棵樹的集合，只要將森林中各棵樹的根視為兄弟弊仪，每棵樹又可以用二叉樹表示，這樣森林同樣可以用二叉樹表示。方法如下：

• 將森林中的每棵樹轉(zhuǎn)換成相應的二叉樹甫恩；
• 第一棵二叉樹不動莱褒，從第二課二叉樹開始，依次把后一棵二叉樹的根結(jié)點作為前一棵二叉樹根結(jié)點的右孩子，當所有二叉樹連起來后宇色，所得到的二叉樹就是由森林轉(zhuǎn)換得到的二叉樹思币。

該方法可形式化描述為：

如果F={T1,T2,···盯蝴，Tm}是森林捧挺，則可按如下規(guī)則轉(zhuǎn)換成一顆二叉樹B={Root ,LB,RB}闽烙。

若F為空黑竞，即m=0很魂，則B為空樹遏匆；

若F非空，即m!=0惰爬，則B的根Root即為森林中第一棵樹的根Root(T1)撕瞧；B的左子樹LB是從T1中根結(jié)點的子樹森林F1={T11,T12,···丛版，T1m}轉(zhuǎn)換而成的二叉樹页畦；其右子樹RB是從森林F = {T2豫缨，T3，···舍败，Tm}轉(zhuǎn)換而成的二叉樹敬拓。轉(zhuǎn)換過程示意圖如下：

image.png

3厕诡、二叉樹轉(zhuǎn)換為樹和森林

樹和森林都可以轉(zhuǎn)換為二叉樹木人，二者不同的是：樹轉(zhuǎn)換成的二叉樹的根結(jié)點不同的是：樹轉(zhuǎn)換的二叉樹的根結(jié)點無右分支，而森林轉(zhuǎn)換后的二叉樹的根結(jié)點有右分支渔嚷。顯然這一轉(zhuǎn)換過程是可逆的形病，即可以依據(jù)二叉樹的根結(jié)點有無右分支，將一棵二叉樹還原成樹或森林司恳。方法如下：

若某結(jié)點是某雙親的左孩子扔傅，則把該結(jié)點的右孩子猎塞、右孩子的右孩子·····都與該結(jié)點的雙親結(jié)點用線連起來；
刪去原二叉樹中所有的雙親結(jié)點與右孩子結(jié)點的連線铝量；
整理由前面兩步所得到的樹或森林款违，使之結(jié)構層次分明插爹。
這一方法可形式化描述為：

如果B = {Root,LB,RB}是一棵二叉樹赠尾，則可按如下規(guī)則轉(zhuǎn)換成森林F={T1,T2,···，Tm};

若B為空寸宵，則F為空梯影；

若B非空甲棍，則森林中第一棵樹T1的根Root（T1）即為B的根Root感猛；T1中根結(jié)點的子樹森林F1是由B的左子樹LB轉(zhuǎn)換而成的森林颈走；F中除T1之外其余樹組成的森林F ={T2,T3,···咱士，Tm}是由B的右子樹RB轉(zhuǎn)換而成的森林司致。過程示意圖如下：

image.png

3.3 樹和森林的遍歷

1枣耀、樹的遍歷

（1）先根遍歷：訪問根結(jié)點捞奕，按照從左到右的順序先根遍歷根結(jié)點的每一棵樹。

（2）后根遍歷：按照從左到右的順序后根遍歷根結(jié)點的每一棵子樹院促，再訪問根結(jié)點常拓。

根據(jù)樹與二叉樹的轉(zhuǎn)換關系及樹和二叉樹的遍歷定義可以推知，樹的先根遍歷與其轉(zhuǎn)換的相應二叉樹的先序遍歷的結(jié)果序列相同宪郊；樹的后根遍歷與其轉(zhuǎn)換的相應二叉樹的中序遍歷的結(jié)果序列相同掂恕。因此樹的遍歷算法是可以采用相應二叉樹的遍歷算法來實現(xiàn)的。

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

void RootFirst(NodeTepe t){
    NodeType *p;
    if(t!=NULL){
        Visit(t -> data);//訪問根結(jié)點
        p=t->firstchild;//指向第一個孩子結(jié)點
        while(p){        
            RootFirst(p);//訪問孩子結(jié)點
            p =p->nextsibling;//指向下一個孩子結(jié)點弛槐，右兄弟結(jié)點
        }
    }
}

2懊亡、森林的遍歷

（1）前序遍歷：訪問森林中第一棵樹的根結(jié)點；前序遍歷第一棵樹的根結(jié)點的子樹丐黄；前序遍歷去掉第一棵樹后的子森林斋配。

（2）中序遍歷：遍歷第一棵樹的根結(jié)點的子樹孔飒；訪問森林中第一棵樹的根結(jié)點灌闺；去掉第一棵樹后的子森林蕉斜。

根據(jù)森林與二叉樹轉(zhuǎn)換關系及森林和二叉樹的遍歷定義可以推知，森林的前序遍歷和后序遍歷與所轉(zhuǎn)換的二叉樹的前序遍歷和中序遍歷的結(jié)果序列相同璧亮。

第四節(jié)：最優(yōu)二叉樹——哈夫曼樹

4.1 基本概念

最優(yōu)二叉樹也稱為哈夫曼樹（Huffman）,是指對于一組帶有確定權值的葉子結(jié)點及刻，構造的具有最小帶權路徑長度的二叉樹茴扁。權值是指一個與特定結(jié)點相關的數(shù)值卖丸。前面介紹過路徑和結(jié)點的路徑長度的概念嫁艇，而二叉樹的路徑長度則是指由根節(jié)點到所有葉子結(jié)點的路徑長度之和猾漫。如果二叉樹中的所有葉子結(jié)點都具有一個特定權值，則可將這一概念加以推廣。

設二叉樹具有n個帶權值的葉子結(jié)點解总，那么從根結(jié)點到各個葉子結(jié)點的路徑長度與該葉子結(jié)點相應的權值的乘積之和叫做二叉樹的帶權路徑長度(Weighted Path Length，簡稱WPL = 路徑長度X權值)颖变。

給定一組具有確定權值的葉子結(jié)點佩脊，可以 構造出不同的帶權二叉樹崔列。例如，給出4個葉子結(jié)點丈积，設其權值分別為：1,3,5,5，可以構造出形狀不同的多個二叉樹擒悬。這些形狀不同的二叉樹的帶權路徑長度各不相同归苍。如下圖所示：

image.png

a:WPL = 1X2 + 3X2 + 5X2 +5X2 = 28;

b:WPL = 1X3 + 3X3 +5X2 +5X1 = 27;

c: WPL =1X2+3X3 +5X3 + 5X1 =31;

由此可見吻氧，由相同權值的一組葉子結(jié)點所構成的二叉樹由不同形態(tài)和不同的帶權路徑長度。根據(jù)哈夫曼樹定義，一棵二叉樹要使其WPL值最小盯孙，必須使權值越大的葉子結(jié)點越靠近根節(jié)點振惰，而權值越小的葉子結(jié)點越遠離根結(jié)點仔雷。哈夫曼根據(jù)這一特點提出了一種構造最優(yōu)二叉樹的方法，這種方法的基本思想是：

• 由給定的n個權值{W1,W2,,Wn}構造n棵只有一個葉子結(jié)點的二叉樹，從而得到一個二叉樹的集合F={T1,T2,,Tn};
• 在F中選取根結(jié)點的權值最小和次小的兩棵二叉樹作為左右子樹構造一棵新樹的二叉樹它匕，這棵新的二叉樹根節(jié)點的權值為其左右子樹的根節(jié)點權值之和；
• 在集合F中刪除作為左右子樹的兩棵二叉樹窖认，并將新建立的二叉樹加入到集合F中;
• 重復上面兩部后豫柬，當F中只剩下一棵二叉樹時告希，這棵二叉樹便是所要建立的哈夫曼樹。
  下圖給出了前面提到的葉子結(jié)點權值集合為W = {1,3,5,5}的哈夫曼樹的構造過程烧给。WPL=3X3+1X3+5X2+5X1 =27

由此可見燕偶，對于同一組給定葉子結(jié)點所構造的哈夫曼樹，樹的形狀可能不同础嫡，但帶權路徑長度值是相同的指么，一定是最小的。

image.png

4.2 哈夫曼樹的構造算法
在構造哈夫曼樹時榴鼎，可以設置一個結(jié)構數(shù)組HuffNode保存哈夫曼樹中各結(jié)點的信息伯诬，根據(jù)二叉樹的性質(zhì)可知，具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點檬贰，所以數(shù)組HuffNode的大小設置為2n-1姑廉，數(shù)組元素的結(jié)構形式如下：

weight缺亮、lchild翁涤、rchild、parent萌踱。

其中葵礼，weight域保存結(jié)點的權值，lchild和rchild域分別保存該結(jié)點的左右孩子結(jié)點在數(shù)組HuffNode中序號并鸵，從而建立起結(jié)點之間的關系鸳粉。為了判定一個結(jié)點算法已加入到要建立的哈夫曼樹中，可通過parent域的值來確定园担。初始時parent的值為-1届谈，當結(jié)點加入到樹中時，該結(jié)點parent的值為其雙親結(jié)點在數(shù)組HuffNode中的序號弯汰，就不會是-1了艰山。

構造哈夫曼樹時，首先將由n個字符形成的n個葉子結(jié)點存放到數(shù)組HuffNode的前n個分量中咏闪，然后根據(jù)前面介紹的哈夫曼方法的基本思想曙搬，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新子樹的根結(jié)點順序放到HuffNode數(shù)組中前n個分量的后面鸽嫂。算法如下：

#define MAXVALUE 1000;//定義最大權值
#define MAXLEAF 30; // 定義哈夫曼樹中葉子結(jié)點的最大個數(shù)
#define MAXNODE MAXLEAF*2-1 ;//定義哈夫曼樹中結(jié)點的最大數(shù)
typedef struct{
    int weight;
    int parent;
    int lchild;
    int rchild;
 }HNode,HuffmanTree[MAXNODE];
 
void CrtHuffmanTree(HuffmanTree ht,int w[],int n){//數(shù)組w[] 傳遞n個權值
    int i,j,m1,m2,x1,x2;
    for(i=0;i<2*n-1;i++){//ht初始化
        ht[i].weight =0;
        ht[i].parent =.1;
        ht[i].lchild =.1;
        ht[i].rchild =.1;
    }
    for(i=0;i<n;i++){
        ht[i].weight =w[i];//賦予n個葉子結(jié)點的權值
    }
    for(i=0;i<n-1;i++){
        m1 =m2=MAXVALUE;//構造哈夫曼樹
        x1 =x2 =0;
        for(j=0;j=n+1;j++){
            //尋找權值最小和次小的兩棵子樹
            if(ht[j].weight<m1 && ht[j].parent ==.1){
                m2 = m1;
                x2=x1;
                x1=j;   
            }else if(ht[j].weight<m2 &&ht[j].parent ==.1){
                m2=ht[j].weight;
                x2 = j;
            }
        }
        //將找出的兩棵子樹合并為一棵子樹
        ht[x1].parent = n+i;
        ht[x2].parent = n+i; 
        ht[n+i].lchild =x1;
        ht[n+i].rchild =x2;
    }
}

4.3 哈夫曼編碼

在數(shù)據(jù)通信中纵装，經(jīng)常需要將傳遞的文字轉(zhuǎn)換成由二進制字符0、1組成二進制串据某，即進行符號的二進制編碼橡娄。常見的如ASCII碼就是8位的二進制編碼，此外癣籽，還有漢字國際碼挽唉、電報明碼等扳还。

ASCII碼是一種定長編碼，即每個字符用相同數(shù)目的二進制位表示橱夭。為了縮短數(shù)據(jù)文件報文長度氨距，可采用不定長編碼。例如棘劣，假設要傳遞的報文為ABACCDA俏让，報文中只含A、B茬暇、C首昔、D四種字符。如下圖所示：

image.png

a編碼糙俗，報文的代碼為0000 1000 0100 1001 11000勒奇，長度為21；

b編碼巧骚，報文的代碼為0001 0010 101100赊颠，長度為14；這兩種編碼均是定長編碼劈彪，碼長分別為3和2竣蹦。

c編碼，報文的代碼為0110 0101 01110沧奴，長度為13痘括；

d編碼，報文的代碼為0101 0010 0100 11001,長度為17滔吠；

顯然纲菌，不同的編碼方案，其最終形成的報文代碼總長度是不同的疮绷。如何使最終的報文最短翰舌，可以借鑒哈夫曼思想，在編碼時考慮字符出現(xiàn)的頻率矗愧，讓出現(xiàn)頻率高的字符采用盡可能短的編碼灶芝，出現(xiàn)頻率低的字符采用稍長的編碼，構造的不定長編碼唉韭，則報文的代碼就可能達到更短夜涕。

因此，利用哈夫曼樹來構造編碼方案属愤，就是哈夫曼樹的典型應用女器。具體做法如下：設需要編碼的字符集合為{d1，d2住诸，···驾胆，dn}涣澡，它們在報文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2,···丧诺，wn}入桂，以d1，d2驳阎，···dn為葉子結(jié)點抗愁，w1，w2,···呵晚，wn為它們的權值蜘腌，構造一棵哈夫曼樹，規(guī)定對哈夫曼樹中的左分支賦予0饵隙，右分支賦予1撮珠，則從根結(jié)點到每個葉子結(jié)點所經(jīng)過的路徑分支組成的0和1序列便為該葉子結(jié)點對應字符的編碼，稱為哈夫曼編碼金矛，這樣的哈夫曼樹也稱為哈夫曼編碼樹芯急。

在哈夫曼編碼樹中，樹的帶全路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和绷柒，也就是報文的代碼總長志于，所以采用哈夫曼樹構造的編碼是一種能使報文代碼總長最短的不定長編碼涮因。

在建立不定長編碼時废睦，必須使任何一個字符的編碼都不是另一個字符編碼的前綴，這樣才能保證譯碼的唯一性养泡。例如d編碼方案嗜湃，字符A的編碼01是字符B的編碼010的前綴部分，這樣對于代碼串0101001澜掩，既是AAC的代碼购披，又是ABA和BDA的代碼，因此肩榕，這樣的編碼不能保證譯碼的唯一性刚陡，稱為具有二義性的譯碼。同時把滿足“任意一個符號的編碼都不是其他的編碼的前綴”這一條件的編碼稱為前綴編碼株汉。

采用哈夫曼樹進行編碼筐乳，則不會產(chǎn)生上述二義性問題。因為乔妈，在哈夫曼樹中蝙云，每個字符結(jié)點都是葉子結(jié)點，它們不可能在根結(jié)點到其他字符結(jié)點的路徑上路召，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴勃刨，從而保證了譯碼的非二義性波材。

設ABCD出現(xiàn)的頻率分別為0.4，0.3身隐，0.2廷区，0.1，則得到的哈夫曼樹和二進制前綴編碼如下圖所示：

image.png

按此編碼贾铝，前面的報文可轉(zhuǎn)換成總長為14bit的二進制位串“01001101101110”躲因，可以看出，這一種不定長的前綴編碼能將報文唯一地無二義性地翻譯成原文忌傻。當原文較長大脉、頻率很不均勻時，這種編碼可使傳送的報文縮短很多水孩。當然镰矿，也可以在哈夫曼樹中規(guī)定左分支表示“1”，右分支表示“0”俘种，得到的二進制前綴編碼雖然不一樣秤标，但使用效果一樣。

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

編碼表存儲結(jié)構：

typedef struct codenode{
    char ch;     //存放要表示符號
    char *code; //存放相應代碼
}CodeNode;
 
typedef CodeNode HuffmanCode[MAXLEAF];

哈夫曼編碼的算法思路：在哈夫曼樹中宙刘，從每個葉子結(jié)點開始苍姜，一直往上搜索，判斷該結(jié)點是其雙親結(jié)點的做孩子還是右孩子悬包。若是左孩子衙猪，則相應位置上的代碼為0，反之為1布近。直到搜索到根據(jù)點為止垫释，具體算法如下：

void CrtHuffmanCode(HuffmanTree ht ,HuffmanCode hc,int n){
    //從葉子結(jié)點到根，逆向搜索求每個葉子結(jié)點對應符號的哈夫曼編碼
    char *cd;
    int i,c,p,start;
    cd = malloc (n*sizeof(char));//為當前工作區(qū)分配空間
    cd[n-1] ="\0";//從右到左逐位存放編碼撑瞧，首先存放結(jié)束符
    
    for(i =1; i<=n ;i++){//求n個葉子結(jié)點對應的哈夫曼編碼
        start = n-1;
        c =1;
        p =ht[i].parent;
        while(p!=0){
            --start;
            if(ht[p].lchild ==c){
                cd[start] ="0";//左分支標0
            }else{
                cd[start] ="1";//右1
            }
            c = p;
            p =ht[p].parent;//向上倒退
        }
        hc[i] = malloc((n-start) * sizeof(char));//為第i個編碼分配空間
        scanf("%c",&(hc[i]).ch)  ;  //輸入相應待編碼字符
        strcpy(hc[i],&ch[start]);  //將工作區(qū)中編碼復制到編碼表中
   }
    free(cd);
}

本章小結(jié)

本章主要介紹了樹與森林棵譬、二叉樹的定義、性質(zhì)预伺、操作和相關算法的實現(xiàn)订咸。特別是二叉樹的遍歷算法，它們是許多二叉樹應用的算法設計基礎酬诀，必須熟練掌握脏嚷。對于樹的遍歷算法，由于樹的先根遍歷次序與對應二叉樹表示的前序遍歷次序一致料滥；樹的后根遍歷次序與對應二叉樹的中序遍歷次序一致然眼，因此可以根據(jù)此得出樹的遍歷算法。

本章最后討論的哈夫曼樹是一種擴充的二叉樹葵腹，即在終端結(jié)點上帶有相應的權值高每，并使其帶權路徑長度最短屿岂。作為哈夫曼樹的應用，引入了哈夫曼編碼鲸匿。通常讓哈夫曼的左分支代表編碼“0”爷怀，右分支代表編碼“1”，得到哈夫曼編碼带欢。這是一種不定長編碼运授，可以有效地實現(xiàn)數(shù)據(jù)壓縮。

原文鏈接：https://blog.csdn.net/csdn_aiyang/java/article/details/84977814