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

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

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

①自由樹： 一棵自由樹Tf

可定義為一個二元組

Tf

=(V,E)

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

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

V,1≤i,j≤n}

是n-1個序?qū)Φ募?，稱為邊集合，E

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

個結(jié)點的有限集合。當(dāng)n=0時，T稱為空樹；否則，T

是非空樹，記作

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

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

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

{c},

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

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

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

若二叉樹結(jié)點的層次從1開始,則在二叉樹的第i層最多有

2i-1

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

深度為k

的二叉樹最少有k

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

20+21+22+…+2k-1=2k-1問：第i層上至少有

個結(jié)點？11313性質(zhì)3:

對任何一棵二叉樹，如果其葉結(jié)點有n0個,度為2的非葉結(jié)點有n2個,則有

n0＝n2＋1

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

n=n0+n1+n2

e

=2n2+n1=

n-1

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

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

滿二叉樹(FullBinaryTree)

定義2:

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

具有n(n≥0)個結(jié)點的完全二叉樹的深度為

log2(n+1)

。

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

2k-1-1<n

≤2k-1

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

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

log2(n+1)

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

個葉子結(jié)點，有

個度為2的結(jié)點，有

個結(jié)點只有非空左子樹，有

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

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

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

二叉樹的鏈?zhǔn)酱鎯Ρ硎?.3.1二叉樹的順序存儲表示20205.3.1二叉樹的順序表示完全二叉樹的順序表示1123456789

10

24891056731412346789

12

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

AABBCCDDFFEErootroot

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

-11-1B

023C

1

-1-1D

145E

3-1-1F

3-1-12626二叉樹的類定義#include<iostream.h>classBinaryTree;classBinTreeNode{

//結(jié)點類的定義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();//不需要遞歸，所以直接對外接口調(diào)用即可。層序遍歷

2929private:BinTreeNode*root;//二叉樹的根指針 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二叉樹遍歷二叉樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問且僅訪問一次。設(shè)訪問根結(jié)點記作

V

遍歷根的左子樹記作

L

遍歷根的右子樹記作

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

前序VLR

中序

LVR

后序LRV

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

a+b*c

-

d

-

e/f5.4.1二叉樹遍歷的遞歸算法

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

-+a*b

-

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

abcd

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

voidBinaryTree::inOrder(BinTreeNode*subTree){

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

voidBinaryTree::PreOrder(BinTreeNode*subTree){

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

voidBinaryTree::PostOrder(BinTreeNode*subTree){

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

subTree開始,搜索結(jié)點

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

subTree->rightChild==current)

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

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

current); };//改錯找雙親節(jié)點4141

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

if(subTree!=NULL){

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

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

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

}};4242

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

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

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

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

BinTreeNode

*p=root;

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

cout<<p->data; //訪問結(jié)點

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

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

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

進(jìn)隊Qa出隊,訪問ab進(jìn)隊,c

進(jìn)隊bcQb出隊,訪問bd

進(jìn)隊cdQc出隊,訪問ce

進(jìn)隊deQd出隊,訪問deQe出隊,訪問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個,1個,2個,3個,4個結(jié)點的不同二叉樹如下b0=1b1=1b2=2b3=5

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

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

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

問題：前序序列為123，中序序列為

312

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

中序序列{HBDFAEKCG

}

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

中序序列{HBDFAEKCG

}EKCGABHDFEKCGABHFDKCGEABHFDEABHFDCKG55555.5線索化二叉樹

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

5858leftChildltagdatartagrightChild

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

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

后繼為當(dāng)前結(jié)點右子樹的中序下的第一個結(jié)點

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

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

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

前驅(qū)為當(dāng)前結(jié)點左子樹

中序下的最后一個結(jié)點

ABDECFHIKGJL61615.6.1樹的存儲表示5.6樹與森林ABCDEFGdataparentABCDEFG-100011301234561.雙親表示：找雙親容易

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

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

datafirstChildnextSibling6464樹的子女-

兄弟表示

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

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

ABCDEFG遍歷算法用到一個隊列。ABCEDGFABCDEFG6969

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

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

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

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

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

T1T2T3AFHBCDGIJEK76765.8Huffman樹路徑長度(PathLength)

兩個結(jié)點之間的路徑長度PL

是連接兩結(jié)點的路徑上的分支數(shù)。樹的外部路徑長度是各葉結(jié)點（外結(jié)點）到根結(jié)點的路徑長度之和EPL。樹的內(nèi)部路徑長度是各非葉結(jié)點（內(nèi)結(jié)點）到根結(jié)點的路徑長度之和IPL。樹的路徑長度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)用問題中為樹的葉結(jié)點賦予一個權(quán)值，用于表示出現(xiàn)頻度、概率值等，稱為擴充二叉樹。若一棵擴充二叉樹有n個外結(jié)點，第i個外結(jié)點的權(quán)值為wi，它到根的路徑長度為li，則該外結(jié)點到根的帶權(quán)路徑長度為wi*li。擴充二叉樹的帶權(quán)路徑長度定義為樹的各外結(jié)點到根的帶權(quán)路徑長度之和。2457帶權(quán)路徑長度

(WeightedPathLength,WPL)7979具