數(shù)據(jù)結構課件：樹和二叉樹-２

3二叉樹的遍歷

3.1二叉樹的遍歷方法

3.2遍歷的遞歸算法3二叉樹的遍歷遍歷：按某種搜索路徑訪問二叉樹的每個結點，而且每個結點僅被訪問一次訪問：含義很廣，可以是對結點的各種處理，如修改結點數(shù)據(jù)、輸出結點數(shù)據(jù)

二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？3二叉樹的遍歷遍歷是各種數(shù)據(jù)結構最基本的操作，許多其他的操作可以在遍歷基礎上實現(xiàn)。對于線性結構由于每個結點只有一個直接后繼，遍歷是很容易的事

二叉樹是非線性結構，每個結點可能有兩個后繼，如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？令：L：遍歷左子樹

D：訪問根結點

R：遍歷右子樹有六種遍歷方法：

DLR，LDR，LRD，

DRL，RDL，RLD約定先左后右,有三種遍歷方法：DLR、LDR、LRD分別稱為先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B二叉樹的遍歷可以分解為：訪問根，遍歷左子樹和遍歷右子樹二叉樹由根、左子樹、右子樹三部分組成二叉樹的遍歷方法先序遍歷序列

A

F

G

E

D

C

B例：先序遍歷右圖所示的二叉樹1）訪問根結點A2）先序遍歷左子樹：即按DLR的順序遍歷左子樹3）先序遍歷右子樹：即按DLR的順序遍歷右子樹A,B,D,E,G,C,F若二叉樹非空

（1）訪問根結點（2）先序遍歷左子樹

（3）先序遍歷右子樹先序遍歷（DLR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結點（3）中序遍歷右子樹中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍歷右圖所示的二叉樹1）中序遍歷左子樹：即按LDR的順序遍歷左子樹2）訪問根結點A3）中序遍歷右子樹：即按LDR的順序遍歷右子樹中序遍歷（LDR）后序遍歷序列：D,G,E,B,F,C,A例：后序遍歷右圖所示的二叉樹1）后序遍歷左子樹：即按LRD的順序遍歷左子樹2）后序遍歷右子樹：即按LRD的順序遍歷右子樹3）訪問根結點A

A

F

G

E

D

C

B若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結點后序遍歷（LRD）后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍歷、中序遍歷、后序遍歷下圖的二叉樹--/+*abcdef這實際上是先序遍歷的遞歸定義，我們知道遞歸定義包括兩個部分：1）基本項（也叫終止項）；2）遞歸項若二叉樹非空（1）訪問根結點；（2）先序遍歷左子樹（3）先序遍歷右子樹；先序遍歷遞歸定義遞歸項該定義隱含著若二叉樹為空，結束三種遍歷方法，顯然是用遞歸的方式給出的，如先序遍歷（DLR）的定義：3.2遍歷的遞歸算法先序遍歷的定義等價于下面給出先序、中序、后序遍歷遞歸算法，為了增加算法的可讀性，這里對書上算法作了簡化，沒有考慮訪問結點出錯的情況（即我們假設調用函數(shù)visit()訪問結點總是成功的。若二叉樹為空，結束——基本項（也叫終止項）若二叉樹非空——遞歸項（1）訪問根結點；（2）先序遍歷左子樹（3）先序遍歷右子樹；先序遍歷遞歸算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹,visit()是訪問結點的函數(shù)。本算法先序遍歷以為根結點指針的二叉樹，對每個數(shù)據(jù)元素調用函數(shù)Visit()

if(T){//若二叉樹不為空，訪問根結點；遍歷左子樹,遍歷右子樹

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse最簡單的Visit函數(shù)是：

StatusPrintElement(TElemTypee){//輸出元素e的值

printf(e);returnOK;}2中序遍歷遞歸算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的//數(shù)。本算法中序遍歷以為根結點指針的二叉樹，//對每個數(shù)據(jù)元素調用函數(shù)Visit()

if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，遍歷左子樹，訪問根結點，//遍歷右子樹

InOrderTraverse(T->lchild,Visit);Visit(T->data)；

InOrderTraverse(T->rchild,Visit);

}//InOrderTraverse

3后序遍歷遞歸算法

voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉鏈表存貯二叉樹，visit()是訪問結點的//函數(shù)。本算法中序遍歷以為根結點指針的二叉//樹，對每個數(shù)據(jù)元素調用函數(shù)Visit()

if(T){//若二叉樹為空，結束返回

//若二叉樹不為空，遍歷左子樹，遍歷右子樹，//訪問根結點

PostOrderTraverse(T->lchild,Visit);

PostOrderTraverse(T->rchild,Visit);Visit(T->data)；

}//PostOrderTraverse

例: 已知一棵二叉樹的中根序列和先根序列分別為ABCDEFGHIJK和EBADCFHGIKJ，試畫出二叉樹4.中序遍歷二叉樹(非遞歸算法)用棧實現(xiàn)baabcdeadaaab入棧b退棧訪問d入棧d退棧訪問e退棧訪問ecc?？?/p>

a退棧訪問ce入棧c

退棧訪問

voidInOrder(BinTreeT){

stackS;InitStack(&S);//遞歸工作棧

BinTreeNode*p=T;

//初始化

while(p!=NULL||!StackEmpty(&S)){ if(p!=NULL){Push(&S,p);p=p->leftChild;}else{Pop(&S,p);//退棧

printf(p->data);//訪問

p=p->rightChild;}//if}//whilereturnok;}abcde4線索二叉樹(ThreadedBinaryTree)遍歷是二叉樹最基本最常用的操作

1）對二叉樹所有結點做某種處理可在遍歷過程中實現(xiàn);2）查找二叉樹某個結點，可通過遍歷實現(xiàn)與線性表相比，對二叉樹的遍歷存在如下問題

1）遍歷算法要復雜的多，費時的多

2）為檢索或查找二叉樹中某結點在某種遍歷下的后繼，必須從根開始遍歷，直到找到該結點及后繼

如果能將二叉樹線性化，就可以簡化遍歷算法，提高遍歷速度4線索二叉樹(ThreadedBinaryTree)如何將二叉樹線性化？以中序遍歷為例通過遍歷可以得到二叉樹結點的中序序列若能將中序序列中每個結點前趨、后繼信息保存起來，以后再遍歷二叉樹時就可以根據(jù)所保存的結點前趨、后繼信息對二叉樹進行遍歷加上結點前趨后繼信息（線索）的二叉樹稱為線索二叉樹中序遍歷序列：D,B,H,E,A,F,C,G在中序序列中，D的后繼是B，H的前趨是B，后繼是E…加上結點前趨后繼信息（線索）的二叉樹

AG

H

E

D

C

B

F線索二叉樹孩子指針前趨指針后繼指針如何將二叉樹線性化？2．線索鏈表

線索二叉樹的存貯方法：

1）

為每個結點增加二個標志域。

缺點：要點用較多的內存空間。

有n個結點的二叉鏈表，有n+1個空指針域,故可利用這些的空指針域存放結點的前趨和后繼指針，以這種結點的構成二叉鏈表稱為線索鏈表T∧

D

A

B

C

∧F

∧∧

H∧

E

∧∧

G

∧對線索鏈表中結點的約定

在二叉鏈表的結點中增加兩個標志域若該結點的左子樹不空則Lchild域的指針指向其左子樹，且左標志域的值為“指針Link”

否則，即左子樹為空Lchild域的指針指向其“前驅”，且左標志的值為“線索Thread”對線索鏈表中結點的約定

在二叉鏈表的結點中增加兩個標志域

若該結點的右子樹不空則rchild域的指針指向其右子樹，且右標志域的值為“指針Link”；

否則即該結點的右子樹為空則rchild域的指針指向其“后繼”，且右標志的值為“線索Thread”Ltag=0,lchild為左孩子指針Ltag=1,lchild為前驅線索Rtag=0,rchild為右孩子指針Rtag=1,rchild為后繼指針結點結構lchildrchilddataLtagRtag線索二叉樹結點線索鏈表的類型說明typedef

enum{link,thread}PointerTag;

//link=0,thread=1typedef

struct

BiThrNode{

TElemTypedata;

Struct

BiThrNode

*lchild,*rchild;//左右指針域

PointerTag

Ltag,Rtag;}BiThrNode，*BiThrTree；//左右標志域標志域為0時表示左右指針域存儲的是左右孩子的指針標志域為1時表示左右指針域存儲的是前趨后繼結點的指針F11E01G10D01A00B00H11C00線索鏈表圖示線索二叉樹

AG

H

E

D

C

B

F孩子指針前趨指針后繼指針中序遍歷序列：D,B,H,E,A,F,C,G為簡化線索鏈表的遍歷算法，仿照線性鏈表，為線索鏈表加上一個頭結點.約定頭結點的lchild域：存放線索鏈表的根結點指針頭結點的rchild域:中序序列最后一個結點指針中序序列第一結點lchild域指向頭結點中序序列最后一個結點的rchild域指向頭結點F11E01G11D11A00B00H11C0001頭結點如圖標出的中序二叉樹結點的順序，可看出1）中序序列的第一結點，是二叉樹的最左下結點2）若p所指結點的右孩子域為線索，則p的右孩子結點即為后繼結點3）若p所指結點的右孩子域為孩子指針，則p的后繼結點為其右子樹的最左下結點中序遍歷序列：D,B,H,E,A,F,C,GF11E01G11D11A00B00H11C0001頭結點3．線索二叉樹的遍歷

基本步驟：1）p=T->lchild;p指向線索鏈表的根結點；2）若線索鏈表非空，循環(huán)：（a）循環(huán)，順著p左孩子指針找到最左下結點；訪問之

（b）若p所指結點的右孩子域為線索，p的右孩子結點即為后繼結點循環(huán)：p=p->rchild；并訪問p所指結點；（在此循環(huán)中，順著后繼線索訪問二叉樹中的結點）（c）一旦線索“中斷”，p所指結點的右孩子域為右孩子指針，p=p->rchild，使p指向右孩子結點；3）返回OK；結束線索鏈表的遍歷算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){

//T指向頭結點，頭結點的左鏈lchild指向根結點，

//中序遍歷二叉線索樹T算法，對每個數(shù)據(jù)元素調用函數(shù)VisitP=T->lchild;//p指向根結點

While(p!=T){//空樹或遍歷結束時，p==T

While(p->Ltag==Link)p=p->lchild;

//找到最左下結點；訪問之

Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){

//若p所指結點的右孩子域為線索且不是最后一個結點

p=p->rchild;Visit(p->data);//訪問后繼結點

}p=p->rchild;}returnOK;}//InOrderTraverse_Thr樹的存儲結構在樹中，每個結點既可能有孩子也可能有雙親既可以通過保存每個結點的孩子結點位置來表示結點之間的結構關系也可以通過保存每個結點的雙親結點位置來表示結點之間的結構關系5.樹與森林5.1雙親表示通過保存每個結點的雙親結點的位置，表示樹中結點之間的結構關系。以一組連續(xù)空間存儲樹的結點，同時在結點中附設一個指針，存放雙親結點在鏈表中的位置ABCDEFGdataparentABCDEFG-10001130123456*便于涉及雙親的操作；*求結點的孩子時需要遍歷整棵樹特點用雙親表示實現(xiàn)的樹定義#defineMaxSize

//最大結點個數(shù)typedefcharTreeData;//結點數(shù)據(jù)typedefstruct{//樹結點定義

TreeDatadata;intparent;//雙親位置域}TreeNode;typedefTreeNodeTree[MaxSize];//樹5.2孩子表示法方法一

順序存儲

#defineMAX_TREE_SIZE100

typedef

struct

PTNode{

TElemTypedata;

intchild1;//第1個孩子位置域

intchild2;//第2個孩子位置域

......

int

childd;//第d個孩子位置域

}PTNode;

typedef

struct{

PTNodenodes[MAX_TREE_SIZE];

intn;//結點數(shù)

}PTree;孩子表示法：通過保存每個結點的孩子結點的位置，表示樹中結點之間的結構關系孩子表示法舉例RADEFCBGKH0123456789數(shù)組下標:*便于涉及孩子的操作；求雙親不方便；*采用同構的結點，空間浪費。R1A4B0C6D0E0F7G0H0K023500000000089000000鏈式存儲：每個結點用線性鏈表存貯它的孩子結點樹的孩子鏈表類型定義typedef

struct

CTNode{//孩子結點

intchild;

struct

CTNode*next;}*ChildPtr;typedef

struct{

TElemTypedata;

ChildPtr

firstchild;//孩子鏈表頭指針}CTBox;typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

Intn,r;//結點數(shù)和根的位置；}CTree;孩子鏈表存儲表示舉例RADEFCBGKH0123456789數(shù)組下標:*便于涉及孩子的操作；*求結點的雙親時不方便。RAB/CD/E/FG/H/K/123/45/6/789/T.nodes[];T.n=10;T.r=0;結點結構

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

typedef

struct

CSNode{

ELemTypedata;

struct

CSNode

*firstchild,*nextsibling;

}CSNode,*CSTree;類型定義孩子兄弟表示法用二叉鏈表作為存貯結構RADEFCBGKHRADECHFGBK孩子兄弟表示法示例二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導出樹與二叉樹之間的轉換樹與二叉樹轉換方法樹根結點X的第一個孩子結點X緊鄰的右兄弟二叉樹根結點X的左孩子結點X的右孩子特點：一棵樹轉換成二叉樹后，根結點沒有右孩子樹與二叉樹的轉換IACBDHGFE此二叉鏈表既是樹(a)的孩子兄弟表示又是二叉樹(b)的二叉鏈表由此可將樹與二叉樹對應起來AIHDGFCEBFIABDHGCE森林：樹的集合

將森林中樹的根看成兄弟，可用樹孩子兄弟表示法存儲森林用樹與二叉樹的轉換方法，進行森林與二叉樹轉換可用樹的遍歷方法對森林進行遍歷

J

O

P

N

M

L

KIACBDHGFE包含兩棵樹的森林森林如果F={T1,T2,…,Tm}是森林,則可按如下規(guī)則轉換成一棵二叉樹B=(root,LB,RB)。

(1)若F為空，即m=0,則B為空樹；

(2)若F非空，則B的根root即為森林中第一棵樹的根ROOT(T1)；

B的左子樹LB是從T1中根結點的子樹森林F1={T11,T12,…,T1m1}轉換而成的二叉樹;

其右子對RB是從森林F'={T2,T3,…,Tm}轉換而成的二叉樹.森林T1T2T3AFHBCDGIJEK3

棵樹的森林T1T2T3AFBCDEGHIKJ各棵樹的二叉樹表示ABCEDHIKJFG森林的二叉樹表示森林與二叉樹的轉換二叉樹轉換成森林如果B=(root,LB,RB)是一棵二叉樹,則可按如下規(guī)則轉換成森林F={T1,T2,…,Tm}：1)若B為空，則F為空；2)若B非空，則F中第一棵樹T1的根ROOT(T1)即為二叉樹B的根root；

T1中的根結點的子樹森林F1是由B的左子樹LB轉換而成的森林;

F中除T1之外其余樹組成的森林F'={T2,T3,…，Tm}是由B的右子樹RB轉換而成的森林。當樹非空時訪問根結點依次先根遍歷根的各棵子樹樹先根遍歷

ABEFCDG對應二叉樹前序遍歷ABEFCDGABCEDGF樹的先根次序遍歷樹的遍歷ACBDGFE樹的先根遍歷結果與其對應二叉樹表示的前序遍歷結果相同樹的先根遍歷可以借助對應二叉樹的前序遍歷算法實現(xiàn)ABCEDGF樹的先根次序遍歷樹的遍歷ACBDGFE樹的后根次序遍歷當樹非空時依次后根遍歷根的各棵子樹訪問根結點樹后根遍歷

EFBCGDA對應二叉樹中序遍歷EFBCGDAACBDGFEABCEDGF樹的后根次序遍歷樹的后根遍歷結果與其對應二叉樹表示的中序遍歷結果相同樹的后根遍歷可以借助對應二叉樹的中序遍歷算法實現(xiàn)ACBDGFEABCEDGF森林的兩種遍歷方法

一、先序遍歷森林若森林非空，則（1）訪問森林中第一棵樹的根結點；（2）先序遍歷第一棵樹的根結點的子樹森林；（3）先序遍歷除去第一棵樹之后的森林。二、中序遍歷森林若森林非空，則（1）中序遍歷第一棵樹的根結點的子樹森林；（2）訪問森林中第一棵樹的根結點；（3）中序遍歷除去第一棵樹之后的森林?；舴蚵鼧?HuffmanTree)在二叉樹中，一個結點到另一個結點之間的分支構成這兩個結點之間的路徑在路徑上的分支數(shù)目被稱為路徑長度樹的路徑長度是從樹根到每一結點的路徑長度之和霍夫曼樹(HuffmanTree)樹的帶權路徑長度是樹的各葉結點所帶的權值

wi

與該結點到根的路徑長度

li

的乘積的和用公式可表示為WPL=2*2+WPL=2*1+WPL=7*1+4*2+5*2+4*2+5*3+5*2+2*3+7*2=367*3=464*3=35222444555777帶權路徑長度達到最小霍夫曼樹假設有n個權值{ω1,ω2,…,ωn}，試構造一棵有n個葉子結點的二叉樹,每個葉子結點帶權為ωi,則其中：帶權路徑長度WPL最小的二叉樹稱做

最優(yōu)二叉樹或赫夫曼樹在霍夫曼樹中，權值大的結點離根最近構造赫夫曼樹的算法思想

1)根據(jù)給定的n個權值{w1,w2,…,wn}構成n棵二叉樹的集合F={T1,T2,…,Tn}其中每棵二叉樹Ti中只有一個帶權為Wi的根結點,其左右子樹均空

2)在F中選取兩棵根結點的權值最小的樹作為左右子樹構造一棵新的二叉樹,且置新的二叉樹的根結點的權值為其左.右子樹根結點的權值之和構造赫夫曼樹的算法思想3)在F中刪除這兩棵樹,同時將新得到的二叉樹加入F中.4)重復(2)和(3),直到F只含一棵樹為止.這棵樹便是赫夫曼樹F:{7}{5}{2}{4}7524初始F:{7}{5}{6}合并{2}{4}75246F:{7}{11}1175246合并{5}{6}F:{18}合并{7}{11}527461118霍夫曼樹的構造過程最佳判定樹考試成績分布表

判定樹不及格及格中良優(yōu)<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.15最佳判定樹不及格及格中良優(yōu)<60?<70?<80?<90?0.100.150.250.350.15≥≥≥≥<<<<WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=0.3+0.45+0.5+0.7+0.3=2.25霍夫曼編碼主要用途是實現(xiàn)數(shù)據(jù)壓縮

設給出一段報文：

CASTCASTSATATATASA

字符集合是{C,A,S,T}，各個字符出現(xiàn)的頻度(次數(shù))是W＝{2,7,4,5}。

若給每個字符以等長編碼

A:00T:10C:01S:11則總編碼長度為(2+7+4+5)*2=36

若按各個字符出現(xiàn)的概率不同而給予不等長編碼，可望減少總編碼長度7254010011ACTS各字符出現(xiàn)概率為{2/18,7/18,4/18,5/18},化整為{2,7,4,5}。以它們?yōu)楦魅~結點上的權值,建立霍夫曼樹。左分支賦0，右分支賦1，得霍夫曼編碼(變長編碼)。0001112457A:0T:10C:110S:111它的總編碼長度7*1+5*2+(2+4)*3=35。比等長編碼的情形要短總編碼長度正好等于霍夫曼樹的帶權路徑長度WPL。

霍夫曼編碼是一種無前綴編碼。解碼時不會混淆?；舴蚵幋a樹0001112457前綴編碼:指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼的前綴。算法typedef

struct{ unsignedintweight; unsignedint

parent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidHuffmanCoding(HuffmanTree

&HT,HuffmanCode

&HC,int*w,intn){HuffmanTreep; char*cd; inti,s1,s2,start;unsignedintc,f;if(n<=1)return;//n為字符樹木，m為結點樹木

intm=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));//0號單元未用

for(p=HT,i=1;i<=n;++i,++p,++w){p->weight=*w;p->parent=0;p->lchild=0;p->rchi