第六章樹和二叉樹第六章樹和二叉樹16.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結構6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的26.1樹的類型定義6.13數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關系R：數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。若D4

基本操作：查找類

插入類刪除類基本操作：查找類插入類刪除類5

Root(T)//求樹的根結點

查找類：Value(T,cur_e)//求當前結點的元素值

Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷Root(T)//求樹的根結點查找類：Val6InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構造樹Assign(T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結點p的第i棵子樹InitTree(&T)//初始化置空樹插入類：C7

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹ClearTree(&T)//將樹清空刪除類：De81、樹（Tree)：是n個結點的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個特定的稱為根的結點（root)；當n>1時，其余結點可分為m（m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。1、樹（Tree)：是n個結點的有限集（n>=0)。在任意一9(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：樹中結點的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關系。無序樹：樹中結點的各子樹之間的先后次序無意義，可以互換。子樹之間不存在確定的次序關系。(１)有確定的根；有向樹：有序樹：樹中結點的各子樹之間的先10ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),11樹的示意圖：根結點根結點葉結點分支結點子樹子樹子樹Level1Level2Level3Level4結點的層次樹的示意圖：根結點根結點葉結點分支結點子樹子樹子樹Level12對比樹型結構和線性結構的結構特點對比樹型結構和線性結構的結構特點13~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數(shù)據(jù)元素(無前驅(qū))

根結點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~14基本術語基本術語151、結點:2、結點的度:3、樹的度:4、葉子結點:5、分支結點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM（終端結點）（非終端結點）1、結點:2、結點的度:3、樹的度:4、葉子結點:5、分支結166、(從根到結點的)路徑：7、孩子結點、雙親結點兄弟結點、堂兄弟結點祖先結點、子孫結點8、結點的層次:9、樹的深度：

由從根到該結點所經(jīng)分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，依次加1樹中葉子結點所在的最大層次6、(從根到結點的)路徑：7、孩子結點、雙親結點8、結點的層17任何一棵非空樹是一個二元組Tree=（root，F(xiàn)）其中：root被稱為根結點F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組10、森林：是m（m≥0）棵互Ar186.2

二叉樹的類型定義二叉樹是樹的基礎，一般的樹可以轉(zhuǎn)化為二叉樹來處理。6.219

1、二叉樹的定義：

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結點左子樹右子樹1、二叉樹的定義：二叉樹或為空樹，或是由一個根結點加202、二叉樹的五種基本形態(tài)：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹2、二叉樹的五種基本形態(tài)：N空樹只含根結點NNNLRR右子樹21

二叉樹的主要基本操作：查找類插入類刪除類二叉樹的主要基本操作：查找類插入類刪除22

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());Root(T);Value(T,e);23

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);24ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);25二叉樹

的重要特性二叉樹

的重要特性26

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個結點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結點：

2i-1=20=1；假設對所有的j，1≤j

i，命題成立；由歸納假設知：第I-1層上至多有2i-2個結點。又因為二叉樹上每個結點至多有兩棵子樹，則第i層的結點數(shù)=2i-22=2i-1

。性質(zhì)1：在二叉樹的第i層上至多有27性質(zhì)2：

深度為k的二叉樹上至多有2k-1個結點（k≥1）。證明：[證明用求等比數(shù)列前k項和的公式]基于上一條性質(zhì)，深度為k的二叉樹上的結點數(shù)至多為

20+21+

+2k-1=2k-1。性質(zhì)2：

深度為k的二叉樹上至多有2k-128

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1。證明：設二叉樹上結點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子29兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-130

性質(zhì)4：

具有n個結點的完全二叉樹的深度為log2n+1。證明：設完全二叉樹的深度為k，則由性質(zhì)2和完全二叉樹的定義知：深度為k-1的二叉樹應該是一棵滿二叉樹，故結點數(shù)為2k-1-1；深度為k的完全二叉樹當為滿二叉樹時結點數(shù)最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因為k只能是整數(shù)，因此，k=log2n

+1。性質(zhì)4：具有n個結點的完全二叉樹的深度為31性質(zhì)5：若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)若2i+1>n，則該結點無右孩子結點，

否則，編號為2i+1的結點為其右孩子結點。性質(zhì)5：若對含n個結點的完全二叉樹從上到下且從左至右321、完全二叉樹第3層有2個葉子，則該二叉樹有多少個結點？分析：第3層最多有23-1=4個結點。完全二叉樹只有3層，則前2層為滿二叉樹，結點數(shù)為22-1=3個結點，故總結點數(shù)=3+2=5；完全二叉樹含有4層，則前3層為滿二叉樹，結點數(shù)為23-1=7個結點。又第3層上結點數(shù)為4，由題知其中兩個為葉子，則其它（4-2）=2個結點應為內(nèi)部結點。由完全二叉樹的定義知：這兩個結點中有一個結點的度可以為1或2，而其它結點的度必為2。綜上：總結點數(shù)=7+1+（2-1）*2=10或總結點數(shù)=7+2*2=11。練習：1、完全二叉樹第3層有2個葉子，則該二叉樹有多少個結點？練習33作業(yè)已知二叉樹有50個葉子結點，則該二叉樹的總結點數(shù)至少應有多少個？任意一個有n個結點的二叉樹，已知它有m個葉子結點，試證明非葉子結點中有（m-1）個結點的度為2，其余度為1。含n個結點的完全三叉樹的高度為多少？完全二叉樹第7層有10個葉子，問該二叉樹共有多少個結點？作業(yè)已知二叉樹有50個葉子結點，則該二叉樹的總結點數(shù)至少應346.3二叉樹的存儲結構二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示6.3二、二叉樹的鏈式存儲表示一、二叉樹的順序存儲表示35（適合存儲完全二叉樹）即用一組地址連續(xù)的存儲單元集資從上至下，從左至右存儲完全二叉樹上的結點元素。也就是說，將完全二叉樹上編號為i的結點存放在數(shù)組下標為（i-1)的分量中。若要存儲一棵一般的二叉樹，結點的存放應與完全二叉樹上的結點對照，存儲在數(shù)組的相應分量中。用“0”表示不存在該結點。可能會浪費很多存儲空間，單支樹就是一個極端情況。一、二叉樹的順序存儲表示（適合存儲完全二叉樹）一、二叉樹的順序存儲表示36完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示完全二叉樹的數(shù)組表示一般二叉樹的數(shù)組表示數(shù)組表示37#defineMAX_TREE_SIZE100//二叉樹的最大結點數(shù)typedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0號單元存儲根結點SqBiTreebt;C語言描述#defineMAX_TREE_SIZE10038ADEBCFrootlchilddatarchild結點結構1.二叉鏈表二、二叉樹的順序存儲表示ADEBCFrootlchilddata39typedefstruct

BiTNode

{//結點結構TElemTypedata;

structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;lchilddatarchild結點結構:C語言描述:typedefstructBiTNode{//結點40ADEBCFroot2．三叉鏈表parent

lchilddatarchild結點結構ADEBCFroot2．三叉鏈表parent41

typedefstruct

TriTNode

{//結點結構

structTriTNode

*parent;//雙親指針

structTriTNode*lchild,;//左孩子指針TElemTypedata;

structTriTNode*rchild;//右孩子指針

}TriTNode,*TriTree;parentlchilddatarchild結點結構:C語言的類型描述如下:typedefstructTriTNode{42二叉樹鏈表表示的示例二叉樹鏈表表示的示例436.4二叉樹的遍歷6.444一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、遍歷算法的應用舉例一、遍歷的概念二、先左后右的遍歷算法三、算法的遞歸描述四、遍45

按照某種順序不重復地訪問二叉樹中的所有結點。此處的訪問可以是輸出、修改等操作，根據(jù)實際需要而定。

使得每個結點均被訪問一次，而且僅被訪問一次。“訪問”的含義可以很廣，如：輸出結點的信息。一、遍歷的概念按照某種順序不重復地訪問二叉樹中的所有結點。此處的46

“遍歷”是任何類型均有的操作，對線性結構而言，只有一條搜索路徑(因為每個結點均只有一個后繼)，故不需要另加討論。而二叉樹是非線性結構，每個結點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑遍歷的問題。“遍歷”是任何類型均有的操作，47對“二叉樹”而言，可以有兩條搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；對“二叉樹”而言，可以有兩條搜索路徑：1．先上后48二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算49

若二叉樹為空樹，則空操作；否則，（1）訪問根結點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。遍歷結果-+a*b-cd/ef先（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，先（根）序的遍歷算法：50voidPreorder(BiTreeT){if(T){//如果樹不為空visit(T->data);//輸出根結點Preorder(T->lchild);//先序遍歷左子樹Preorder(T->rchild);//先序遍歷右子樹}}先序voidPreorder(BiTree51

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結點；（3）中序遍歷右子樹。遍歷結果

a+b*c-d-e/f中（根）序的遍歷算法：若二叉樹為空樹，則空操作；否則，中（根）序的遍歷算法：52voidInorder(BiTreeT){if(T){//如果樹不為空Inorder(T->lchild);//先序遍歷左子樹

visit(T->data);//輸出根結點Inorder(T->rchild);//先序遍歷右子樹}}中序voidInorder(BiTree53

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結點。后（根）序的遍歷算法：遍歷結果abcd-*+ef/-若二叉樹為空樹，則空操作；否則，后（根）序的遍歷算法：遍54voidPastorder(BiTreeT){if(T){//如果樹不為空

Pastorder(T->lchild);//先序遍歷左子樹

visit(T->data);//輸出根結點Pastorder(T->rchild);//先序遍歷右子樹}}后序voidPastorder(BiTree55二、遍歷算法的應用舉例1、統(tǒng)計二叉樹中葉子結點的個數(shù)(先序遍歷)2、求二叉樹的深度(后序遍歷)3、建立二叉樹的存儲結構4、求二叉樹的結點個數(shù)二、遍歷算法的應用舉例1、統(tǒng)計二叉樹中葉子結點的個數(shù)2、求二561、統(tǒng)計二叉樹中葉子結點的個數(shù)算法基本思想:分別求出左子樹、右子樹的葉子數(shù)，然后相加。1、統(tǒng)計二叉樹中葉子結點的個數(shù)算法基本思想:分別求出左子57void

CountLeaf

(BiTreeT){if(!T)return0;elseif((!T->lchild)&&(!T->rchild))return1;else{nl=CountLeaf(T->lchild);nr=CountLeaf(T->rchild);returnnl+nr;

}//if}//CountLeafvoidCountLeaf(BiTreeT)582、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深度的定義可知，二叉樹的深度應為其左、右子樹深度的最大值加1。由此，需先分別求得左、右子樹的深度，算法中“訪問結點”的操作為：求得左、右子樹深度的最大值，然后加1。

首先分析二叉樹的深度和它的左、右子樹深度之間的關系。2、求二叉樹的深度(后序遍歷)算法基本思想:從二叉樹深59int

Depth(BiTreeT){//返回二叉樹的深度

if(!T)return0;else{dl=Depth(T->lchild);dr=Depth(T->rchild);

dep=1+(dl>dr?dl:dr);

}

return

dep;}intDepth(BiTreeT){//返回二叉603建立二叉樹的存儲結構不同的定義方法相應有不同的存儲結構的建立算法3建立二叉樹的存儲結構不同的定義方法相應有不同的存儲結構的建61

以字符串的形式:根左子樹右子樹,定義一棵二叉樹例如:ABCD以空白字符“”表示A(B(,C(,)),D(,))空樹只含一個根結點的二叉樹A以字符串“A”表示以下列字符串表示以字符串的形式:根左子樹右子樹,定義一62status

CreateBiTree(BiTree&T)

{scanf(&ch);

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

else{

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

exit(OVERFLOW);T->data=ch;//生成根結點

CreateBiTree(T->lchild);//構造左子樹

CreateBiTree(T->rchild);//構造右子樹

}

returnOK;}//CreateBiTreestatusCreateBiTree(BiTree&T)63AB

C

D

ABCD上頁算法執(zhí)行過程舉例如下：ATBCD^^^^^ABCDABCD上頁644、求二叉樹的結點個數(shù)IntNodeCount(BiTreeT){if(!T)return0;else{nl=NodeCount(T->lchild);nr=NodeCount(T->rchild);returnnl+nr+1;}}4、求二叉樹的結點個數(shù)IntNodeCount(BiTre65

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，由二叉樹的先序和中序序列建樹

如果同時已知二叉樹的中序序列“cbdaegf”，則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根僅知二叉樹的先序序列“abcdefg”不能唯一確定66主要思想：先序序列中第一個為“根”，標出之；在中序序列中標出“根”，并分出左、右子樹；在先序序列中標出左、右子樹；分別對左、右子樹重復以上步驟。主要思想：67abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列abcdefgcbda68由二叉樹的后序和中序序列建樹二叉樹的后序序列二叉樹的中序序列左子樹右子樹根左子樹右子樹根主要思想：后序序列中第一個為“根”，標出之；在中序序列中標出“根”，并分出左、右子樹；在后序序列中標出左、右子樹；分別對左、右子樹重復以上步驟。由二叉樹的后序和中序序列建樹二叉樹的后序序列二叉樹的中序序列69由二叉樹的后序和先序序列能否建樹？二叉樹的后序序列二叉樹的先序序列左子樹右子樹根左子樹右子樹根結論：不能唯一確定二叉樹！ABAB或例：先序：AB后序：BA由二叉樹的后序和先序序列能否建樹？二叉樹的后序序列二叉樹的先70練習：先序：ABDEGCFH

中序：DBGEAFHC中序：DBGEAFHC

后序：DGEBHFCA畫出二叉樹，并寫出后序序列。畫出二叉樹，并寫出先序序列。練習：畫出二叉樹，并寫出后序序列。畫出二叉樹，并寫出先序序列71證明：在含有n個結點的二叉樹中，含有n+1個空指針。Proof:設二叉樹中度為0、1、2的結點數(shù)分別為n0,n1,n2，即n=n0+n1+n2由于二叉樹中的空指針數(shù)=2n0+n1+0=n0+n0+n1由性質(zhì)3知：n0=n2+1所以空指針數(shù)=n2+1+n0+n1=n+1

證畢。證明：在含有n個結點的二叉樹中，含有n+1個空指針。Proo726.5

線索二叉樹

何謂線索二叉樹？線索鏈表的遍歷算法如何建立線索鏈表？6.5

線索二叉樹何謂線索二叉樹？73一、何謂線索二叉樹？是要借助含有n個結點的二叉樹中(n+1)個空指針域，作為線索，直接指向遍歷序列中“前驅(qū)”或“后繼”結點。ABCDEFGHK例如:先序序列:

ABCDEFGHK中序序列:

BDCAHGKFE后序序列:

DCBHKGFEA一、何謂線索二叉樹？是要借助含有n個結點的二叉樹中(n+1)74指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索”與其相應的二叉樹，稱作“線索二叉樹”包含“線索”的存儲結構，稱作“線索鏈表”ABCDEFGHK^D^

C^^B

E^指向該線性序列中的“前驅(qū)”和“后繼”的指針，稱作“線索751、對線索鏈表中結點的約定：在二叉鏈表的結點中增加兩個標志域，并作如下規(guī)定：若該結點的左子樹不空，則Lchild域的指針指向其左子樹，且左標志域的值為“指針Link=0”；否則，Lchild域的指針指向其“前驅(qū)”，且左標志的值為“線索Thread=1”

。1、對線索鏈表中結點的約定：在二叉鏈表的結點中增加兩個76若該結點的右子樹不空，則rchild域的指針指向其右子樹，且右標志域的值為“指針Link=0”；否則，rchild域的指針指向其“后繼”，且右標志的值為“線索Thread=1”。

如此定義的二叉樹的存儲結構稱作“線索鏈表”。若該結點的右子樹不空，如此定義的二叉樹的存儲結構稱作“線索鏈77typedefstruct

BiThrNod{

TElemTypedata;

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

PointerThrLTag,RTag;//左右標志}BiThrNode,*BiThrTree;2、線索鏈表的類型描述：

typedef

enum{

Link,Thread

}PointerThr;

//Link==0:指針，Thread==1:線索typedefstructBiThrNod2、線索鏈表78二、線索鏈表的遍歷算法:

for(p=

firstNode(T);p;p=Succ(p))Visit(p);由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡化了遍歷的算法。二、線索鏈表的遍歷算法:for(p=firstNo79例如:對中序線索化鏈表的遍歷算法

※中序遍歷的第一個結點？

※在中序線索化鏈表中結點的后繼？左子樹上處于“最左下”（沒有左子樹）的結點。若無右子樹，則為后繼線索所指結點；否則為對其右子樹進行中序遍歷時訪問的第一個結點。例如:對中序線索化鏈表的遍歷算法※中序遍歷的第一80voidInOrder(BiThrTreeT,void(*Visit)(TElemTypee)){p=T->lchild;//p指向根結點

while(p!=T){

//空樹或遍歷結束時，p==Twhile(p->LTag==Link)p=p->lchild;//第一個結點while(p->RTag==Thread&&p->rchild!=T)

{//為右線索時找其右線索p=p->rchild;Visit(p->data);//訪問后繼結點

}p=p->rchild;//p進至其右子樹根

}}

//InOrdervoidInOrder(BiThrTreeT,void81三、如何建立線索鏈表？ABDEGCFH中序遍歷序列：DBEGAFHCNULLNULL方法：在遍歷過程中修改空指針或先寫出遍歷序列，標出空指針，對照再畫出線索。三、如何建立線索鏈表？ABDEGCFH中序遍歷序列：DB82

6.6樹和森林的表示方法6.6樹和森林83樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉鏈表(孩子-兄弟）存儲表示法樹的三種存儲結構一、雙親表示法二、孩子鏈表表示法三、樹的二叉84一、雙親表示法:1、定義：用一組地址連續(xù)的空間存儲樹的結點，同時在每個結點中附設一個指示器指示雙親結點在鏈表中的位置。（即：保存結點信息和雙親的下標）一、雙親表示法:1、定義：用一組地址連續(xù)的空間存儲樹的結點，85ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparent2、特點：求雙親簡便，求孩子麻煩。ABCDEFG0A-1r=0datap86

typedefstructPTNode{ElemTypedata;

intparent;//雙親位置域

}PTNode;

dataparent#defineMAX_TREE_SIZE100結點結構:3、C語言的類型描述:typedefstructPTNode{dat87typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根結點的位置和結點個數(shù)

}PTree;樹結構:typedefstruct{樹結構:88二、孩子鏈表表示法:1、定義：把每個結點的孩子結點鏈成單鏈表。2、特點：求孩子方便，求雙親麻煩。二、孩子鏈表表示法:1、定義：把每個結點的孩子結點鏈成單鏈表89ABCDEFG0

A1

B2

C3

D4

E5

F6

Gr=0n=7datafirstchild123456孩子鏈表表示法ABCDEFG0Ar=0datafirstchi90ABCDEFG0

A

-11

B

02

C

03

D

04

E

25

F

26

G

5r=0n=7dataparentfirstchild123456-10002243、可能把孩子鏈表表示法和雙親表示法結合起來。ABCDEFG0A-1r=0dataparen91typedefstructCTNode{

intchild;

structCTNode*next;

}*ChildPtr;孩子結點結構:

childnext4、C語言的類型描述:typedefstructCTNode{孩子結點結構:92

typedefstruct{ElemTypedata;ChildPtrfirstchild;//孩子鏈的頭指針

}CTBox;雙親結點結構

datafirstchildtypedefstruct{雙親結點結構data93typedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//結點數(shù)和根結點的位置

}CTree;樹結構:typedefstruct{樹結構:94三、樹的二叉鏈表(孩子-兄弟）存儲表示法1、定義：鏈表中結點的兩個鏈域分別指向該結點的第一個孩子結點和下一個兄弟結點。2、結點結構：firstchilddatanextsibling第一個孩子下一個兄弟三、樹的二叉鏈表(孩子-兄弟）存儲表示法1、定義：鏈表中結95ABCDEFGABCEDFGrootABCEDFG

ABCDEFGAroot96typedefstructCSNode{TElemTypedata;

structCSNode

*firstchild,*nextsibling;}CSNode,*CSTree;3、C語言的類型描述:結點結構:

firstchilddatanextsiblingtypedefstructCSNode{3、C語言的類型97四、樹和二叉樹的轉(zhuǎn)換1、轉(zhuǎn)換規(guī)則樹的根樹的第一個孩子右兄弟二叉樹的根左孩子右孩子注：由樹轉(zhuǎn)換得到的二叉樹的右子樹永遠為空！四、樹和二叉樹的轉(zhuǎn)換1、轉(zhuǎn)換規(guī)則二叉樹的根左孩子右孩子注：98五、森林和二叉樹的轉(zhuǎn)換1、規(guī)則：森林中第一棵樹的根變成二叉樹的根森林中其它樹的根當成第一棵樹的根的兄弟把森林中每棵樹都轉(zhuǎn)化成相應的二叉樹注：由森林轉(zhuǎn)換得到的二叉樹的右子樹可能不為空！五、森林和二叉樹的轉(zhuǎn)換1、規(guī)則：注：由森林轉(zhuǎn)換得到的二叉樹99ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI1006.7樹和森林的遍歷6.7101一、樹的遍歷二、森林的遍歷一、樹的遍歷二、森林的遍歷102ABCDEFGHIJK一、樹的遍歷把樹看成兩部分：1。樹的根2。根的子樹森林12A一、樹的遍歷12103樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:若樹不空，則先訪問根結點，然后依次先根遍歷各棵子樹。若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結點。若樹不空，則自上而下自左至右訪問樹中每個結點。1、22、1樹的遍歷可有三條搜索路徑:按層次遍歷:先根(次序)遍歷:后根104ABCDEFGHIJK先根遍歷時頂點的訪問次序：ABEFCDGHIJK后根遍歷時頂點的訪問次序：EFBCIJKHGDA層次遍歷時頂點的訪問次序：ABCDEFGHIJKA先根遍歷時頂點的訪問次105

BCDEFGHIJK森林中第一棵樹的根結點；森林中第一棵樹的子樹森林；森林中其它樹構成的森林。森林由三部分構成：二、森林的遍歷123森林中第一棵樹的根結點；森林中第一棵1061.先序遍歷若森林不空，則訪問森林中第一棵樹的根結點；先序遍歷森林中第一棵樹的子樹森林；先序遍歷森林中(除第一棵樹之外)其余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行先序遍歷。(1、2、3)1.先序遍歷107

BCDEFGHIJK123先序遍歷序列：BEFCDGHIJK123先序遍歷序列：BEFCDGHI108２．中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林；訪問森林中第一棵樹的根結點；中序遍歷森林中(除第一棵樹之外)其

余樹構成的森林。即：依次從左至右對森林中的每一棵樹進行中序遍歷。(2、1、3)２．中序遍歷若森林不空，則即：依次從左至右對森109

BCDEFGHIJK123中序遍歷序列：EFBCIJKHGD123中序遍歷序列：EFBCIJKH1106.8哈夫曼樹與

哈夫曼編碼

幾個預備概念

最優(yōu)樹的定義

如何構造最優(yōu)樹

前綴編碼

6.8哈夫曼樹與

哈夫曼編碼111幾個概念路徑：樹中一個結點到另一個結點所經(jīng)過的分支。路徑長度：路徑上的分支數(shù)目。樹的路徑長度：從根到每一個結點的路徑長度之和。（完全二叉樹是路徑長度最短的二叉樹）ABCD幾個概念路徑：樹中一個結點到另一個結點所經(jīng)過的分支。ABCD112

一、最優(yōu)樹的定義結點的帶權路徑長度定義為：

結點的權值乘以該結點的路徑長度。結點的路徑長度定義為：

從根結點到該結點的路徑上分支的數(shù)目。一、最優(yōu)樹的定義結點的帶權路徑長度定義為：結點的路徑長度113樹的帶權路徑長度定義為：

樹中所有葉子結點的帶權路徑長度之和WPL(T)=wklk(對所有葉子結點)。

在所有含n個葉子結點、并帶相同權值的m叉樹中，必存在一棵其帶權路徑長度取最小值的樹，稱為“最優(yōu)二叉樹”。例如：樹的帶權路徑長度定義為：在所有含n個葉子結11427975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=895427975492WPL(T)=7115用給定的n個權值構造n棵以各權值為根的二叉樹。二、如何構造最優(yōu)樹(哈夫曼樹）(1)(赫夫曼算法)以二叉樹為例：問題：根據(jù)給定的n個權值{w1,w2,…,wn}，構造一棵以這些權值為葉子的哈夫曼樹？用給定的n個權值構造n棵以各權值為根的二叉樹。二、如何構116選取其根結點的權值為最小的兩棵二叉樹，分別作為左、右子樹構造一棵新的二叉樹，并且這棵新的二叉樹根結點的權值為其左、右子樹根結點的權值之和；并刪去這兩棵二叉樹，同時加入剛新生成的二叉樹；(2)(3)重復

第(2)

步，直至生成一棵樹為止。選取其根結點的權值為最小的兩棵二叉樹，分別作為左、1179例如:已知權值W={5,6,2,9,7}5627527697671395279例如:已知權值W={5,6,2,9,7}51186713952795271667132900001111000110110111671395279527166713290000111100119

指的是，任何一個字符的編碼都不是同一字符集中另一個字符的編碼碼的前綴。三、前綴編碼

利用哈夫曼樹可以構造一種不等長的二進制編碼，并且構造所得的哈夫曼編碼是一種最優(yōu)前綴編碼，即：使所傳電文的總長度最短。指的是，任何一個字符的編碼都三、前綴編碼120有八種字符：abcdefgh，其在通信聯(lián)絡中出現(xiàn)的概率分別為：0.050.290.070.080.140.230.030.11,試設計哈夫曼遍碼。

設權w=(5,29,7,8,14,23,3,11)n=8構造過程：52978142331153829781423117815292311141119291423142929232342295810000000001111111a:0000b:11c:1000d:1001e:101f:01g:0001h:001有八種字符：abcdefgh，其在通信聯(lián)絡中121作業(yè)以數(shù)據(jù)集{2，5，7，9，13}為權值構造一棵huffman樹，并計算其帶權路徑長度。習題集P416.26（僅使用01編碼方案）作業(yè)122按層次遍歷二叉樹（二叉鏈表）分析：使用一個隊列，先將二叉樹根結點入隊列，然后出隊，并輸出該結點。若它有左孩子則左孩子入隊；若有右孩子則右孩子入隊，然后分別出隊，直到隊列為空。

按層次遍歷二叉樹（二叉鏈表）分析：123#defineMAXSIZE100structqueue{bitreev[MAXSIZE];

intfront,rear;

//隊頭、隊尾指針}q;voidlevelorder(bitreet){q.front=q.rear=0;//初始化空隊列

if(t!=NULL)printf(“%d”,t->data);

//遍歷根結點

q.v[q.rear]=t;q.rear=q.rear+1;

//結點指針入隊while(q.front<q.rear)//隊列不空

{

s=q.v[q.front];q.front=q.front;

//隊頭出隊if(s->lchild!=NULL)//遍歷左孩子

{printf(“%d”,s->lchile->data);q.v[q.rear]=s->lchild;q.rear=q.rear+1;}if(s->rchild!=NULL)//遍歷右孩子{printf(“%d”,s->rchile->data);q.v[q.rear]=s->rchild;q.rear=q.rear+1;}

}}

#defineMAXSIZE100124

1.熟練掌握二叉樹的結構特性，了解相應的證明方法。2.熟悉二叉樹的各種存儲結構的特點及適用范圍。3.遍歷二叉樹是二叉樹各種操作的基礎。實現(xiàn)二叉樹遍歷的具體算法與所采用的存儲結構有關。掌握各種遍歷策略的遞歸算法，靈活運用遍歷算法實現(xiàn)二叉樹的其它操作。層次遍歷是按另一種搜索策略進行的遍歷。1.熟練掌握二叉樹的結構特性，了解相應的證明方法。1254.理解二叉樹線索化的實質(zhì)是建立結點與其在相應序列中的前驅(qū)或后繼之間的直接聯(lián)系，熟練掌握二叉樹的線索化過程以及在中序線索化樹上找給定結點的前驅(qū)和后繼的方法。二叉樹的線索化過程是基于對二叉樹進行遍歷，而線索二叉樹上的線索又為相應的遍歷提供了方便。4.理解二叉樹線索化的實質(zhì)是建立結點與其在相應序列中的1265.熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹的轉(zhuǎn)換方法。建立存儲結構是進行其它操作的前提，因此讀者應掌握1至2種建立二叉樹和樹的存儲結構的方法。6.學會編寫實現(xiàn)樹的各種操作的算法。7.了解最優(yōu)樹的特性，掌握建立最優(yōu)樹和哈夫曼編碼的方法。5.熟悉樹的各種存儲結構及其特點，掌握樹和森林與二叉樹127

第六章樹和二叉樹第六章樹和二叉樹1286.1樹的類型定義6.2二叉樹的類型定義6.3

二叉樹的存儲結構6.4二叉樹的遍歷6.5線索二叉樹6.6樹和森林的表示方法6.7樹和森林的遍歷6.8哈夫曼樹與哈夫曼編碼6.1樹的類型定義6.2二叉樹的類型定義6.3二叉樹的1296.1樹的類型定義6.1130數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。

若D為空集，則稱為空樹。否則:(1)在D中存在唯一的稱為根的數(shù)據(jù)元素root；(2)當n>1時，其余結點可分為m(m>0)個互不相交的有限集T1,T2,…,Tm，其中每一棵子集本身又是一棵符合本定義的樹，稱為根root的子樹。

數(shù)據(jù)關系R：數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。若D131

基本操作：查找類

插入類刪除類基本操作：查找類插入類刪除類132

Root(T)//求樹的根結點

查找類：Value(T,cur_e)//求當前結點的元素值

Parent(T,cur_e)//求當前結點的雙親結點LeftChild(T,cur_e)//求當前結點的最左孩子RightSibling(T,cur_e)//求當前結點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷Root(T)//求樹的根結點查找類：Val133InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構造樹Assign(T,cur_e,value)//給當前結點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結點p的第i棵子樹InitTree(&T)//初始化置空樹插入類：C134

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結構DeleteChild(&T,&p,i)//刪除結點p的第i棵子樹ClearTree(&T)//將樹清空刪除類：De1351、樹（Tree)：是n個結點的有限集（n>=0)。在任意一棵非空樹中，有且僅有一個特定的稱為根的結點（root)；當n>1時，其余結點可分為m（m>0)個互不相交的有限集T1,T2,…,Tm,其中每個集合Ti本身又是一棵符合本定義的樹，并且稱為根root的子樹。1、樹（Tree)：是n個結點的有限集（n>=0)。在任意一136(１)有確定的根；(２)樹根和子樹根之間為有向關系。有向樹：有序樹：樹中結點的各子樹之間的先后次序是有意義的，不能互換，否則就成為另一棵樹了。子樹之間存在確定的次序關系。無序樹：樹中結點的各子樹之間的先后次序無意義，可以互換。子樹之間不存在確定的次序關系。(１)有確定的根；有向樹：有序樹：樹中結點的各子樹之間的先137ABCDEFGHIJMKLA(B(E,F(K,L)),

C(G),

D(H,I,J(M))

)T1T3T2樹根例如:ABCDEFGHIJMKLA(B(E,F(K,L)),138樹的示意圖：根結點根結點葉結點分支結點子樹子樹子樹Level1Level2Level3Level4結點的層次樹的示意圖：根結點根結點葉結點分支結點子樹子樹子樹Level139對比樹型結構和線性結構的結構特點對比樹型結構和線性結構的結構特點140~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結構樹型結構第一個數(shù)據(jù)元素(無前驅(qū))

根結點(無前驅(qū))最后一個數(shù)據(jù)元素(無后繼)多個葉子結點(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~141基本術語基本術語1421、結點:2、結點的度:3、樹的度:4、葉子結點:5、分支結點:數(shù)據(jù)元素+若干指向子樹的分支分支的個數(shù)樹中所有結點的度的最大值度為零的結點度大于零的結點DHIJM（終端結點）（非終端結點）1、結點:2、結點的度:3、樹的度:4、葉子結點:5、分支結1436、(從根到結點的)路徑：7、孩子結點、雙親結點兄弟結點、堂兄弟結點祖先結點、子孫結點8、結點的層次:9、樹的深度：

由從根到該結點所經(jīng)分支和結點構成ABCDEFGHIJMKL假設根結點的層次為1，依次加1樹中葉子結點所在的最大層次6、(從根到結點的)路徑：7、孩子結點、雙親結點8、結點的層144任何一棵非空樹是一個二元組Tree=（root，F(xiàn)）其中：root被稱為根結點F被稱為子樹森林10、森林：是m（m≥0）棵互不相交的樹的集合。ArootBCDEFGHIJMKLF任何一棵非空樹是一個二元組10、森林：是m（m≥0）棵互Ar1456.2

二叉樹的類型定義二叉樹是樹的基礎，一般的樹可以轉(zhuǎn)化為二叉樹來處理。6.2146

1、二叉樹的定義：

二叉樹或為空樹，或是由一個根結點加上兩棵分別稱為左子樹和右子樹的、互不交的二叉樹組成（即左、右子樹次序不能顛倒）。ABCDEFGHK根結點左子樹右子樹1、二叉樹的定義：二叉樹或為空樹，或是由一個根結點加1472、二叉樹的五種基本形態(tài)：N空樹只含根結點NNNLRR右子樹為空樹L左子樹為空樹左右子樹均不為空樹2、二叉樹的五種基本形態(tài)：N空樹只含根結點NNNLRR右子樹148

二叉樹的主要基本操作：查找類插入類刪除類二叉樹的主要基本操作：查找類插入類刪除149

Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);

PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());Root(T);Value(T,e);150

InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);InitBiTree(&T);151ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);ClearBiTree(&T);152二叉樹

的重要特性二叉樹

的重要特性153

性質(zhì)1：

在二叉樹的第i層上至多有2i-1個結點。(i≥1)用歸納法證明：

歸納基：

歸納假設：

歸納證明：i=1

層時，只有一個根結點：

2i-1=20=1；假設對所有的j，1≤j

i，命題成立；由歸納假設知：第I-1層上至多有2i-2個結點。又因為二叉樹上每個結點至多有兩棵子樹，則第i層的結點數(shù)=2i-22=2i-1

。性質(zhì)1：在二叉樹的第i層上至多有154性質(zhì)2：

深度為k的二叉樹上至多有2k-1個結點（k≥1）。證明：[證明用求等比數(shù)列前k項和的公式]基于上一條性質(zhì)，深度為k的二叉樹上的結點數(shù)至多為

20+21+

+2k-1=2k-1。性質(zhì)2：

深度為k的二叉樹上至多有2k-1155

性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子結點、n2個度為2的結點，則必存在關系式：n0=n2+1。證明：設二叉樹上結點總數(shù)n=n0+n1+n2又二叉樹上分支總數(shù)b=n0*0+n1+2n2

而b=n-1=n0+n1+n2-1由此，n0=n2+1。性質(zhì)3：

對任何一棵二叉樹，若它含有n0個葉子156兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1個結點的二叉樹。完全二叉樹：樹中所含的n個結點和滿二叉樹中編號為1至n的結點一一對應。123456789101112131415abcdefghij兩類特殊形態(tài)的二叉樹：滿二叉樹：指的是深度為k且含有2k-1157

性質(zhì)4：

具有n個結點的完全二叉樹的深度為log2n+1。證明：設完全二叉樹的深度為k，則由性質(zhì)2和完全二叉樹的定義知：深度為k-1的二叉樹應該是一棵滿二叉樹，故結點數(shù)為2k-1-1；深度為k的完全二叉樹當為滿二叉樹時結點數(shù)最多為2k–1。所以得2k-1-1

<n≤2k–1

2k-1≤n<2k

即k-1≤log2n<k因為k只能是整數(shù)，因此，k=log2n

+1。性質(zhì)4：具有n個結點的完全二叉樹的深度為158性質(zhì)5：若對含n個結點的完全二叉樹從上到下且從左至右進行1至n的編號，則對完全二叉樹中任意一個編號為i的結點：

(1)若i=1，則該結點是二叉樹的根，無雙親，否則，編號為i/2的結點為其雙親結點；

(2)若2i>n，則該結點無左孩子，

否則，編號為2i的結點為其左孩子結點；

(3)