數(shù)據(jù)結(jié)構(gòu)第5章課件-中國(guó)石油大學(xué)(華東)

11第五章樹(shù)與二叉樹(shù)22第五章樹(shù)與二叉樹(shù)5.1樹(shù)的基本概念5.2二叉樹(shù)5.3

二叉樹(shù)的存儲(chǔ)表示5.5線(xiàn)索二叉樹(shù)5.6樹(shù)和森林5.8哈夫曼樹(shù)與哈夫曼編碼5.4二叉樹(shù)的遍歷及其應(yīng)用5.7樹(shù)和森林的遍歷及其應(yīng)用335.1樹(shù)的基本概念5.1.1樹(shù)的定義和術(shù)語(yǔ)兩種樹(shù)：自由樹(shù)與有根樹(shù)。

①自由樹(shù)： 一棵自由樹(shù)Tf

可定義為一個(gè)二元組

Tf

=(V,E)

其中V={v1,...,vn}

是由n(n＞0)個(gè)元素組成的有限非空集合，稱(chēng)為頂點(diǎn)集合。E={(vi,vj)|vi,vj

V,1≤i,j≤n}

是n-1個(gè)序?qū)Φ募?，稱(chēng)為邊集合，E

中的元素(vi,vj）稱(chēng)為邊或分支。44自由樹(shù)②有根樹(shù)： 一棵有根樹(shù)T，簡(jiǎn)稱(chēng)為樹(shù)，它是n(n≥0)

個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，T稱(chēng)為空樹(shù)；否則，T

是非空樹(shù)，記作

55r是一個(gè)特定的稱(chēng)為根(root)的結(jié)點(diǎn)，它只有直接后繼，沒(méi)有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為m(m

0)個(gè)互不相交的有限集合T1,T2,…,Tm，每個(gè)集合又是一棵樹(shù)，并且稱(chēng)之為根的子樹(shù)。每棵子樹(shù)的根結(jié)點(diǎn)有且僅有一個(gè)直接前驅(qū)，但可以有0個(gè)或多個(gè)直接后繼。6a.直觀(guān)表示法：

用圓圈表示結(jié)點(diǎn)，元素寫(xiě)在圓圈中，連線(xiàn)表示元素之間的關(guān)系。根在上，葉子在下（即樹(shù)向下生長(zhǎng)）。acebdfg③樹(shù)的常見(jiàn)表示方法7b.嵌套集合表示法：根據(jù)樹(shù)的集合定義，寫(xiě)出集合劃分。{a,{b,{e},{f}},

{c},

{d,{g}}}c.文氏圖表示法：集合表示的一種直觀(guān)表示，用圖表示集合。acbefdgacebdfg直觀(guān)表示法8結(jié)點(diǎn):結(jié)點(diǎn)的度:樹(shù)的度:葉子結(jié)點(diǎn):分支結(jié)點(diǎn):數(shù)據(jù)元素+若干指向子樹(shù)的分支分支的個(gè)數(shù)即結(jié)點(diǎn)擁有的子樹(shù)數(shù)一棵樹(shù)中各結(jié)點(diǎn)度數(shù)的最大值度為零的結(jié)點(diǎn)度大于零的結(jié)點(diǎn)DHIJM④樹(shù)的基本術(shù)語(yǔ)9子女結(jié)點(diǎn)、雙親結(jié)點(diǎn)兄弟結(jié)點(diǎn)、堂兄弟祖先結(jié)點(diǎn)、子孫結(jié)點(diǎn)結(jié)點(diǎn)的層次:樹(shù)的深度：(從根到結(jié)點(diǎn)的)路徑：由從根到該結(jié)點(diǎn)所經(jīng)分支和結(jié)點(diǎn)構(gòu)成。ABCDEFGHIJMKL規(guī)定根結(jié)點(diǎn)的層次為1，它的孩子為第2層……樹(shù)中葉子結(jié)點(diǎn)所在的最大層次1010等于根結(jié)點(diǎn)的高度，即根結(jié)點(diǎn)所有子女高度的最大值加一。高度：樹(shù)的高度:有序樹(shù)：無(wú)序樹(shù):森林:規(guī)定葉結(jié)點(diǎn)的高度為1，其雙親結(jié)點(diǎn)的高度等于它的高度加一。樹(shù)中結(jié)點(diǎn)的各棵子樹(shù)T0,T1,…是有次序的，即為有序樹(shù)。樹(shù)中結(jié)點(diǎn)的各棵子樹(shù)之間的次序是不重要的，可以互相交換位置。是m（m≥0）棵樹(shù)的集合。

1111二叉樹(shù)的五種不同形態(tài)LLRR5.2二叉樹(shù)(BinaryTree)5.2.1二叉樹(shù)的定義 每個(gè)結(jié)點(diǎn)最多有2棵子樹(shù)，且有左右之分。問(wèn)：二叉樹(shù)有幾種可能的形態(tài)？

1212二叉樹(shù)的性質(zhì)性質(zhì)1:

若二叉樹(shù)結(jié)點(diǎn)的層次從1開(kāi)始,則在二叉樹(shù)的第i層最多有

2i-1

個(gè)結(jié)點(diǎn)。(i≥1)[證明用數(shù)學(xué)歸納法]性質(zhì)2:

深度為k

的二叉樹(shù)最少有k

個(gè)結(jié)點(diǎn)，最多有2k-1個(gè)結(jié)點(diǎn)。(k≥1)每一層最少要有1個(gè)結(jié)點(diǎn)，因此，最少結(jié)點(diǎn)數(shù)為k。最多結(jié)點(diǎn)個(gè)數(shù)借助性質(zhì)1：用求等比級(jí)數(shù)前k項(xiàng)和的公式:

20+21+22+…+2k-1=2k-1問(wèn)：第i層上至少有

個(gè)結(jié)點(diǎn)？11313性質(zhì)3:

對(duì)任何一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)有n0個(gè),度為2的非葉結(jié)點(diǎn)有n2個(gè),則有

n0＝n2＋1

若設(shè)度為1的結(jié)點(diǎn)有n1個(gè)，總結(jié)點(diǎn)數(shù)為n， 總邊數(shù)為e，則根據(jù)二叉樹(shù)的定義，

n=n0+n1+n2

e

=2n2+n1=

n-1

因此，有2n2+n1=n0+n1+n2-1

n2=n0-1n0=n2+11414定義1:

滿(mǎn)二叉樹(shù)(FullBinaryTree)

定義2:

完全二叉樹(shù)(CompleteBinaryTree)若設(shè)二叉樹(shù)的深度為k，則共有k層。除第k層外，其它各層(1～k-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹(shù)。151231145891213571014151231145891257101234557123455問(wèn)：下列哪棵二叉樹(shù)為完全二叉樹(shù)？1616性質(zhì)4:

具有n(n≥0)個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為

log2(n+1)

。

設(shè)完全二叉樹(shù)的深度為k，則有

2k-1-1<n

≤2k-1

變形2k-1<n+1≤2k

取對(duì)數(shù)k-1<log2(n+1)≤k,有

log2(n+1)

=k上面k-1層結(jié)點(diǎn)數(shù)包括第k層的最大結(jié)點(diǎn)數(shù)23-124-11717性質(zhì)5：如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1,2,…,n，則有以下關(guān)系：若i=1,則i無(wú)雙親若i>1,則i的雙親為

i／2

若2*i<=n,則i的左子女為

2*i， 若2*i+1<=n,則i的右子女為2*i+1若i為奇數(shù),且i!=1,

則其左兄弟為i-1,若

i為偶數(shù),且i!=n,

則其右兄弟為i+11234856791018討論：②設(shè)一棵完全二叉樹(shù)具有1000個(gè)結(jié)點(diǎn)，則它有

個(gè)葉子結(jié)點(diǎn)，有

個(gè)度為2的結(jié)點(diǎn)，有

個(gè)結(jié)點(diǎn)只有非空左子樹(shù)，有

個(gè)結(jié)點(diǎn)只有非空右子樹(shù)。50049910①為什么要研究滿(mǎn)二叉樹(shù)和完全二叉樹(shù)這兩種特殊形式？因?yàn)橹挥羞@兩種形式可以實(shí)現(xiàn)順序存儲(chǔ)！由于最后一層葉子數(shù)為489個(gè)，是奇數(shù)，說(shuō)明有1個(gè)結(jié)點(diǎn)只有非空左子樹(shù)；而完全二叉樹(shù)中不可能出現(xiàn)非空右子樹(shù)(0個(gè))。易求出總層數(shù)和末層葉子數(shù)?？倢訑?shù)k=

log2n+1)=10;且前9層總結(jié)點(diǎn)數(shù)為29-1=511(完全二叉樹(shù)的前k-1層肯定是滿(mǎn)的)所以末層葉子數(shù)為1000-511=489個(gè)。末層的葉子只占據(jù)了上層的245個(gè)結(jié)點(diǎn)（

489/2),上層（k=9)右邊的0度結(jié)點(diǎn)數(shù)還有29-1-245=11個(gè)！195.3二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)5.3.2

二叉樹(shù)的鏈?zhǔn)酱鎯?chǔ)表示5.3.1二叉樹(shù)的順序存儲(chǔ)表示20205.3.1二叉樹(shù)的順序表示完全二叉樹(shù)的順序表示1123456789

10

24891056731412346789

12

1412376489125101113一般二叉樹(shù)的順序表示21211371531極端情形:只有右單支的二叉樹(shù)1371531順序存儲(chǔ)的特點(diǎn)：結(jié)點(diǎn)間關(guān)系蘊(yùn)含在其存儲(chǔ)位置中浪費(fèi)空間，適于存滿(mǎn)二叉樹(shù)和完全二叉樹(shù)2222二叉樹(shù)結(jié)點(diǎn)定義：每個(gè)結(jié)點(diǎn)有3個(gè)數(shù)據(jù)成員，data域存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)，leftChild和rightChild分別存放指向左子女和右子女的指針。leftChilddatarightChilddataleftChildrightChild二叉鏈表5.3.2二叉樹(shù)的鏈表表示（二叉鏈表）2323leftChilddataparentrightChildparentdataleftChildrightChild三叉鏈表二叉樹(shù)的鏈表表示（三叉鏈表）每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親的指針parent，使得查找雙親也很方便。2424二叉樹(shù)鏈表表示的示例

AABBCCDDFFEErootroot

ABCDFEroot二叉樹(shù)二叉鏈表三叉鏈表2525二叉鏈表的靜態(tài)結(jié)構(gòu)ABCDFErootdataparentleftChildrightChild012345A

-11-1B

023C

1

-1-1D

145E

3-1-1F

3-1-12626二叉樹(shù)的類(lèi)定義#include<iostream.h>classBinaryTree;classBinTreeNode{

//結(jié)點(diǎn)類(lèi)的定義friendBinaryTree;public:BinTreeNode(){leftChild=NULL;rightChild=NULL;}

BinTreeNode(DataTypex,BinTreeNode

*left=NULL,BinTreeNode*right=NULL):data(x),leftChild(left),rightChild(right){}//構(gòu)造函數(shù)

~BinTreeNode(){}//析構(gòu)函數(shù)private:BinTreeNode*leftChild,*rightChild;//左、右子女鏈域DataTypedata;//數(shù)據(jù)域};

2727classBinaryTree{public: BinaryTree():root(NULL){} BinaryTree(DataTypevalue){RefValue=value;root=NULL;} ~BinaryTree(){destroy(root);} voidCreateBinTree(){CreateBinTree(root);}為什么既定義公有函數(shù)又定義私有函數(shù)？boolIsEmpty(){return(root==NULL)?true:false;}BinTreeNode*Parent(BinTreeNode*current) {return(root==NULL||root==current)?NULL:Parent(root,current);}2828BinTreeNode*LeftChild(BinTreeNode*current) {return(current!=NULL)?current->leftChild:NULL;}BinTreeNode*RightChild(BinTreeNode*current) {return(current!=NULL)?current->rightChild:NULL;} intHeight(

){returnHeight(root);} intSize(

){returnSize(root);} BinTreeNode*GetRoot()const{returnroot;} voidpreOrder(){preOrder(root);}//前序遍歷 voidinOrder(

){inOrder(root);}//中序遍歷 voidpostOrder(

){postOrder(root);}//后序遍歷 voidlevelOrder();//不需要遞歸，所以直接對(duì)外接口調(diào)用即可。層序遍歷

2929private:BinTreeNode*root;//二叉樹(shù)的根指針 DataTypeRefValue;//數(shù)據(jù)輸入停止標(biāo)志

voidCreateBinTree(BinTreeNode*&subTree) BinTreeNode*Parent(BinTreeNode*subTree,BinTreeNode*current);

intHeight(BinTreeNode*subTree); intSize(BinTreeNode*subTree); voidpreOrder(BinTreeNode*subTree);//前序遍歷

voidinOrder(BinTreeNode*subTree);//中序遍歷

voidpostOrder(BinTreeNode*subTree);//后序遍歷

voiddestroy(BinTreeNode*&subTree);};

30305.4二叉樹(shù)遍歷二叉樹(shù)的遍歷就是按某種次序訪(fǎng)問(wèn)樹(shù)中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪(fǎng)問(wèn)且僅訪(fǎng)問(wèn)一次。設(shè)訪(fǎng)問(wèn)根結(jié)點(diǎn)記作

V

遍歷根的左子樹(shù)記作

L

遍歷根的右子樹(shù)記作

R則可能的遍歷次序有(只考慮先左后右)

前序VLR

中序

LVR

后序LRV

3131中序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則中序遍歷左子樹(shù)(L)；訪(fǎng)問(wèn)根結(jié)點(diǎn)(V)；中序遍歷右子樹(shù)(R)。遍歷結(jié)果:

a+b*c

-

d

-

e/f5.4.1二叉樹(shù)遍歷的遞歸算法

①中序遍歷(InorderTraversal)--/+*abcdef3232前序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則訪(fǎng)問(wèn)根結(jié)點(diǎn)(V)；前序遍歷左子樹(shù)(L)；前序遍歷右子樹(shù)(R)。遍歷結(jié)果:

-+a*b

-

cd/ef②前序遍歷(PreorderTraversal)--/+*abcdef3333后序遍歷二叉樹(shù)算法的框架是：若二叉樹(shù)為空，則空操作；否則后序遍歷左子樹(shù)(L)；后序遍歷右子樹(shù)(R)；訪(fǎng)問(wèn)根結(jié)點(diǎn)(V)。遍歷結(jié)果:

abcd

-*+ef/-③后序遍歷(PostorderTraversal)--/+*abcdef3434

voidBinaryTree::inOrder(BinTreeNode*subTree){

//私有函數(shù)，中序遍歷以subTree為根的二叉樹(shù)if(subTree!=NULL){ inOrder(subTree->leftChild); cout<<subTree->data; inOrder(subTree->rightChild);}}二叉樹(shù)遞歸的中序遍歷算法3535

voidBinaryTree::PreOrder(BinTreeNode*subTree){

//私有函數(shù)，前序遍歷以subTree為根的二叉樹(shù)if(subTree!=NULL){ cout<<subTree->data; PreOrder(subTree->leftChild); PreOrder(subTree->rightChild);}}二叉樹(shù)遞歸的前序遍歷算法3636

voidBinaryTree::PostOrder(BinTreeNode*subTree){

//私有函數(shù)，后序遍歷以subTree為根的二叉樹(shù)if(subTree!=NULL){ PostOrder(subTree->leftChild); PostOrder(subTree->rightChild); cout<<subTree->data;}}二叉樹(shù)遞歸的后序遍歷算法37375.4.2遞歸算法在樹(shù)中的應(yīng)用以遞歸方式建立二叉樹(shù)。輸入結(jié)點(diǎn)值的順序必須對(duì)應(yīng)二叉樹(shù)結(jié)點(diǎn)完全前序遍歷的順序。約定以輸入序列中不可能出現(xiàn)的值作為空結(jié)點(diǎn)的值以結(jié)束遞歸,此值在RefValue中。例如用“@”或用“-1”表示字符序列或正整數(shù)序列空結(jié)點(diǎn)。3838如圖所示的二叉樹(shù)的前序遍歷順序?yàn)锳BC@@DE@G@@F@@@ABCDEGF@@@@@@@@39voidBinaryTree::CreateBinTree(BinTreeNode*&subTree){//私有函數(shù):建立根為subTree的子樹(shù)DataTypeitem; cin>>item; if(item!=RefValue){ subTree=newBinTreeNode(item); CreateBinTree(subTree->leftChild); CreateBinTree(subTree->rightChild);

} elsesubTree=NULL;};39^item^ABC@@DE@G@@F@@@4040BinTreeNode*BinaryTree::Parent(BinTreeNode*subTree,BinTreeNode*current){//私有函數(shù):從結(jié)點(diǎn)

subTree開(kāi)始,搜索結(jié)點(diǎn)

current的//雙親,若找到則返回雙親結(jié)點(diǎn)地址,否則返回NULLif(subTree==NULL)returnNULL;if(subTree->leftChild==current||

subTree->rightChild==current)

returnsubTree; //找到,返回父結(jié)點(diǎn)地址

returnParent(subTree->leftChild,current);returnParent(subTree->rightChild,

current); };//改錯(cuò)找雙親節(jié)點(diǎn)4141

清空樹(shù)voidBinaryTree::destroy(BinTreeNode*subTree){//私有函數(shù):刪除根為subTree的子樹(shù)

if(subTree!=NULL){

destroy(subTree->leftChild);//刪除左子樹(shù)

destroy(subTree->rightChild);//刪除右子樹(shù)

deletesubTree; //刪除根結(jié)點(diǎn)

}};4242

計(jì)算二叉樹(shù)深度或高度的函數(shù)intBinaryTree::Depth(constBinTreeNode*subTree)const{ if(subTree==NULL)return0;//空二叉樹(shù)的深度為0 elsereturn1+Max(Depth(subTree->leftChild),Depth(subTree->rightChild));}4343

計(jì)算二叉樹(shù)結(jié)點(diǎn)個(gè)數(shù)的函數(shù)intBinaryTree::Size(constBinTreeNode*subTree)const{//私有函數(shù)，計(jì)算根指針為subTree的二叉樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)if(subTree==NULL)return0;elsereturn}1+Size(subTree->leftChild)+Size(subTree->rightChild);44思路：①若根不為空，訪(fǎng)問(wèn)根，若右子樹(shù)不為空則入棧；②若左子樹(shù)不為空，則訪(fǎng)問(wèn)左子樹(shù)，

若左子樹(shù)為空，退棧。重復(fù)執(zhí)行上述過(guò)程，直到遍歷完44abcde5.4.3二叉樹(shù)遍歷的非遞歸算法

①前序遍歷的非遞歸算法4545前序遍歷的非遞歸算法voidBinaryTree::PreOrder(BinTreeNode*t){SeqstackS;

BinTreeNode

*p=root;

S.Push(NULL); while(p!=NULL){

cout<<p->data; //訪(fǎng)問(wèn)結(jié)點(diǎn)

if(p->rightChild!=NULL)S.Push(p->rightChild);//預(yù)留右指針在棧中if(p->leftChild!=NULL)p=p->leftChild; //訪(fǎng)問(wèn)左子樹(shù)

elseS.Pop(p); //左子樹(shù)為空

}};4646層次序遍歷二叉樹(shù)就是從根結(jié)點(diǎn)開(kāi)始，按層次逐層遍歷，如圖：遍歷順序abcdef--+/*層次序遍歷二叉樹(shù)的算法4747這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪(fǎng)問(wèn)它們。算法是非遞歸的。4848abcdeQaa

進(jìn)隊(duì)Qa出隊(duì),訪(fǎng)問(wèn)ab進(jìn)隊(duì),c

進(jìn)隊(duì)bcQb出隊(duì),訪(fǎng)問(wèn)bd

進(jìn)隊(duì)cdQc出隊(duì),訪(fǎng)問(wèn)ce

進(jìn)隊(duì)deQd出隊(duì),訪(fǎng)問(wèn)deQe出隊(duì),訪(fǎng)問(wèn)eP205Bug4949層次序遍歷的（非遞歸）算法voidBinaryTree::levelOrder(){if(root==NULL)return;SeqQueue

Q;

BinTreeNode*p=root; Q.EnQueue(p);

while(!Q.IsEmpty()){Q.DeQueue(p);cout<<p->data;if(p->leftChild!=NULL){Q.EnQueue(p->leftChild);}

if(p->rightChild!=NULL){ Q.EnQueue(p->rightChild);}}};5050有0個(gè),1個(gè),2個(gè),3個(gè),4個(gè)結(jié)點(diǎn)的不同二叉樹(shù)如下b0=1b1=1b2=2b3=5

b4=145.4.4二叉樹(shù)的計(jì)數(shù)5151計(jì)算具有n個(gè)結(jié)點(diǎn)的不同二叉樹(shù)的棵數(shù)Catalan函數(shù)bibn-i-115252例如,有3個(gè)數(shù)據(jù){1,2,3

}，可得5種不同的二叉樹(shù)。它們的前序排列均為

123，中序序列可能是321，231，213，132，123。

問(wèn)題：前序序列為123，中序序列為

312

的二叉樹(shù)存在嗎？1231231231231235353思考：由二叉樹(shù)的前序序列和中序序列可唯一地確定一棵二叉樹(shù)嗎？試：前序序列{ABHFDECKG}

中序序列{HBDFAEKCG

}

構(gòu)造一棵二叉樹(shù)HBDFEKCGAEKCGABHDF5454前序序列{ABHFDECKG}

中序序列{HBDFAEKCG

}EKCGABHDFEKCGABHFDKCGEABHFDEABHFDCKG55555.5線(xiàn)索化二叉樹(shù)

(ThreadedBinaryTree)又稱(chēng)為穿線(xiàn)樹(shù)。通過(guò)二叉樹(shù)的遍歷，可將二叉樹(shù)中所有結(jié)點(diǎn)的數(shù)據(jù)排列在一個(gè)線(xiàn)性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。希望不必每次都通過(guò)遍歷找出這樣的線(xiàn)性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼關(guān)系記在樹(shù)的存儲(chǔ)結(jié)構(gòu)中，以后就可以高效地找出某結(jié)點(diǎn)的前驅(qū)、后繼。5656線(xiàn)索(Thread)bdaec增加前驅(qū)Pred指針和后繼Succ指針的二叉樹(shù)predleftChilddatarightChildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc5757缺點(diǎn)：每個(gè)結(jié)點(diǎn)增加兩個(gè)指針，當(dāng)結(jié)點(diǎn)數(shù)很大時(shí)存儲(chǔ)消耗較大。改造樹(shù)結(jié)點(diǎn)，將pred指針和succ指針壓縮到leftChild和rightChild的空閑指針中，并增設(shè)兩個(gè)標(biāo)志ltag和rtag，指明指針是指示子女還是前驅(qū)／后繼。后者稱(chēng)為線(xiàn)索。ltag(或rtag)=0，表示相應(yīng)指針指示左子女（或右子女結(jié)點(diǎn)）；當(dāng)ltag(或rtag)=1,表示相應(yīng)指針為前驅(qū)（或后繼）線(xiàn)索。leftChildltagdatartagrightChild

5858leftChildltagdatartagrightChild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111線(xiàn)索化二叉樹(shù)及其鏈表表示bdaec5959if(current->rtag==1)

后繼為current->rightChildelse//current->rtag==0

后繼為當(dāng)前結(jié)點(diǎn)右子樹(shù)的中序下的第一個(gè)結(jié)點(diǎn)

尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼ABDECFHIKGJ6060尋找當(dāng)前結(jié)點(diǎn)在中序

下的前驅(qū)if(current->ltag==1)

前驅(qū)為current->leftChildelse//current->ltag==0

前驅(qū)為當(dāng)前結(jié)點(diǎn)左子樹(shù)

中序下的最后一個(gè)結(jié)點(diǎn)

ABDECFHIKGJL61615.6.1樹(shù)的存儲(chǔ)表示5.6樹(shù)與森林ABCDEFGdataparentABCDEFG-100011301234561.雙親表示：找雙親容易

樹(shù)中結(jié)點(diǎn)的存放順序一般不做特殊要求，但為了操作實(shí)現(xiàn)的方便，有時(shí)也會(huì)規(guī)定結(jié)點(diǎn)的存放順序。例如，可以規(guī)定按樹(shù)的前序次序存放樹(shù)中的各個(gè)結(jié)點(diǎn)，或規(guī)定按樹(shù)的層次次序安排所有結(jié)點(diǎn)。

62622.子女(孩子)鏈表表示：找孩子容易無(wú)序樹(shù)情形鏈表中各結(jié)點(diǎn)順序任意，有序樹(shù)必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG012345663633.孩子-兄弟表示法：找孩子容易也稱(chēng)為樹(shù)的二叉樹(shù)表示。結(jié)點(diǎn)構(gòu)造為：firstChild指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無(wú)序樹(shù)時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。nextSibling指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在存儲(chǔ)時(shí)總是有順序的。若想找某結(jié)點(diǎn)的所有子女，可先找firstChild,再反復(fù)用nextSibling沿鏈掃描。

datafirstChildnextSibling6464樹(shù)的子女-

兄弟表示

datafirstChildnextSiblingABCDEFGABCDGFE6565樹(shù)的二叉樹(shù)表示5.7樹(shù)的遍歷①深度優(yōu)先遍歷先根次序遍歷后根次序遍歷②廣度優(yōu)先遍歷ABCDEFGABCEDGF6666ABCEDGF樹(shù)的先根次序遍歷當(dāng)樹(shù)非空時(shí)訪(fǎng)問(wèn)根結(jié)點(diǎn)依次先根遍歷根的各棵子樹(shù)樹(shù)先根遍歷：對(duì)應(yīng)二叉樹(shù)前序遍歷：樹(shù)的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示的前序遍歷結(jié)果相同樹(shù)的先根遍歷可以借助對(duì)應(yīng)二叉樹(shù)的前序遍歷算法實(shí)現(xiàn)ABCDEFGABEFCDGABEFCDG6767ABCEDGF樹(shù)的后根次序遍歷當(dāng)樹(shù)非空時(shí)

依次后根遍歷根的各棵子樹(shù)訪(fǎng)問(wèn)根結(jié)點(diǎn)樹(shù)后根遍歷：對(duì)應(yīng)二叉樹(shù)中序遍歷：樹(shù)的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹(shù)表示的中序遍歷結(jié)果相同樹(shù)的后根遍歷可以借助對(duì)應(yīng)二叉樹(shù)的中序遍歷算法實(shí)現(xiàn)ABCDEFGEFBCGDAEFBCGDA6868廣度優(yōu)先（層次次序）遍歷按廣度優(yōu)先次序遍歷樹(shù)的結(jié)果

ABCDEFG遍歷算法用到一個(gè)隊(duì)列。ABCEDGFABCDEFG6969

將一般樹(shù)化為二叉樹(shù)表示就是用樹(shù)的子女-兄弟表示來(lái)存儲(chǔ)樹(shù)的結(jié)構(gòu)。森林與二叉樹(shù)表示的轉(zhuǎn)換可以借助樹(shù)的二叉樹(shù)表示來(lái)實(shí)現(xiàn)。5.6.2森林與二叉樹(shù)的轉(zhuǎn)換7070T1T2T3AT1T2T3AFHBCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵樹(shù)的森林各棵樹(shù)的二叉樹(shù)表示森林的二叉樹(shù)表示1.森林轉(zhuǎn)化成二叉樹(shù)71712.二叉樹(shù)轉(zhuǎn)換為森林T1T2T3AFHBCDGIJEKABCEDHIKJFG5.7森林的遍歷森林的遍歷也分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，深度優(yōu)先遍歷又可分為先根次序遍歷和后根次序遍歷。7373森林的先根次序遍歷的結(jié)果序列:

ABCDEFGHIKJ對(duì)應(yīng)二叉樹(shù)的前序遍歷結(jié)果：ABCEDHIKJFGT1T2T3AFHBCDGIJEK7474ABCEDHIKJFG森林的后根次序遍歷的結(jié)果序列:

BCEDAGFKIJH對(duì)應(yīng)二叉樹(shù)中序遍歷的結(jié)果：T1T2T3AFHBCDGIJEK7575廣度優(yōu)先遍歷（層次序遍歷）AFHBCDGIJEK若森林F

為空，返回；否則：①依次遍歷各棵樹(shù)的根結(jié)點(diǎn)；②依次遍歷各棵樹(shù)根結(jié)點(diǎn)的所有子女；③依次遍歷這些子女結(jié)點(diǎn)的子女結(jié)點(diǎn)；

T1T2T3AFHBCDGIJEK76765.8Huffman樹(shù)路徑長(zhǎng)度(PathLength)

兩個(gè)結(jié)點(diǎn)之間的路徑長(zhǎng)度PL

是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。樹(shù)的外部路徑長(zhǎng)度是各葉結(jié)點(diǎn)（外結(jié)點(diǎn)）到根結(jié)點(diǎn)的路徑長(zhǎng)度之和EPL。樹(shù)的內(nèi)部路徑長(zhǎng)度是各非葉結(jié)點(diǎn)（內(nèi)結(jié)點(diǎn)）到根結(jié)點(diǎn)的路徑長(zhǎng)度之和IPL。樹(shù)的路徑長(zhǎng)度PL=EPL+IPL。77771122334455667788IPL=0+1+1+2=4EPL=2+2+2+3=9PL=13IPL=0+1+2+3=6EPL=1+2+3+4=10PL=167878在很多應(yīng)用問(wèn)題中為樹(shù)的葉結(jié)點(diǎn)賦予一個(gè)權(quán)值，用于表示出現(xiàn)頻度、概率值等，稱(chēng)為擴(kuò)充二叉樹(shù)。若一棵擴(kuò)充二叉樹(shù)有n個(gè)外結(jié)點(diǎn)，第i個(gè)外結(jié)點(diǎn)的權(quán)值為wi，它到根的路徑長(zhǎng)度為li，則該外結(jié)點(diǎn)到根的帶權(quán)路徑長(zhǎng)度為wi*li。擴(kuò)充二叉樹(shù)的帶權(quán)路徑長(zhǎng)度定義為樹(shù)的各外結(jié)點(diǎn)到根的帶權(quán)路徑長(zhǎng)度之和。2457帶權(quán)路徑長(zhǎng)度

(WeightedPathLength,WPL)7979具