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

數(shù)據(jù)結(jié)構(gòu)王向文1325300350@西北師范大學(xué)第五章樹和二叉樹1樹的基本概念2二叉樹3遍歷二叉樹4二叉搜索樹5樹與森林6Huffman樹1樹的基本概念樹的定義樹的基本術(shù)語1.1樹的定義樹(Tree)是n(n≧0)個(gè)結(jié)點(diǎn)的有限集合T，若n=0時(shí)稱為空樹，否則：⑴有且只有一個(gè)特殊的稱為樹的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分為m(m>0)個(gè)互不相交的子集T1,T2,T3…Tm，其中每個(gè)子集本身又是一棵樹，稱其為根的子樹(Subtree)。1.1樹的定義AABDCEGFHIMJNKL(a)

只有根結(jié)點(diǎn)(b)

一般的樹1.2樹的基本術(shù)語⑴結(jié)點(diǎn)(node)：一個(gè)數(shù)據(jù)元素及其若干指向其子樹的分支。⑵結(jié)點(diǎn)的度(degree)、樹的度：結(jié)點(diǎn)所擁有的子樹的棵數(shù)稱為結(jié)點(diǎn)的度。樹中結(jié)點(diǎn)度的最大值稱為樹的度。⑶葉子(left)結(jié)點(diǎn)、非葉子結(jié)點(diǎn)：樹中度為0的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)(或終端結(jié)點(diǎn))。相對(duì)應(yīng)地，度不為0的結(jié)點(diǎn)稱為非葉子結(jié)點(diǎn)(或非終端結(jié)點(diǎn)或分支結(jié)點(diǎn))。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)又稱為內(nèi)部結(jié)點(diǎn)。1.2樹的基本術(shù)語⑷孩子結(jié)點(diǎn)、雙親結(jié)點(diǎn)、兄弟結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子結(jié)點(diǎn)(child)或子結(jié)點(diǎn)；相應(yīng)地，該結(jié)點(diǎn)是其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)(parent)或父結(jié)點(diǎn)。⑸層次、堂兄弟結(jié)點(diǎn)：規(guī)定樹中根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次等于其雙親結(jié)點(diǎn)的層次加1。

若某結(jié)點(diǎn)在第l(l≧1)層，則其子結(jié)點(diǎn)在第l+1層。雙親結(jié)點(diǎn)在同一層上的所有結(jié)點(diǎn)互稱為堂兄弟結(jié)點(diǎn)。1.2樹的基本術(shù)語⑹結(jié)點(diǎn)的層次路徑、祖先、子孫：從根結(jié)點(diǎn)開始，到達(dá)某結(jié)點(diǎn)p所經(jīng)過的所有結(jié)點(diǎn)成為結(jié)點(diǎn)p的層次路徑(有且只有一條)。結(jié)點(diǎn)p的層次路徑上的所有結(jié)點(diǎn)（p除外）稱為p的祖先(ancester)。以某一結(jié)點(diǎn)為根的子樹中的任意結(jié)點(diǎn)稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)(descent)。⑺樹的深度(depth)：樹中結(jié)點(diǎn)的最大層次值，又稱為樹的高度。1.2樹的基本術(shù)語⑻有序樹和無序樹：對(duì)于一棵樹，若其中每一個(gè)結(jié)點(diǎn)的子樹（若有）具有一定的次序，則該樹稱為有序樹，否則稱為無序樹。⑼森林(forest)：是m(m≧0)棵互不相交的樹的集合。顯然，若將一棵樹的根結(jié)點(diǎn)刪除，剩余的子樹就構(gòu)成了森林。1.3樹的抽象數(shù)據(jù)類型定義ADTTree{數(shù)據(jù)對(duì)象D：D是具有相同數(shù)據(jù)類型的數(shù)據(jù)元素的集合。數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹；

……基本操作：……}ADTTree2二叉樹二叉樹的定義二叉樹的基本形態(tài)二叉樹的性質(zhì)二叉樹的存儲(chǔ)結(jié)構(gòu)2.1二叉樹的定義二叉樹(Binarytree)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合。若n=0時(shí)稱為空樹，否則：⑴有且只有一個(gè)特殊的稱為樹的根(Root)結(jié)點(diǎn)；⑵若n>1時(shí)，其余的結(jié)點(diǎn)被分成為二個(gè)互不相交的子集T1,T2，分別稱之為左、右子樹，并且左、右子樹又都是二叉樹。2.2二叉樹的基本形態(tài)AAAA(a)(b)(c)(d)(e)(a)空二叉樹(b)單結(jié)點(diǎn)二叉樹(c)右子樹為空(d)左子樹為空(e)左、右子樹都不空二叉樹的基本形態(tài)2.3二叉樹的性質(zhì)性質(zhì)1：在非空二叉樹中，第i層上至多有2i-1個(gè)結(jié)點(diǎn)(i≧1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)（k≧1)。性質(zhì)3：對(duì)任何一棵二叉樹，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。2.3二叉樹的性質(zhì)滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二叉樹稱為滿二叉樹(FullBinaryTree)。滿二叉樹的特點(diǎn)：基本特點(diǎn)是每一層上的結(jié)點(diǎn)數(shù)總是最大結(jié)點(diǎn)數(shù)。滿二叉樹的所有的支結(jié)點(diǎn)都有左、右子樹?？蓪?duì)滿二叉樹的結(jié)點(diǎn)進(jìn)行連續(xù)編號(hào)，若規(guī)定從根結(jié)點(diǎn)開始，按“自上而下、自左至右”的原則進(jìn)行。2.3二叉樹的性質(zhì)完全二叉樹(CompleteBinaryTree)：如果深度為k，由n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1到n的結(jié)點(diǎn)一一對(duì)應(yīng)，該二叉樹稱為完全二叉樹?；蛏疃葹閗的滿二叉樹中編號(hào)從1到n的前n個(gè)結(jié)點(diǎn)構(gòu)成了一棵深度為k的完全二叉樹。

其中2k-1≦

n≦2k-1。完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。2.3二叉樹的性質(zhì)完全二叉樹的特點(diǎn)：

若完全二叉樹的深度為k，則所有的葉子結(jié)點(diǎn)都出現(xiàn)在第k層或k-1層。對(duì)于任一結(jié)點(diǎn)，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l+1。894101151213614157213894101152112673(a)滿二叉樹(b)完全二叉樹1362455674213(c)非完全二叉樹特殊形態(tài)的二叉樹2.3二叉樹的性質(zhì)性質(zhì)4：n個(gè)結(jié)點(diǎn)的完全二叉樹深度為：㏒2n

+1。其中符號(hào)：x表示不小于x的最小

整數(shù)。x

表示不大于x的最大整數(shù)。2.3二叉樹的性質(zhì)性質(zhì)5：若對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(深度為

㏒2n

+1)的結(jié)點(diǎn)按層（從第1層到第㏒2n

+1層)序自左至右進(jìn)行編號(hào),則對(duì)于編號(hào)為i（1≦i≦n)的結(jié)點(diǎn)：⑴若i=1：則結(jié)點(diǎn)i是二叉樹的根，無雙親結(jié)點(diǎn)；否則，若i>1，則其雙親結(jié)點(diǎn)編號(hào)是

i/2

。⑵如果2i>n：則結(jié)點(diǎn)i為葉子結(jié)點(diǎn)，無左孩子；否則，其左孩子結(jié)點(diǎn)編號(hào)是2i。⑶如果2i+1>n：則結(jié)點(diǎn)i無右孩子；否則，其右孩子結(jié)點(diǎn)編號(hào)是2i+1。性質(zhì)6：給定N個(gè)節(jié)點(diǎn)，能構(gòu)成CN種不同的二叉樹，其中為卡塔蘭數(shù)（Catalan）。2.4二叉樹的存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)：用一組地址連續(xù)的存儲(chǔ)單元依次“自上而下、自左至右”存儲(chǔ)完全二叉樹的數(shù)據(jù)元素。對(duì)于完全二叉樹上編號(hào)為i的結(jié)點(diǎn)元素存儲(chǔ)在一維數(shù)組的下標(biāo)值為i-1的分量中。對(duì)于一般的二叉樹，將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的結(jié)點(diǎn)相對(duì)照，存儲(chǔ)在一維數(shù)組中。最壞的情況下，一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的單支樹需要長(zhǎng)度為2k-1的一維數(shù)組。abcdhiejklfg(a)完全二叉樹(b)非完全二叉樹abcdefgh???123456789101112

abcdefghijkl

(c)完全二叉樹的順序存儲(chǔ)形式1234567891011abcde?h?

?

fg(d)非完全二叉樹的順序存儲(chǔ)形式2.4二叉樹的存儲(chǔ)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：二叉鏈表結(jié)點(diǎn)。有三個(gè)域：一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)點(diǎn)的指針域。三叉鏈表結(jié)點(diǎn)。除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來指向結(jié)點(diǎn)的父結(jié)點(diǎn)。LchilddataRchildLchilddataparentRchild(a)二叉鏈表結(jié)點(diǎn)(b)三叉鏈表結(jié)點(diǎn)鏈表結(jié)點(diǎn)結(jié)構(gòu)形式2.4二叉樹的存儲(chǔ)結(jié)構(gòu)(a)二叉樹afedcbg(c)三叉鏈表

a?

?

b?

c?

d?

e?

f??

g?T(b)二叉鏈表

a?

b?c?

d?e?g??f?T3遍歷二叉樹遍歷二叉樹(TraversingBinaryTree)：是指按指定的規(guī)律對(duì)二叉樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。先(根)序遍歷中(根)序遍歷后(根)序遍歷3.1先序遍歷二叉樹若二叉樹為空，則遍歷結(jié)束；否則⑴訪問根結(jié)點(diǎn)；⑵先序遍歷左子樹(遞歸調(diào)用本算法)；⑶先序遍歷右子樹(遞歸調(diào)用本算法)。3.1先序遍歷二叉樹voidPreorderTraverse(BTNode*T){if(T!=NULL){visit(T->data);/*訪問根結(jié)點(diǎn)*/PreorderTraverse(T->Lchild);PreorderTraverse(T->Rchild);}}3.2中序遍歷二叉樹若二叉樹為空，則遍歷結(jié)束；否則⑴中序遍歷左子樹(遞歸調(diào)用本算法)；⑵訪問根結(jié)點(diǎn)；⑶中序遍歷右子樹(遞歸調(diào)用本算法)。3.2中序遍歷二叉樹voidInorderTraverse(BTNode*T){if(T!=NULL){InorderTraverse(T->Lchild);visit(T->data);/*訪問根結(jié)點(diǎn)*/InorderTraverse(T->Rchild);}}3.3后序遍歷二叉樹若二叉樹為空，則遍歷結(jié)束；否則⑴后序遍歷左子樹(遞歸調(diào)用本算法)；⑵后序遍歷右子樹(遞歸調(diào)用本算法)；⑶訪問根結(jié)點(diǎn)。3.3后序遍歷二叉樹voidPostorderTraverse(BTNode*T){if(T!=NULL){PostorderTraverse(T->Lchild);PostorderTraverse(T->Rchild);visit(T->data);/*訪問根結(jié)點(diǎn)*/}}3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹二叉樹遍歷的結(jié)果是將一個(gè)非線性結(jié)構(gòu)中的數(shù)據(jù)通過訪問排列到一個(gè)線性序列中。前序序列：abdce特點(diǎn)是第一個(gè)訪問的a一定是樹根，只要左子樹非空，后面緊跟的b一定是根的左子女，…中序序列：bdaec特點(diǎn)是樹根a把整個(gè)中序分成兩部分，a左側(cè)子序列是根的左子樹上的結(jié)點(diǎn)數(shù)據(jù)，右側(cè)子序列是根的右子樹上的結(jié)點(diǎn)數(shù)據(jù)。abcde3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：HBDFEKCGAEKCGABHDF3.4根據(jù)遍歷結(jié)果構(gòu)建二叉樹KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKG3.5層次遍歷二叉樹層次遍歷二叉樹，是從根結(jié)點(diǎn)開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點(diǎn)。這種遍歷需要使用一個(gè)先進(jìn)先出的隊(duì)列，在處理上一層時(shí)，將其下一層的結(jié)點(diǎn)直接進(jìn)到隊(duì)列（的隊(duì)尾）。在上一層結(jié)點(diǎn)遍歷完后，下一層結(jié)點(diǎn)正好處于隊(duì)列的隊(duì)頭，可以繼續(xù)訪問它們。4二叉搜索樹二叉排序樹（BinarySortTree）又稱二叉查找樹（BinarySearchTree），亦稱二叉搜索樹。二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：（1）若左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；（2）若右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；（3）左、右子樹也分別為二叉排序樹；（4）沒有鍵值相等的節(jié)點(diǎn)。4.1二叉搜索樹的查找若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查左子樹。若大于根結(jié)點(diǎn)的關(guān)鍵字值，遞歸查右子樹。若子樹為空，查找不成功。4.2二叉搜索樹的插入在插入之前，先使用搜索算法在樹中檢查要插入元素有還是沒有。如果搜索成功，說明樹中已經(jīng)有這個(gè)元素，不再插入；如果搜索不成功，說明樹中原來沒有關(guān)鍵碼等于給定值的結(jié)點(diǎn)，把新元素加到搜索操作停止的地方。輸入數(shù)據(jù)

{53,78,65,17,87,09,81,15}4.3二叉搜索樹的刪除刪除葉結(jié)點(diǎn)，只需將其雙親結(jié)點(diǎn)指向它的指針清零，再釋放它即可。被刪結(jié)點(diǎn)右子樹為空，可以拿它的左子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左子樹為空，可以拿它的右子女結(jié)點(diǎn)頂替它的位置，再釋放它。被刪結(jié)點(diǎn)左、右子樹都不為空，可以在它的右子樹中尋找中序下的第一個(gè)結(jié)點(diǎn)(關(guān)鍵碼最小),用它的值填補(bǔ)到被刪結(jié)點(diǎn)中，再來處理這個(gè)結(jié)點(diǎn)的刪除問題。4.3二叉搜索樹的刪除被刪結(jié)點(diǎn)右子樹為空：4.3二叉搜索樹的刪除被刪結(jié)點(diǎn)左子樹為空：4.3二叉搜索樹的刪除被刪結(jié)點(diǎn)左、右子樹都不為空：5樹與森林樹的存儲(chǔ)結(jié)構(gòu)樹與二叉樹的轉(zhuǎn)換5.1樹的存儲(chǔ)結(jié)構(gòu)以二叉鏈表作為樹的存儲(chǔ)結(jié)構(gòu)兩個(gè)指針域：分別指向結(jié)點(diǎn)的第一個(gè)子結(jié)點(diǎn)和下一個(gè)兄弟結(jié)點(diǎn)。結(jié)點(diǎn)類型定義如下：typedefstructCSnode{ElemTypedata;structCSnode*firstchild,*nextsibing;}CSNode;樹及孩子兄弟存儲(chǔ)結(jié)構(gòu)(b)樹

FGRABCDE(c)孩子兄弟存儲(chǔ)結(jié)構(gòu)

R?

A?D

C??G?B?F??E?孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchilddatanextsibing(a)結(jié)點(diǎn)結(jié)構(gòu)5.2樹與二叉樹的轉(zhuǎn)換由于二叉樹和樹都可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，對(duì)比各自的結(jié)點(diǎn)結(jié)構(gòu)可以看出，以二叉鏈表作為媒介可以導(dǎo)出樹和二叉樹之間的一個(gè)對(duì)應(yīng)關(guān)系。從物理結(jié)構(gòu)來看，樹和二叉樹的二叉鏈表是相同的，只是對(duì)指針的邏輯解釋不同而已。從樹的二叉鏈表表示的定義可知，任何一棵和樹對(duì)應(yīng)的二叉樹，其右子樹一定為空。樹與二叉樹的對(duì)應(yīng)關(guān)系二叉樹

CERADB

R?

A?D??C?

B?E?樹

RABCDE對(duì)應(yīng)關(guān)系

R?

A?D??C?

B?E??C?

B?E?

R

A?D?存儲(chǔ)解釋存儲(chǔ)解釋5.2樹與二叉樹的轉(zhuǎn)換樹轉(zhuǎn)換成二叉樹：⑴加虛線。在樹的每層按從“左至右”的順序在兄弟結(jié)點(diǎn)之間加虛線相連。⑵去連線。除最左的第一個(gè)子結(jié)點(diǎn)外，父結(jié)點(diǎn)與所有其它子結(jié)點(diǎn)的連線都去掉。⑶旋轉(zhuǎn)。將樹順時(shí)針旋轉(zhuǎn)450，原有的實(shí)線左斜。⑷整型。將旋轉(zhuǎn)后樹中的所有虛線改為實(shí)線，并向右斜。5.2樹與二叉樹的轉(zhuǎn)換樹向二叉樹的轉(zhuǎn)換過程(a)一般的樹

FGRABCDEFGRABCDE(b)加虛線，去連線后

(C)轉(zhuǎn)換后的二叉樹FGRACDBE5.2樹與二叉樹的轉(zhuǎn)換轉(zhuǎn)換后的二叉樹的特點(diǎn)是：

二叉樹的根結(jié)點(diǎn)沒有右子樹，只有左子樹；

左子結(jié)點(diǎn)仍然是原來樹中相應(yīng)結(jié)點(diǎn)的左子結(jié)點(diǎn)，而所有沿右鏈往下的右子結(jié)點(diǎn)均是原來樹中該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)。5.2樹與二叉樹的轉(zhuǎn)換二叉樹轉(zhuǎn)換成樹：⑴加虛線。若某結(jié)點(diǎn)i是其父結(jié)點(diǎn)的左子樹的根結(jié)點(diǎn)，則將該結(jié)點(diǎn)i的右子結(jié)點(diǎn)以及沿右子鏈不斷地搜索所有的右子結(jié)點(diǎn)，將所有這些右子結(jié)點(diǎn)與i結(jié)點(diǎn)的父結(jié)點(diǎn)之間加虛線相連。⑵去連線。去掉二叉樹中所有父結(jié)點(diǎn)與其右子結(jié)點(diǎn)之間的連線。⑶規(guī)整化。將圖中各結(jié)點(diǎn)按層次排列且將所有的虛線變成實(shí)線。5.2樹與二叉樹的轉(zhuǎn)換二叉樹向樹的轉(zhuǎn)換過程(C)還原后的樹FGRABCDE(b)去連線后(a)加虛線后FGRACDBECFGRADBE5.3二叉樹與森林的轉(zhuǎn)換森林轉(zhuǎn)換成二叉樹：(1)將F={T1,T2,?,Tn}中的每棵樹轉(zhuǎn)換成二叉樹。(2)按給出的森林中樹的次序，從最后一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的根結(jié)點(diǎn)的右子樹，依次類推，則第一棵樹的根結(jié)點(diǎn)就是轉(zhuǎn)換后生成的二叉樹的根結(jié)點(diǎn)。5.3二叉樹與森林的轉(zhuǎn)換ACBDGMLHK(a)森林森林轉(zhuǎn)換成二叉樹的過程(b)森林中每棵樹對(duì)應(yīng)的二叉樹ABCDGLKHM(c)森林對(duì)應(yīng)的二叉樹ABCDGLKHM5.3二叉樹與森林的轉(zhuǎn)換二叉樹轉(zhuǎn)換成森林：(1)去連線。將二叉樹B的根結(jié)點(diǎn)與其右子結(jié)點(diǎn)以及沿右子結(jié)點(diǎn)鏈方向的所有右子結(jié)點(diǎn)的連線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來森林F中的樹依次對(duì)應(yīng)的二叉樹。(2)二叉樹的還原。將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹。5.3二叉樹與森林的轉(zhuǎn)換二叉樹還原成森林的過程ACBDMGLHK(c)還原成森林(a)二叉樹ABCDGLKHM(b)去連線后ABCDMGLKH5.4樹與森林的遍歷樹的遍歷：先序遍歷：先訪問根結(jié)點(diǎn)，然后依次先序遍歷完每棵子樹。后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結(jié)點(diǎn)。樹的先序遍歷實(shí)質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對(duì)二叉樹的先序遍歷相同。樹的后序遍歷實(shí)質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對(duì)二叉樹的中序遍歷相同。5.4樹與森林的遍歷先序遍歷的次序是：ABCDEFGIJHK后序遍歷的次序是：CDBFGIJHEKAABDCKGJIFHE5.4樹與森林的遍歷森林的遍歷：先序遍歷：按先序遍歷樹的方式依次遍歷森林中的每棵樹。中序遍歷：按后序遍歷樹的方式依次遍歷森林中的每棵樹。6Huffman樹基本概念Huffman樹的構(gòu)造6.1基本概念結(jié)點(diǎn)路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。路徑長(zhǎng)度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長(zhǎng)度。樹的路徑長(zhǎng)度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：從該結(jié)點(diǎn)的到樹的根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)的權(quán)(值)的乘積。6.1基本概念