數(shù)據(jù)結(jié)構(gòu)課件 第6章 樹和二叉樹

10086510DataStructure第六章樹和二叉樹6/29/20231學(xué)習(xí)目標(biāo)領(lǐng)會(huì)樹和二叉樹的類型定義，理解樹和二叉樹的結(jié)構(gòu)差別。熟記二叉樹的主要特性，并掌握它們的證明方法。熟練掌握二叉樹的各種遍歷算法，并能靈活運(yùn)用遍歷算法實(shí)現(xiàn)二叉樹的其它操作。理解二叉樹的線索化過程以及在中序線索化樹上找給定結(jié)點(diǎn)的前驅(qū)和后繼的方法。熟練掌握二叉樹和樹的各種存儲結(jié)構(gòu)及其建立的算法。學(xué)會(huì)編寫實(shí)現(xiàn)樹的各種操作的算法。了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和赫夫曼編碼的方法。6/29/20232重點(diǎn)和難點(diǎn)重點(diǎn)：二叉樹和樹的遍歷及其應(yīng)用。難點(diǎn)：編寫實(shí)現(xiàn)二叉樹和樹的各種操作的遞歸算法。知識點(diǎn)樹的類型定義、二叉樹的類型定義二叉樹的存儲表示二叉樹的遍歷以及其它操作的實(shí)現(xiàn)線索二叉樹樹和森林的存儲表示樹和森林的遍歷以及其它操作的實(shí)現(xiàn)最優(yōu)樹和赫夫曼編碼6/29/20233樹型結(jié)構(gòu)是一類非常重要的非線性數(shù)據(jù)結(jié)構(gòu)。6/29/202346.1樹的定義和基本術(shù)語——樹(tree)的定義是n(n0)個(gè)結(jié)點(diǎn)的有限集T；在任意一棵非空樹中，有且僅有一個(gè)特定的結(jié)點(diǎn)，稱為樹的根(root)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1,T2,……Tm，其中每一個(gè)集合本身又是一棵樹，稱為根的子樹(subtree)。特點(diǎn)：非空樹中至少有一個(gè)結(jié)點(diǎn)——根；樹中各子樹是互不相交的集合。樹的定義是采用遞歸方法6/29/20235AABCDEFGHIJKLM只有根結(jié)點(diǎn)的樹有子樹的樹根子樹6/29/20236(a)一棵樹結(jié)構(gòu)(b)一個(gè)非樹結(jié)構(gòu)(c)一個(gè)非樹結(jié)構(gòu)樹中各子樹互不相交的含義ACBGFEDHIACBGFDACBGFDE兩點(diǎn)①某結(jié)點(diǎn)不能同時(shí)屬于兩個(gè)子集，如圖(b)所示；②兩個(gè)子集的結(jié)點(diǎn)之間不能有關(guān)系，如圖(c)所示.6/29/20237結(jié)點(diǎn)的度：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)。樹的度：樹中各結(jié)點(diǎn)度的最大值。CGBDEFKLHMIJA6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/20238葉子結(jié)點(diǎn)：度為0的結(jié)點(diǎn)，也稱為終端結(jié)點(diǎn)。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)，也稱為非終端結(jié)點(diǎn)。CGBDEFKLHMIJA6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/20239孩子、雙親：樹中某結(jié)點(diǎn)子樹的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的孩子結(jié)點(diǎn)，這個(gè)結(jié)點(diǎn)稱為它孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)；兄弟：具有同一個(gè)雙親的孩子結(jié)點(diǎn)互稱為兄弟。

CGBDEFKLHMIJA6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202310路徑：如果樹的結(jié)點(diǎn)序列n1,n2,…,nk有如下關(guān)系：結(jié)點(diǎn)ni是ni+1的雙親（1<=i<k），則把n1,n2,…,nk稱為一條由n1至nk的路徑；路徑上經(jīng)過的邊的個(gè)數(shù)稱為路徑長度。CGBDEFKLHMIJA6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202311祖先、子孫：在樹中，如果有一條路徑從結(jié)點(diǎn)x到結(jié)點(diǎn)y，那么x就稱為y的祖先，而y稱為x的子孫。CGBDEFKLHMIJA6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202312結(jié)點(diǎn)所在層數(shù)：根結(jié)點(diǎn)的層數(shù)為1；對其余任何結(jié)點(diǎn)，若某結(jié)點(diǎn)在第k層，則其孩子結(jié)點(diǎn)在第k+1層。樹的深度：樹中所有結(jié)點(diǎn)的最大層數(shù)，也稱高度。1層2層4層3層高度＝4CGBDEFKLHMIJC6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202313CBDEFKLHJA71234568910層序編號：將樹中結(jié)點(diǎn)按照從上層到下層、同層從左到右的次序依次給他們編以從1開始的連續(xù)自然數(shù)。6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202314有序樹、無序樹：如果一棵樹中結(jié)點(diǎn)的各子樹從左到右是有次序的，稱這棵樹為有序樹；反之，稱為無序樹。數(shù)據(jù)結(jié)構(gòu)中討論的一般都是有序樹

ACBGFEDACBGFED6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202315CBDEFKLHJ森林：m(m≥0)棵互不相交的樹的集合。

A6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202316同構(gòu)：對兩棵樹，若通過對結(jié)點(diǎn)適當(dāng)?shù)刂孛?，就可以使這兩棵樹完全相等（結(jié)點(diǎn)對應(yīng)相等，結(jié)點(diǎn)對應(yīng)關(guān)系也相等），則稱這兩棵樹同構(gòu)。ACBGFEDDAECFBG6.1樹的定義和基本術(shù)語——樹的基本術(shù)語6/29/202317ABCDEFGHIJKLM結(jié)點(diǎn)A的度：3結(jié)點(diǎn)B的度：2結(jié)點(diǎn)M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點(diǎn)A的孩子：B，C，D結(jié)點(diǎn)B的孩子：E，F(xiàn)結(jié)點(diǎn)I的雙親：D結(jié)點(diǎn)L的雙親：E結(jié)點(diǎn)B，C，D為兄弟結(jié)點(diǎn)K，L為兄弟樹的度：3結(jié)點(diǎn)A的層次：1結(jié)點(diǎn)M的層次：4樹的深度：4結(jié)點(diǎn)A是結(jié)點(diǎn)F，G的祖先結(jié)點(diǎn)F，G為堂兄弟6/29/202318樹的抽象數(shù)據(jù)類型的定義ADTTree{數(shù)據(jù)對象：D是具有相同特性的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系： 若D為空集，則稱為空樹； 若D中僅含一個(gè)數(shù)據(jù)元素，則關(guān)系R為空集； 若D中含多于一個(gè)數(shù)據(jù)元素，則R={H}，H是如下二元關(guān)系：

(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān)系H下無前驅(qū)；

(2)當(dāng)n>1時(shí)，其余數(shù)據(jù)元素可分為m(m>0)個(gè)互不相交的(非空)有限

集T1,T2,…,Tm,其中每一個(gè)子集本身又是一棵符合本定義的樹，

稱為根root的子樹，每一棵子樹的根xi都是根root的后繼，即

<root,xi>H，i=1,2,…,m。6/29/202319基本操作：

InitTree(&T);

操作結(jié)果：構(gòu)造空樹T。

CreateTree(&T,definition);

初始條件：definition給出樹T的定義。

操作結(jié)果：按definition構(gòu)造樹T。

DestroyTree(&T);

初始條件：樹T存在。

操作結(jié)果：銷毀樹T。

TreeEmpty(T);

初始條件：樹T存在。

操作結(jié)果：若T為空樹，則返回TRUE，否則返回FALSE。6/29/202320

TreeDepth(T);

初始條件：樹T存在。

操作結(jié)果：返回T的深度。

Root(T);

初始條件：樹T存在。

操作結(jié)果：返回T的根。

Value(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：返回cur_e的值。6/29/202321

Parent(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非根結(jié)點(diǎn)，則返回它的雙親，

否則返回“空”。

LeftChild(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e是T的非葉子結(jié)點(diǎn)，則返回它的最左

孩子，否則返回“空”。

RightSibling(T,cur_e);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：若cur_e有右兄弟，則返回它的右兄弟，否則

返回“空”。

6/29/202322

TraverseTree(T,visit());

初始條件：樹T存在，visit是對結(jié)點(diǎn)操作的應(yīng)用函數(shù)。

操作結(jié)果：按某種次序?qū)的每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)visit()

一次且至多一次。一旦visit()失敗，則操作

失敗。

Assign(T,cur_e,value);

初始條件：樹T存在，cur_e是T中某個(gè)結(jié)點(diǎn)。

操作結(jié)果：結(jié)點(diǎn)cur_e賦值為value。

ClearTree(&T);

初始條件：樹T存在。

操作結(jié)果：將樹T清為空樹。6/29/202323

InsertChild(&T,&p,i,c);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p所

指結(jié)點(diǎn)的度＋1，非空樹c與T不相交。

操作結(jié)果：插入c為T中p所指結(jié)點(diǎn)的第i棵子樹。

DeleteChild(&T,&p,i);

初始條件：樹T存在，p指向T中某個(gè)結(jié)點(diǎn)，1≤i≤p

指結(jié)點(diǎn)的度。

操作結(jié)果：刪除T中p所指結(jié)點(diǎn)的第i棵子樹。}ADTTree6/29/202324樹的表示方法樹形表示法：自然界倒長的樹；文氏表示法：用集合表示；凹入表示法：類似書目；嵌套括號表示法：廣義表表示法。樹形文氏ABDCG凹入ABCDG嵌套括號(A(B,C(G),D))6/29/202325樹和線性結(jié)構(gòu)對照線性結(jié)構(gòu)樹結(jié)構(gòu)存在唯一的沒有前驅(qū)

的"首元素"存在唯一的沒有前驅(qū)的

"根結(jié)點(diǎn)"存在唯一的沒有后繼

的"尾元素"存在多個(gè)沒有后繼的

"葉子"其余元素均存在唯一

的"前驅(qū)元素"和唯一

的"后繼元素"其余結(jié)點(diǎn)均存在唯一的

"前驅(qū)(雙親)結(jié)點(diǎn)"和多

個(gè)"后繼(孩子)結(jié)點(diǎn)"6/29/2023266·2二叉樹二叉樹的定義是n(n>=0)個(gè)結(jié)點(diǎn)的有限集，其子樹分為互不相交的兩個(gè)集合，分別稱為左子樹和右子樹，左子樹和右子樹也是二叉樹。ABCDEIJGH根結(jié)點(diǎn)左子樹右子樹6/29/202327二叉樹不是樹的特例。特點(diǎn)每個(gè)結(jié)點(diǎn)至多有二棵子樹(即不存在度大于2的結(jié)點(diǎn))；二叉樹的子樹有左、右之分，且其次序不能任意顛倒?；拘螒B(tài)AABABABC空二叉樹只有根結(jié)點(diǎn)的二叉樹右子樹為空左子樹為空左、右子樹均非空6/29/202328斜樹1.所有結(jié)點(diǎn)都只有左子樹的二叉樹稱為左斜樹；2.所有結(jié)點(diǎn)都只有右子樹的二叉樹稱為右斜樹；3.左斜樹和右斜樹統(tǒng)稱為斜樹。1.在斜樹中，每一層只有一個(gè)結(jié)點(diǎn)；2.斜樹的結(jié)點(diǎn)個(gè)數(shù)與其深度相同。

幾種特殊形式的二叉樹斜樹的特點(diǎn)：ABCABC6/29/202329幾種特殊形式的二叉樹滿二叉樹深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹。特點(diǎn)每一層上的結(jié)點(diǎn)數(shù)都是最大結(jié)點(diǎn)數(shù)；所有的分支結(jié)點(diǎn)的度數(shù)都為2；葉子結(jié)點(diǎn)都在同一層次上。1231145891213671014156/29/202330幾種特殊形式的二叉樹完全二叉樹若對滿二叉樹的結(jié)點(diǎn)從上到下從左至右進(jìn)行編號，則深度為k且有n個(gè)結(jié)點(diǎn)的二叉樹稱為完全二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹的編號從1到n一一對應(yīng)時(shí)。特點(diǎn)葉子結(jié)點(diǎn)只可能在層次最大的兩層上出現(xiàn)；前k-1層中的結(jié)點(diǎn)都是“滿”的，且第k層的結(jié)點(diǎn)都集中在左邊。1231145891267106/29/202331判斷是否為完全二叉樹，說明理由。1234567123456思考：滿二叉樹與完全二叉樹的關(guān)系？6/29/202332在滿二叉樹中，從最后一個(gè)結(jié)點(diǎn)開始，連續(xù)去掉任意個(gè)結(jié)點(diǎn)，即是一棵完全二叉樹。A1523467910BCDEFGHIJK11L12M13N14O158CDEFGHIJ不是完全二叉樹，結(jié)點(diǎn)10與滿二叉樹中的結(jié)點(diǎn)10不是同一個(gè)結(jié)點(diǎn)6/29/202333二叉樹的性質(zhì)性質(zhì)1：在二叉樹的第i層至多有2i-1個(gè)結(jié)點(diǎn)(i1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。性質(zhì)3：對于任何一棵二叉樹T，若其終端結(jié)點(diǎn)(葉子)數(shù)為

n0，度為1的結(jié)點(diǎn)數(shù)為n1，度為2的結(jié)點(diǎn)數(shù)n2，

則n0=n2+1。6/29/202334性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度是log2n+1。性質(zhì)5：如果對一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹的結(jié)點(diǎn)按層序

編號，則對任一結(jié)點(diǎn)i(1in)，有：如果i=1，則結(jié)點(diǎn)i是二叉樹的根，無雙親；如果i>1，則其雙親是i/2；如果2i>n，則結(jié)點(diǎn)i無左孩子；如果2in，則其左孩子是2i；如果2i+1>n，則結(jié)點(diǎn)i無右孩子；如果2i+1n，則其右孩子是2i+1。6/29/202335二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)用一組地址連續(xù)的存儲單元存儲二叉樹中的數(shù)據(jù)元素。完全二叉樹，只要從根起按層序存儲即可。將完全二叉樹上編號為i的結(jié)點(diǎn)元素存儲在一維數(shù)組中下標(biāo)為i-1的分量中。一般的二叉樹，可對照完全二叉樹的編號進(jìn)行相應(yīng)的存儲，但在沒有結(jié)點(diǎn)的分量中需填充空白字符(例如填充0)。順序存儲表示

#defineMAX_TREE_SIZE100 //最大結(jié)點(diǎn)數(shù)

Typedef

TElemType

SqBiTree[MAX_TREE_SIZE]; //0號根結(jié)點(diǎn)

SqBiTree

bt;6/29/202336深度為4，有12個(gè)結(jié)點(diǎn)的完全二叉樹的順序存儲123451011678912111210987654321

123456789101112沒有浪費(fèi)6/29/202337深度為4，有7個(gè)結(jié)點(diǎn)的一般二叉樹的順序存儲abcdefggf0000edcba

1234567891011浪費(fèi)4個(gè)6/29/202338深度為4，只有4個(gè)右孩子的二叉樹的順序存儲0000400030002011234123456789101112131415浪費(fèi)11個(gè)6/29/202339順序存儲結(jié)構(gòu)適用于滿二叉樹和完全二叉樹的存儲。6/29/202340鏈?zhǔn)酱鎯Y(jié)構(gòu)二叉鏈表結(jié)點(diǎn)除包括元素自身的信息外，還包括指向其左、右子樹的指針。即結(jié)點(diǎn)要包括數(shù)據(jù)域，左子樹指針域和右子樹指針域。二叉鏈表的存儲表示

typedef

struct

BiTNode{

TElemType

data;

struct

BiTNode

*lchild,*rchild;

}BiTNode,*Bitree;

lchilddatarchild6/29/202341ABCDEFGAB

CD

E

F

G^^^^^^^^在n個(gè)結(jié)點(diǎn)的二叉鏈表中，有n+1個(gè)空指針域。6/29/202342二叉鏈存儲結(jié)構(gòu)的二叉樹操作實(shí)現(xiàn)

二叉樹的初始化算法的基本思想：創(chuàng)建二叉樹的頭結(jié)點(diǎn)。voidInitiate(BiTreeNode**root){ *root=(BiTreeNode*)malloc(sizeof(BiTreeNode)); (*root)->leftChild=NULL; (*root)->rightChild=NULL;}6/29/202343二叉鏈存儲結(jié)構(gòu)的二叉樹操作實(shí)現(xiàn)

二叉樹中給某結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn)的操作

算法的基本思想：……BiTreeNode*InsertLeftNode(BiTreeNode*curr,DataTypex){BiTreeNode*s,*t;

if(curr==NULL)returnNULL; t=curr->leftChild; s=(BiTreeNode*)malloc(sizeof(BiTreeNode));s->data=x; s->leftChild=t; s->rightChild=NULL;

curr->leftChild=s; returncurr->leftChild; }6/29/202344二叉鏈存儲結(jié)構(gòu)的二叉樹操作實(shí)現(xiàn)

刪除二叉樹中某結(jié)點(diǎn)的左子樹操作

算法的基本思想：……BiTreeNode*DeleteLeftTree(BiTreeNode*curr){

if(curr==NULL||curr->leftChild==NULL)returnNULL;

Destroy(&curr->leftChild);

curr->leftChild=NULL; returncurr;}6/29/202345三叉鏈表結(jié)點(diǎn)包括數(shù)據(jù)域，左子樹指針域、雙親域和右子樹指針域。lchilddataparentrchild三叉鏈表的存儲表示

typedef

struct

TriTNode{

TElemType

data;

struct

TriTNode

*lchild,*rchild,*parent;

}TriTNode,*Tritree;6/29/202346ABC

DEF

G^^^^^^^^^ABCDEFG6/29/2023476.3遍歷二叉樹遍歷是樹結(jié)構(gòu)的一種常用的、重要的運(yùn)算，是樹的其它運(yùn)算的基礎(chǔ)。6/29/202348遍歷按一定的規(guī)律，走遍二叉樹的每個(gè)結(jié)點(diǎn)，使每個(gè)結(jié)點(diǎn)被訪問一次，且只被訪問一次。遍歷方式按根、左子樹、右子樹三個(gè)部分進(jìn)行訪問；按層次訪問；

遍歷的過程就是把非線性結(jié)構(gòu)的二叉樹中的結(jié)點(diǎn)排成一個(gè)線性序列的過程。6/29/202349按根、左子樹、右子樹三個(gè)部分進(jìn)行訪問設(shè)D表示根結(jié)點(diǎn)，L表示左子樹，R表示右子樹，則對這三個(gè)部分進(jìn)行訪問的組合共有6種，DLRDRLLDRLRDRDLRLD若限定先左后右，則只有DLR，LDR，LRD三種，分別稱為先序遍歷，中序遍歷，后序遍歷。6/29/202350先序遍歷若二叉樹為空，則空操作；否則訪問根結(jié)點(diǎn)：先序遍歷左子樹；先序遍歷右子樹。6/29/202351ADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC6/29/202352算法6.1先序遍歷的遞歸算法StatusPreOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，visit是對元素操作的應(yīng)用函數(shù)，

//先序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡單的visit函數(shù)是輸出元素的值。

if(T){

visit(T->data)；

PreOrderTraverse(T->lchild,visit)；

PreOrderTraverse(T->rchild,visit);}//if}//PreOrderTraverse6/29/202353ABCDGEFH先序遍歷：ABDGCEFH6/29/202354中序遍歷若二叉樹為空，則空操作；否則中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。6/29/202355ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC6/29/202356中序遍歷的遞歸算法StatusInOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，visit是對元素操作的應(yīng)用函數(shù)，

//中序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡單的visit函數(shù)是輸出元素的值。

if(T){

InOrderTraverse(T->lchild,visit)；

visit(T->data)；

InOrderTraverse(T->rchild,visit)；

}//if}//InOrderTraverse6/29/202357DGBAECH中序遍歷：ABCDGEFHF6/29/202358后序遍歷若二叉樹為空，則空操作；否則后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。6/29/202359ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCAB6/29/202360ABCDGEFH后序遍歷：CGFDHBEA6/29/202361后序遍歷的遞歸算法StatusPostOrderTraverse(BiTreeT，Status(*visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，visit是對元素操作的應(yīng)用函數(shù)，

//先序遍歷二叉樹T的遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

//最簡單的visit函數(shù)是輸出元素的值。

if(T){

PostOrderTraverse(T->lchild,visit);

PostOrderTraverse(T->rchild,visit); visit(T->data);}//if}//InOrderTraverse6/29/202362三種遍歷算法的比較相同點(diǎn)：如果把訪問根結(jié)點(diǎn)這個(gè)不涉及遞歸的語句拋開，則三個(gè)遞歸算法走過的路線是一樣的。6/29/202363三種遍歷算法的比較不同點(diǎn)：前序遍歷是每進(jìn)入一層遞

歸調(diào)用時(shí)先訪問根結(jié)點(diǎn)，

然后再依次向它的左、右

子樹執(zhí)行遞歸調(diào)用；中序遍歷是在執(zhí)行完左子

樹遞歸調(diào)用后再訪問根結(jié)

點(diǎn)，然后向它的右子樹遞

歸調(diào)用；后序遍歷則是在從右子樹

遞歸調(diào)用退出后訪問根結(jié)

點(diǎn)。6/29/202364實(shí)例1：統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù)算法思想：對二叉樹“遍歷”一遍，并在遍歷過程中對“葉子結(jié)點(diǎn)計(jì)數(shù)”

即可。為了在遍歷的同時(shí)進(jìn)行計(jì)數(shù)，在算法的參數(shù)中設(shè)

一個(gè)“計(jì)數(shù)器”。這個(gè)遍歷的次序可以隨意，即先序或中

序或后序均可。voidCountLeaf(BiTreeT,int&count){

//先序遍歷二叉樹，以count返回二叉樹中葉子結(jié)點(diǎn)的數(shù)目

if(T){if((!T->Lchild)&&(!T->Rchild))

count++;

CountLeaf(T->Lchild,count);

CountLeaf(T->Rchild,count);}//if}//CountLeaf6/29/202365實(shí)例2：求二叉樹的深度算法思想：深度為樹中葉子結(jié)點(diǎn)所在層次的最大值。

結(jié)點(diǎn)的層次需從根結(jié)點(diǎn)起遞推，根結(jié)點(diǎn)為第一層。

需要在先序遍歷二叉樹的過程中求每個(gè)結(jié)點(diǎn)的層次數(shù)，并

將其中的最大值設(shè)為二叉樹的深度。算法一：voidBiTreeDepth(BiTreeT,intlevel,int&depth){

//T指向二叉樹的根，level為T所指結(jié)點(diǎn)所在層次，

//其初值為1，depth為當(dāng)前求得的最大層次,其初值為0if(T){if(level>depth)depth=level;

BiTreeDepth(T->Lchild,level+1,depth);

BiTreeDepth(T->Rchild,level+1,depth);}//if}//BiTreeDepth6/29/2023666/29/202367算法二：int

depth(BitreeT){ if(T==NULL)return0; else{ h1=depth(T->lchild); h2=depth(T->rchild); returnmax(h1,h2)+1; }}6/29/202368實(shí)例3：在二叉樹上查詢某個(gè)結(jié)點(diǎn)問題描述假設(shè)給定一個(gè)和二叉樹中數(shù)據(jù)元素有相同類型的值，在已知二叉樹中進(jìn)行查找，若存在和給定值相同的數(shù)據(jù)元素，則返回函數(shù)值為TRUE，并用引用參數(shù)返回指向該結(jié)點(diǎn)的指針；否則返回函數(shù)值為FALSE。算法的基本思想為：若二叉樹為空樹，則二叉樹上不存在這個(gè)結(jié)點(diǎn)，返回FALSE；否則，和根結(jié)點(diǎn)的元素進(jìn)行比較，若相等，則找到，即刻返回指向該結(jié)點(diǎn)的指針和函數(shù)值TRUE，從而查找過程結(jié)束；否則，在左子樹中進(jìn)行查找，若找到，則返回TRUE；否則，返回在右子樹中進(jìn)行查找的結(jié)果。因?yàn)橛易訕渖喜檎业慕Y(jié)果即為整個(gè)查找過程的結(jié)果，即若找到，返回的函數(shù)值為TRUE，并且已經(jīng)得到指向該結(jié)點(diǎn)的指針，否則返回的函數(shù)值為FALSE。6/29/202369boolLocate(BiTreeT,ElemTypex,BiTree&p){

//存在和x相同的元素，則p指向該結(jié)點(diǎn)并返回TRUE，否則p=NULL且返回FALSE

if(!T){

p=NULL;returnFALSE;}

//空樹中不存在這樣的結(jié)點(diǎn)

else{if(T->data==x){

p=T;returnTRUE;}

//找到所求結(jié)點(diǎn)elseif(Preorder(T->Lchild,x,p))

returnTRUE;

//在左子樹中找到所求結(jié)點(diǎn)

elsereturn(Preorder(T->Rchild,x,p)); //返回在右子樹

//中查找的結(jié)果

}//else}6/29/202370實(shí)例4：建立二叉樹的存儲結(jié)構(gòu)--二叉鏈表voidCreateBiTree(BiTree&T){//按先序序列輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格表示空樹，//構(gòu)造二叉鏈表表示的二叉樹T。

scanf(&ch)；

if(ch==‘’)T=NULL;

//建空樹

else{

if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))eixt(OVERFLOW);

T->data=ch; //生成根結(jié)點(diǎn)

CreateBiTree(T->Lchild); //遞歸建(遍歷)左子樹

CreateBiTree(T->Rchild); //遞歸建(遍歷)右子樹

}//else returnOK;}//CreateBiTree6/29/202371AB#CD###E#F##6/29/202372實(shí)例5：交換二叉樹中所有結(jié)點(diǎn)的左、右子樹。voidexchg_tree(bitreptrBT){

//采用后序遍歷的方法，交換每一個(gè)結(jié)點(diǎn)的左右子樹。

if(BT!=null){//非空

exchg_tree(BT->lchild);//交換左子樹所有結(jié)點(diǎn)指針

exchg_tree(BT->rchild);//交換右子樹所有結(jié)點(diǎn)指針

p=BT->lchild;//交換根結(jié)點(diǎn)左右指針

BT->lchild=BT->rchild;BT->rchild=p; }}6/29/202373實(shí)例6：輸出后序序列的逆序。voidpreorder(treeT){

//輸出后序序列的逆序

if(T!=NULL){

printf(“%f”,T->data);

preorder(T->rchild);

preorder(T->lchild);

}}6/29/202374遞歸算法轉(zhuǎn)化為非遞歸算法遞歸算法優(yōu)點(diǎn)形式簡潔，可讀性好，正確性容易得到證明，可以給程序的編制和調(diào)試帶來很大的方便。遞歸算法缺點(diǎn)遞歸調(diào)用比非遞歸調(diào)用消耗的時(shí)間與存儲空間多，運(yùn)行的效率較低。所有的遞歸算法都可轉(zhuǎn)化成相應(yīng)的非遞歸算法。將遞歸算法改成相應(yīng)的非遞歸算法需要一個(gè)棧來記

錄調(diào)用返回的路徑。通過分析遞歸調(diào)用的執(zhí)行過程，

并觀察棧的變化就可得到相應(yīng)的非遞歸算法。6/29/202375statusInOrderTraverse(BiTreeT,status(*visit)(TElemTypee)){

//采用二叉鏈表存儲結(jié)構(gòu)，visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)

//中序遍歷二叉樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)visit。

InitStack(S);Push(S,T); //根指針進(jìn)棧

while(!StackEmpty(S){

while(GetTop(S,p)&&p)Push(S,p->lchild); //向左走到盡頭

Pop(S,p); //空指針退棧

if(!StackEmpty(S)){ //訪問結(jié)點(diǎn)，向右一步

Pop(S,p);if(!Visit(p->data))returnERROR;

Push(S,p->rchild);

}

} returnOK;}中序遍歷二叉樹T的非遞歸算法6/29/202376piP->AABCDEFG6/29/202377piP->AP->BABCDEFG6/29/202378piP->AP->BP->CABCDEFG6/29/202379p=NULLiP->AP->BABCDEFG訪問：C6/29/202380piP->A訪問：CBABCDEFG6/29/202381piP->AP->D訪問：CBABCDEFG6/29/202382piP->AP->DP->E訪問：CBABCDEFG6/29/202383訪問：CBEpABCDEFGiP->AP->D6/29/202384訪問：CBEP=NULLABCDEFGiP->AP->DP->G6/29/202385訪問：CBEGpABCDEFGiP->AP->D6/29/202386訪問：CBEGDpABCDEFGiP->A6/29/202387pABCDEFGiP->AP->F訪問：CBEGD6/29/202388ABCDEFGiP->Ap=NULL訪問：CBEGDF6/29/202389pABCDEFGi訪問：CBEGDFA6/29/202390ABCDEFGip=NULL訪問：CBEGDFA6/29/202391表達(dá)式a+b*(c-d)-e/f用二叉樹表示-+/a*b-efcd先序遍歷：-+a*b-cd/ef波蘭式6/29/202392表達(dá)式a+b*(c-d)-e/f用二叉樹表示-+/a*b-efcd中序遍歷：-+a*b-cd/ef中綴表示6/29/202393表達(dá)式a+b*(c-d)-e/f用二叉樹表示-+/a*b-efcd后序遍歷：-+a*b-cd/ef逆波蘭式6/29/202394已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AEBCDFHIGJ6/29/202395已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AFHIGJBECD6/29/202396已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AFHIGJBECD6/29/202397已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AFHIGJBDEC6/29/202398已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AFHIGJBECD6/29/202399已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AHIGJBECDF6/29/2023100已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。AHIBECDFGJ6/29/2023101已知一棵二叉樹的先序遍歷序列為ABECDFGHIJ，中序遍歷序列為EBCDAFHIGJ，試畫出這顆二叉樹。ABECDFGHJI試編寫算法實(shí)現(xiàn)上述過程。

思考：先序、中序、后序序列中任意給定兩個(gè)

序列就可以畫出該二叉樹嗎？為什么？6/29/2023102按層次遍歷ABECDFGHJI按層次遍歷序列：ABFECGDHJI6/29/20231036.4線索二叉樹遍歷二叉樹的實(shí)質(zhì)二叉樹遍歷的過程，為沿著某一條搜索路徑對二叉樹中的結(jié)點(diǎn)進(jìn)行一次且僅僅一次訪問。也就是按一定規(guī)則將一個(gè)處于層次結(jié)構(gòu)中的結(jié)點(diǎn)排列成一個(gè)線性序列之后進(jìn)行依次訪問，這個(gè)線性序列或是先序序列、或是中序序列或是后序序列。在這些線性序列中每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)外）有且僅有一個(gè)直接前驅(qū)和直接后繼。顯然，這種信息是在遍歷的動(dòng)態(tài)過程中產(chǎn)生的，如果將這些信息在第一次遍歷時(shí)就保存起來，則在以后再次需要對二叉樹進(jìn)行"遍歷"時(shí)就可以將二叉樹視作線性結(jié)構(gòu)進(jìn)行訪問操作了。如何保存在遍歷過程中得到的前驅(qū)和后繼信息？6/29/2023104最簡單的辦法在結(jié)點(diǎn)中增加兩個(gè)指針域分別指向該結(jié)點(diǎn)的前驅(qū)和后繼。缺點(diǎn)：存儲結(jié)構(gòu)的存儲密度大大降低，浪費(fèi)。另一種方法（尋求存儲結(jié)構(gòu)中的空指針域）靈感：思想：一個(gè)含n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)鏈域的值為

“NULL”。問題：利用這些空的指針域存放指向前驅(qū)和后繼的信息。引起混淆。lchilddatarchild是左孩子還是前驅(qū)指針？是右孩子還是后繼指針？6/29/2023105AB

CD

E

F

G^^^^^^^^6/29/2023106

解決辦法：在結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域。lchildLtagdataRtagrchild

0 lchild域指示結(jié)點(diǎn)的左孩子Ltag=

1 lchild域指示結(jié)點(diǎn)的前趨

0 rchild域指示結(jié)點(diǎn)的右孩子Rtag=

1 rchild域指示結(jié)點(diǎn)的后繼6/29/2023107線索鏈表：以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉鏈表。線索：指向結(jié)點(diǎn)前趨和后繼的指針。線索二叉樹：加上線索二叉樹。線索化：對二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹

的過程。若某程序中所用二叉樹需經(jīng)常遍歷或查找結(jié)點(diǎn)在遍歷所得線性序列中的前驅(qū)或后繼，應(yīng)采用線索鏈表作存儲結(jié)構(gòu)。6/29/2023108先序線索鏈表和先序線索二叉樹ABCDEABDCE先序序列：ABCDE先序線索鏈表0000111111thrt

0

1先序線索二叉樹NIL指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)的右線索指向頭結(jié)點(diǎn)6/29/2023109中序線索鏈表和中序線索二叉樹DABCE中序序列：BCAED中序線索鏈表0000111111ABCDEthrt

0

1中序線索二叉樹NILNIL指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)的右線索指向頭結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的左線索指向頭結(jié)點(diǎn)6/29/2023110后序線索鏈表和后序線索二叉樹ABCDEABDCE后序序列：CBEDA后序線索鏈表0000111111thrt

0

1后序線索二叉樹指向根結(jié)點(diǎn)指向序列的最后一個(gè)結(jié)點(diǎn)第一個(gè)結(jié)點(diǎn)的左線索指向頭結(jié)點(diǎn)NIL6/29/2023111對二叉樹進(jìn)行中序線索化的算法StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){

//中序遍歷二叉樹T，并將其中序線索化，Thrt指向頭結(jié)點(diǎn)。

if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode))))exit(OVERFLOW);

Thrt->Ltag=0;Thrt->Rtag=1; //建頭結(jié)點(diǎn)

Thrt->rchild=Thrt; //右指針回指

if(!T)Thrt->lchild=Thrt; //若二叉樹為空，則左指針回指

else{

Thrt->lchild=T;pre=Thrt;

InThreading(T); //中序遍歷進(jìn)行中序線索化

pre->rchild=Thrt;pre->Rtag=1; //最后一個(gè)結(jié)點(diǎn)線索化

Thrt->rchild=pre;//頭結(jié)點(diǎn)的右指針指向遍歷的最后一個(gè)結(jié)點(diǎn)

}returnOK;}//InOrderThreading空指針改為指向前驅(qū)或后繼的線索1

2

34

5678910116/29/2023112voidInThreading(BiThrtTreep){if(p){

InThreading(p->lchild); //左子樹線索化

if(!p->lchild)

{p->Ltag=1;p->lchild=pre;} //前驅(qū)線索

if(!pre->rchild)

{pre->Rtag=1;p->rchild=p;} //后繼線索

pre=p;

InThreading(p->rchild);}}先序、后序線索化的算法？與中序的區(qū)別？123

45

67896/29/2023113在線索二叉樹上進(jìn)行遍歷（以中序線索二叉樹為例）遍歷的關(guān)鍵問題找到訪問的第一個(gè)結(jié)點(diǎn)；根據(jù)中序遍歷的特點(diǎn)，第一個(gè)結(jié)點(diǎn)必定是“其左子樹為空”的結(jié)點(diǎn)。若根結(jié)點(diǎn)沒有左子樹，根結(jié)點(diǎn)即為中序遍歷訪問的第一個(gè)結(jié)點(diǎn)；若根結(jié)點(diǎn)有左子樹，第一個(gè)結(jié)點(diǎn)是其左子樹中“最左下的結(jié)點(diǎn)”。即從根結(jié)點(diǎn)出發(fā)，順指針lchild

找到其左子樹直至某個(gè)結(jié)點(diǎn)的指針lchild

為"線索"止，該結(jié)點(diǎn)為中序序列中的第一個(gè)結(jié)點(diǎn)。找到每個(gè)結(jié)點(diǎn)在序列中的后繼。若結(jié)點(diǎn)沒有右子樹，即結(jié)點(diǎn)的右指針類型標(biāo)志Rtag

為“Thread”，則指針

rchild

所指即為它的后繼。若結(jié)點(diǎn)有右子樹，則它的后繼應(yīng)該是其右子樹中訪問的第一個(gè)結(jié)點(diǎn)。應(yīng)該從它的右子樹根出發(fā)，順指針lchild

直至沒有左子樹的結(jié)點(diǎn)為止，該結(jié)點(diǎn)即為它的后繼。6/29/2023114FJICAHEGBD6/29/2023115FJICAHEGBD另一種遍歷方法：找最后一個(gè)結(jié)點(diǎn)；然后找每個(gè)結(jié)點(diǎn)的前驅(qū)。先序、后序線索二叉樹上如何遍歷？6/29/2023116對線索二叉樹進(jìn)行中序遍歷的算法StatusInOrderTraverse_Tri(BiThrTreeT,Status(*Visit)(TElemTypee)){

//T指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的lchid指向根結(jié)點(diǎn)，

//中序遍歷二叉線索樹T的非遞歸算法，對每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。

p=T->lchild; //p指向根結(jié)點(diǎn)

while(p!=T){ //空樹或遍歷結(jié)束時(shí)，p==T while(p->Ltag==0) p=p->lchild; if(!Visit(p->data)) returnERROR;//訪問左子樹為空的結(jié)點(diǎn)

while(p->Rtag==1&&p->rchild!=T){

p=p->rchild; Visit(p->data);//訪問后繼結(jié)點(diǎn)

} p=p->rchild; } returnOK;}123

45

6

7896/29/2023117學(xué)習(xí)線索化時(shí)，有三點(diǎn)必須注意：何種“序”的線索化，是先序、中序還是后序；要“前驅(qū)”線索化、“后繼”線索化還是“全”線索化；只有空指針處才能加線索；6/29/20231186.5樹和森林6.5.1樹的存儲結(jié)構(gòu)雙親表示法以一組連續(xù)的存儲空間存放樹的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)中附設(shè)一個(gè)指針指示其雙親結(jié)點(diǎn)在這連續(xù)的存儲空間中的位置。形式說明#defineMAX_TREE_SIZE=100;typedef

struct

PTNode{

//結(jié)點(diǎn)結(jié)構(gòu)

TElemTypedata;

intparent;

//雙親位置域

}PTNode;typedef

struct{

//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE];

intr,n;

//根的位置和結(jié)點(diǎn)數(shù)

}PTree;6/29/2023119abcdefhgiacdefghib-1011244406012345789dataparent優(yōu)點(diǎn)：找雙親容易。缺點(diǎn)：找孩子難，

需要遍歷整個(gè)結(jié)構(gòu)。r=0n=96/29/2023120孩子表示法把每個(gè)結(jié)點(diǎn)的孩子排列起來，看成一個(gè)線性表，以單鏈表存儲；令其頭指針和結(jié)點(diǎn)的數(shù)據(jù)元素構(gòu)成一個(gè)結(jié)點(diǎn)，并將所有這樣的結(jié)點(diǎn)存放在一個(gè)地址連續(xù)的存儲空間里。形式說明typedef

struct

CTNode{

//孩子結(jié)點(diǎn)

intchild;

struct

CTNode*next;

}*ChildPtr;typedef

struct{

ElemTypedata;

//結(jié)點(diǎn)的數(shù)據(jù)元素

ChildPtr

firstchild;

//孩子鏈表頭指針

}CTBox;typedef

struct{

CTBoxnodes[MAX_TREE_SIZE];

intn,r;

//結(jié)點(diǎn)數(shù)和根的位置

}CTree;6/29/2023121abcdefhgi優(yōu)點(diǎn)：找孩子容易。缺點(diǎn)：找雙親難，

需要遍歷整個(gè)結(jié)構(gòu)。acdefghib6012345789datafc

1

2^

3

4^^8

6

7^5^^^^^n=9r=06/29/2023122abcdefhgi優(yōu)點(diǎn)：找孩子和雙親容易。缺點(diǎn)：存儲空間增加。acdefghib

1

2^

3

4^^8

6

7^5^^^^^n=9r=06012345789datafcpar-1011244406/29/2023123孩子兄弟表示法（二叉鏈表表示法）用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個(gè)結(jié)點(diǎn)的兩個(gè)指針域分別指向其第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。形式說明typedef

struct

CSNode{

ElemTypedata;

struct

CSNode*firstchild,*nextsibling;

}CSNode,*CSTree;6/29/2023124abcdef

g

h

i^^^^^^^^^^abcdefhgi6/29/2023125優(yōu)點(diǎn)：便于實(shí)現(xiàn)樹的各種操作。缺點(diǎn)：破壞了樹的層次。abcdefhgiabcdef

g

h

i^^^^^^^^^^6/29/20231266.5.2森林與二叉樹的轉(zhuǎn)換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應(yīng)存儲存儲解釋解釋6/29/2023127樹轉(zhuǎn)換為二叉樹的方法加線：在兄弟之間加一連線。抹線：對每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系。旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45°。ABCDEFGHI6/29/2023128ABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空6/29/2023129森林轉(zhuǎn)換成二叉樹的方法將各棵樹分別轉(zhuǎn)換成二叉樹。將每棵樹的根結(jié)點(diǎn)用線相連。以第一棵樹根結(jié)點(diǎn)為二叉樹的根，再以根結(jié)點(diǎn)為軸心，順時(shí)針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)。ABCDEFGHIJ6/29/2023130ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6/29/2023131二叉樹轉(zhuǎn)換成樹的方法加線：若p結(jié)點(diǎn)是雙親結(jié)點(diǎn)的左孩子，則將p的右孩子，右孩子的右孩

子，……沿分支找到的所有右孩子，都與p的雙親用線連起來。抹線：抹掉原二叉樹中雙親與右孩子之間的連線。調(diào)整：將結(jié)點(diǎn)按層次排列，形成樹結(jié)構(gòu)。ABCDEFGHI6/29/2023132ABCDEFGHIABCDEFGHIABCDEFGHI6/29/2023133二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點(diǎn)與其右孩子連線，及沿右分支搜索到的

所有右孩子間連線全部抹掉，使之變成孤立的二叉樹。還原：將孤立的二叉樹還原成樹。ABCDEFGHIJ6/29/2023134ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ6/29/20231356.5.3

樹和森林的遍歷樹的遍歷先根遍歷若樹不空，則先訪問根結(jié)點(diǎn)，然后依次從左到右先根遍歷根的各棵子樹。后根遍歷若樹不空，則先依次從左到右后根遍歷根的各棵子樹，然后訪問根結(jié)點(diǎn)。6/29/2023136ABCDEFGHIJKLMNO先根遍歷：后根遍歷：ABEFIGCDHJKLNOMEIFGBCJKNOLMHDA轉(zhuǎn)換二叉樹的先序遍歷轉(zhuǎn)換二叉樹的中序遍歷6/29/2023137森林的遍歷先序遍歷

訪問森林中第一棵樹的根結(jié)點(diǎn)；先序遍歷第一棵樹中的子樹森林；先序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。中序遍歷

中序遍歷第一棵樹中的子樹森林；訪問森林中第一棵樹的根結(jié)點(diǎn)；中序遍歷除去第一棵樹之后剩余的樹構(gòu)成的森林。6/29/2023138ABCDEFGHIJ先序遍歷：中序遍歷：ABCDEFGHIJBCDAFEHJIG轉(zhuǎn)換二叉樹的先序遍歷轉(zhuǎn)換二叉樹的中序遍歷6/29/20231396.6哈夫曼樹及其應(yīng)用6.6.1哈夫曼樹（最優(yōu)二叉樹---帶權(quán)路徑長度最短的樹）基本概念路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的分支。路徑長度：路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度：從樹根到每一結(jié)點(diǎn)的路徑長度之和。256714327134561710完全二叉樹是路徑長度最短的二叉樹6/29/2023140結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長度。dcab2475WPL=7*3+5*3+2*1+4*2=466/29/2023141結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長度。WPL=7*2+5*2+2*2+4*2=36abcd75246/29/2023142結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長度。WPL=7*1+5*2+2*3+4*3=35abcd75246/29/2023143結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)到樹根之間的路徑長度與結(jié)點(diǎn)上

的權(quán)值的乘積。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。通常

記作其中，Wk葉子結(jié)點(diǎn)的權(quán)值，lk葉子結(jié)點(diǎn)的路徑長度。加權(quán)后路徑長度最小的并非是完全二叉樹，而是權(quán)大的葉子離根最近的二叉樹。6/29/2023144哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點(diǎn)，帶權(quán)路徑長度最小的二叉樹。例：給定4個(gè)葉子結(jié)點(diǎn)，其權(quán)值分別為{2，3，4，7}，可以構(gòu)造出形狀不同的多個(gè)二叉樹。

WPL=32WPL=41WPL=302347234774236/29/2023145哈夫曼樹的特點(diǎn)：1.權(quán)值越大的葉子結(jié)點(diǎn)越靠近根結(jié)點(diǎn)，而權(quán)值越小的葉子結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。2.只有度為0（葉子結(jié)點(diǎn)）和度為2（分支結(jié)點(diǎn)）的結(jié)點(diǎn)，不存在度為1的結(jié)點(diǎn).

2347WPL=32WPL=41WPL=30234774236/29/2023146構(gòu)造哈夫曼樹的過程（哈夫曼算法）根據(jù)給定的n個(gè)權(quán)值{w1,w2,……wn}，構(gòu)造n棵只有根結(jié)點(diǎn)的二叉樹，令初始權(quán)值為wj；在森林中選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作左右子樹，構(gòu)造一棵新的二叉樹，置新二叉樹根結(jié)點(diǎn)權(quán)值為其左右子樹根結(jié)點(diǎn)權(quán)值之和；在森林中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入森林中；重復(fù)上述兩步，直到只含一棵樹為止，這棵樹即哈夫曼樹。

哈夫曼樹的形態(tài)不是唯一的，但對具有一組權(quán)值的各哈夫曼樹的WPL是唯一的。6/29/2023147w={5,29,7,8,14,23,3,11}，構(gòu)造哈夫曼樹85311192342291487152958100WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=271w={5,29,7,8,14,23,3,11}w={29,7,8,14,23,11,8}w={29,14,23,11,8,15}w={29,14,23,15,19}w={29,23,19,29}w={29,29,42}w={42,58}w={100}6/29/2023148哈夫曼樹應(yīng)用------判定樹等級分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.1070a<80YNCa<60EYNABYN80a<90DYN60a<70EADBC哈夫曼樹6/29/2023149哈夫曼樹應(yīng)用------判定樹等級分?jǐn)?shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<80YNa<60EDYNCa<70YNa<90YNBA70a<80YNCa<60EYNABYN80a<90DYN60a<706/29/20231506.6.2哈夫曼編碼背景目前，遠(yuǎn)距離通信的主要手段是電報(bào)，即將需傳送的文字轉(zhuǎn)換成由二進(jìn)制的字符組成的字符串。編碼時(shí)需要遵循以下原則解碼的結(jié)果唯一；發(fā)送的二進(jìn)制編碼盡可能短。兩類二進(jìn)制編碼等長編碼：各個(gè)字符的編碼長度相等。優(yōu)點(diǎn)：解碼簡單。缺點(diǎn)：編碼長度可能不最短。不等長編碼：各個(gè)字符的編碼長度不等。優(yōu)點(diǎn)：編碼長度盡可能地短。缺點(diǎn)：解碼困難。等長編碼什么情況下空間效率高？不等長編碼什么情況下空間效率高？6/29/2023151例如：傳送電文“ABACCDA”等長編碼A：00B：01C：10D：11編碼結(jié)果00010010101100，長度為14位。解碼方以兩位為一字段解碼。不等長編碼原則：出現(xiàn)次數(shù)較多的字符編碼短，次數(shù)較少的字符編碼長。A：0B：00C：1D：01編碼結(jié)果000011010，長度為9位。解碼方無法解碼，因?yàn)榻獯a的結(jié)果不唯一。6/29/2023152前綴編碼任意一個(gè)字符的編碼都不能是另一個(gè)字符的編碼的前綴，這種編碼稱為前綴編碼。哈夫曼編碼（同時(shí)滿足代碼長度短，且解碼唯一）目標(biāo)：使電文總長最短。以字符出現(xiàn)的次數(shù)為權(quán)，構(gòu)造一棵赫夫曼樹；將樹中結(jié)點(diǎn)引向其左孩子的分支標(biāo)“0”，引向其右孩子的分支標(biāo)“1”；每個(gè)字符的編碼即為從根到每個(gè)葉子的路徑上得到的0、1序列，這樣得到的編碼稱為哈夫碼編碼。哈夫曼編碼為前綴編碼。以這組編碼傳送電文可使電文總長最短(對所有其它前綴編碼而言)。6/29/2023153vuiywtre

字符集vwertyui頻率5297814233110000000111111100100000111011111110100001iuytrewv6/29/2023154哈夫曼解碼從哈夫曼樹根開始，從待譯碼電文中逐位取碼。若編碼是“0”，則向左走；若編碼是“1”，則向右走，一旦到達(dá)葉子結(jié)點(diǎn)，則譯出一個(gè)字符；再重新從根出發(fā)，直到電文結(jié)束。vuiywtre

00000001111111解碼：111111100