課件5 數(shù)據(jù)結(jié)構(gòu)-樹

,樹,樹,1樹的定義樹(Tree)是n(n0)個結(jié)點的有限集合T，若n=0時稱為空樹，否則：（1）有且只有一個特殊的稱為樹的根(Root)結(jié)點；（2）若n1時，其余的結(jié)點被分為m(m0)個互不相交的子集T1,T2,T3Tm，其中每個子集本身又是一棵樹，稱其為根的子樹(Subtree)。這是樹的遞歸定義，即用樹來定義樹，而只有一個結(jié)點的樹必定僅由根組成，如圖6-1(a)所示。樹作為一種邏輯結(jié)構(gòu)，同時也是一種分層結(jié)構(gòu)，具有兩個特點：（1）樹的根結(jié)點沒有前驅(qū)結(jié)點，除根結(jié)點外的所有結(jié)點有且只有一個前驅(qū)結(jié)點。（2）樹中所以結(jié)點可以有零個或多個后繼結(jié)點。樹適合于表達具有層次結(jié)構(gòu)的數(shù)據(jù)。,樹,2樹的基本術(shù)語結(jié)點(node)：一個數(shù)據(jù)元素及其若干指向其子樹的分支。結(jié)點的度(degree)、樹的度：結(jié)點所擁有的子樹的棵數(shù)稱為結(jié)點的度。樹中結(jié)點度的最大值稱為樹的度。,如圖6-1(b)中結(jié)點A的度是3，結(jié)點B的度是2，結(jié)點M的度是0，樹的度是3。,樹,葉子(left)結(jié)點、非葉子結(jié)點：樹中度為0的結(jié)點稱為葉子結(jié)點(或終端結(jié)點)。相對應(yīng)地，度不為0的結(jié)點稱為非葉子結(jié)點(或非終端結(jié)點或分支結(jié)點)。除根結(jié)點外，分支結(jié)點又稱為內(nèi)部結(jié)點。如圖6-1(b)中結(jié)點H、I、J、K、L、M、N是葉子結(jié)點，而所有其它結(jié)點都是分支結(jié)點。,樹,孩子結(jié)點、雙親結(jié)點、兄弟結(jié)點一個結(jié)點的子樹的根稱為該結(jié)點的孩子結(jié)點(child)或子結(jié)點；相應(yīng)地，該結(jié)點是其孩子結(jié)點的雙親結(jié)點(parent)或父結(jié)點。如圖6-1(b)中結(jié)點B、C、D是結(jié)點A的子結(jié)點，而結(jié)點A是結(jié)點B、C、D的父結(jié)點；類似地結(jié)點E、F是結(jié)點B的子結(jié)點，結(jié)點B是結(jié)點E、F的父結(jié)點。同一雙親結(jié)點的所有子結(jié)點互稱為兄弟結(jié)點。如圖6-1(b)中結(jié)點B、C、D是兄弟結(jié)點；結(jié)點E、F是兄弟結(jié)點。,樹,層次、堂兄弟結(jié)點規(guī)定樹中根結(jié)點的層次為1，其余結(jié)點的層次等于其雙親結(jié)點的層次加1。若某結(jié)點在第l(l1)層，則其子結(jié)點在第l+1層。雙親結(jié)點在同一層上的所有結(jié)點互稱為堂兄弟結(jié)點。如圖6-1(b)中結(jié)點E、F、G、H、I、J。結(jié)點的層次路徑、祖先、子孫從根結(jié)點開始，到達某結(jié)點p所經(jīng)過的所有結(jié)點成為結(jié)點p的層次路徑(有且只有一條)。結(jié)點p的層次路徑上的所有結(jié)點（p除外）稱為p的祖先(ancester)。以某一結(jié)點為根的子樹中的任意結(jié)點稱為該結(jié)點的子孫結(jié)點(descent)。,樹,樹的深度(depth)：樹中結(jié)點的最大層次值，又稱為樹的高度，如圖6-1(b)中樹的高度為4。有序樹和無序樹：對于一棵樹，若其中每一個結(jié)點的子樹（若有）具有一定的次序，則該樹稱為有序樹，否則稱為無序樹。森林(forest)：是m(m0)棵互不相交的樹的集合。顯然，若將一棵樹的根結(jié)點刪除，剩余的子樹就構(gòu)成了森林。,結(jié)點的層次從樹根開始定義，根結(jié)點為第1層，它的子結(jié)點為第2層，以此類推。結(jié)點的深度是從根結(jié)點開始自頂向下逐層累加。結(jié)點的高度是從葉結(jié)點開始自底向上逐層累加的。,樹,3樹的表示形式倒懸樹。是最常用的表示形式，如圖6-1(b)。嵌套集合。是一些集合的集體，對于任何兩個集合，或者不相交，或者一個集合包含另一個集合。圖6-2(a)是圖6-1(b)樹的嵌套集合形式。廣義表形式。圖6-2(b)是樹的廣義表形式。,樹,樹,4樹的性質(zhì)(重點)樹中的結(jié)點數(shù)等于所有結(jié)點的度數(shù)加1。度為m的樹中第i層上至多有個結(jié)點（）。高度為h的m叉樹至多有個結(jié)點。(4)具有n個結(jié)點的m叉樹的最小高度為。式（3）的推導(dǎo)公式：,二叉樹,1二叉樹的定義二叉樹(Binarytree)是另一種樹形結(jié)構(gòu)，其特點是每個結(jié)點至多只有兩顆子樹（即二叉樹中不存在度大于2的結(jié)點），并且，二叉樹的子樹有左右之分，其次序不能隨意顛倒。二叉樹是n(n0)個結(jié)點的有限集合。若n=0時稱為空樹，否則：有且只有一個特殊的稱為樹的根(Root)結(jié)點；若n1時，其余的結(jié)點被分成為二個互不相交的子集T1,T2，分別稱之為左、右子樹，并且左、右子樹又都是二叉樹。由此可知，二叉樹的定義是遞歸的。二叉樹在樹結(jié)構(gòu)中起著非常重要的作用。因為二叉樹結(jié)構(gòu)簡單，存儲效率高，樹的操作算法相對簡單，且任何樹都很容易轉(zhuǎn)化成二叉樹結(jié)構(gòu)。上節(jié)中引入的有關(guān)樹的術(shù)語也都適用于二叉樹。,二叉樹,2二叉樹的基本形態(tài)二叉樹有5種基本形態(tài)，如圖6-3所示。,圖6-3二叉樹的基本形態(tài),二叉樹,3滿二叉樹、完全二叉樹和平衡二叉樹一棵深度為k且有2k-1個結(jié)點的二叉樹稱為滿二叉樹(FullBinaryTree)。如圖6-4(a)就是一棵深度為4的滿二叉樹。滿二叉樹的特點：基本特點是每一層上的結(jié)點數(shù)總是最大結(jié)點數(shù)。滿二叉樹的所有的支結(jié)點都有左、右子樹?？蓪M二叉樹的結(jié)點進行連續(xù)編號，若規(guī)定從根結(jié)點開始，按“自上而下、自左至右”的原則進行。,平衡二叉樹：樹上任一結(jié)點的左子樹和右子樹的深度之差不超過1,二叉樹,完全二叉樹(CompleteBinaryTree)：如果深度為k，由n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為k的滿二叉樹中編號從1到n的結(jié)點一一對應(yīng)，該二叉樹稱為完全二叉樹?；蛏疃葹閗的滿二叉樹中編號從1到n的前n個結(jié)點構(gòu)成了一棵深度為k的完全二叉樹。其中2k-1n2k-1。完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。完全二叉樹的特點（重點）：（1）若完全二叉樹的深度為k，則所有的葉子結(jié)點都出現(xiàn)在第k層或k-1層。對于任一結(jié)點，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l+1。（2）若in/2，則結(jié)點i為分支結(jié)點，否則為葉子結(jié)點（3）葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)。對于最大層次中的葉子結(jié)點，都依次排列在該層的最左邊的位置（4）如果有度為1的結(jié)點，只可能有一個，且該結(jié)點只有左孩子而無左右孩子。（5）按層序編號后，一旦出現(xiàn)某結(jié)點（其編號為i）為葉子結(jié)點或只有左孩子，則編號大于i的結(jié)點均為葉子結(jié)點。,二叉樹,二叉樹,4二叉樹的性質(zhì)（重點）性質(zhì)1：在非空二叉樹中，第i層上至多有2i-1個結(jié)點(i1)。性質(zhì)2：深度為k的二叉樹至多有2k-1個結(jié)點（k1)。性質(zhì)3：對任何一棵二叉樹，若其葉子結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1。性質(zhì)4：n個結(jié)點的完全二叉樹深度為：2n+1或。其中符號：x表示不大于x的最大整數(shù)。x表示不小于x的最小整數(shù)。,二叉樹,4二叉樹的性質(zhì)性質(zhì)5：若對一棵有n個結(jié)點的完全二叉樹(深度為2n+1)的結(jié)點按層（從第1層到第2n+1層)序自左至右進行編號,則對于編號為i（1in)的結(jié)點：若i=1：則結(jié)點i是二叉樹的根，無雙親結(jié)點；否則，若i1，則其雙親結(jié)點編號是i/2。如果2in：則結(jié)點i為葉子結(jié)點，無左孩子；否則，其左孩子結(jié)點編號是2i。如果2i+1n：則結(jié)點i無右孩子；否則，其右孩子結(jié)點編號是2i+1。,二叉樹,二叉樹,5二叉樹的存儲結(jié)構(gòu)1.順序存儲結(jié)構(gòu)依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序存儲比較合適用一組地址連續(xù)的存儲單元依次“自上而下、自左至右”存儲完全二叉樹的數(shù)據(jù)元素。對于完全二叉樹上編號為i的結(jié)點元素存儲在一維數(shù)組的下標(biāo)值為i-1的分量中，如圖6-6(c)所示。對于一般的二叉樹，將其每個結(jié)點與完全二叉樹上的結(jié)點相對照，存儲在一維數(shù)組中，如圖6-6(d)所示。最壞的情況下，一個深度為k且只有k個結(jié)點的單支樹需要長度為2k-1的一維數(shù)組。,二叉樹,二叉樹,5二叉樹的存儲結(jié)構(gòu)2.鏈?zhǔn)酱鎯Y(jié)構(gòu)設(shè)計不同的結(jié)點結(jié)構(gòu)可構(gòu)成不同的鏈?zhǔn)酱鎯Y(jié)構(gòu)。(1)結(jié)點的類型及其定義二叉鏈表結(jié)點。有三個域：一個數(shù)據(jù)域，兩個分別指向左右子結(jié)點的指針域，如圖6-7(a)所示。三叉鏈表結(jié)點。除二叉鏈表的三個域外，再增加一個指針域，用來指向結(jié)點的父結(jié)點，如圖6-7(b)所示。,二叉樹,5二叉樹的存儲結(jié)構(gòu),二叉樹,6遍歷二叉樹（重點）遍歷二叉樹(TraversingBinaryTree)：是指按指定的規(guī)律對二叉樹中的每個結(jié)點訪問一次且僅訪問一次。二叉樹的基本組成：根結(jié)點、左子樹、右子樹。若能依次遍歷這三部分，就是遍歷了二叉樹。若以L、D、R分別表示遍歷左子樹、遍歷根結(jié)點和遍歷右子樹，則有六種遍歷方案：DLR、LDR、LRD、DRL、RDL、RLD。若規(guī)定先左后右，則只有前三種情況三種情況，分別是：DLR先(根)序遍歷。LDR中(根)序遍歷。LRD后(根)序遍歷。此外，還有層序遍歷。,二叉樹,6遍歷二叉樹1.先(根)序遍歷（根左右）算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則訪問根結(jié)點；先序遍歷左子樹(遞歸調(diào)用本算法)；先序遍歷右子樹(遞歸調(diào)用本算法)。,2.中(根)序遍歷（左根右）算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則中序遍歷左子樹(遞歸調(diào)用本算法)；訪問根結(jié)點；中序遍歷右子樹(遞歸調(diào)用本算法)。,二叉樹,6遍歷二叉樹3.后(根)序遍歷（左右根）算法的遞歸定義是：若二叉樹為空，則遍歷結(jié)束；否則后序遍歷左子樹(遞歸調(diào)用本算法)；后序遍歷右子樹(遞歸調(diào)用本算法)；訪問根結(jié)點。,4.層次遍歷（需要借助一個隊列）層次遍歷二叉樹，是從根結(jié)點開始遍歷，按層次次序“自上而下，從左至右”訪問樹中的各結(jié)點。,三種遍歷的時間復(fù)雜度都為O(n),二叉樹,6遍歷二叉樹如圖6-9所示的二叉樹表示表達式：(a+b*(c-d)-e/f)按不同的次序遍歷此二叉樹，將訪問的結(jié)點按先后次序排列起來的次序是：其先序序列為：-+a*b-cd/ef其中序序列為：a+b*c-d-e/f其后序序列為：abcd-*+ef/-其層序序列為：-+/a*efb-cd,二叉樹,7線索二叉樹遍歷二叉樹是按一定的規(guī)則將樹中的結(jié)點排列成一個線性序列，即是對非線性結(jié)構(gòu)的線性化操作。如何找到遍歷過程中動態(tài)得到的每個結(jié)點的直接前驅(qū)和直接后繼(第一個和最后一個除外)?如何保存這些信息?設(shè)一棵二叉樹有n個結(jié)點，則有n-1條邊(指針連線)，而n個結(jié)點共有2n個指針域(Lchild和Rchild)，顯然有n+1個空閑指針域未用。則可以利用這些空閑的指針域來存放結(jié)點的直接前驅(qū)和直接后繼信息。對結(jié)點的指針域做如下規(guī)定：若結(jié)點有左孩子，則Lchild指向其左孩子，否則，指向其直接前驅(qū)；若結(jié)點有右孩子，則Rchild指向其右孩子，否則，指向其直接后繼；為避免混淆,對結(jié)點結(jié)構(gòu)加以改進，增加兩個標(biāo)志域，如圖6-10所示。,二叉樹,7線索二叉樹,二叉樹（真題檢測）,1.非空二叉樹的第K層的結(jié)點數(shù)最多為（）A.B.C.D.2.設(shè)某二叉樹中有2000個結(jié)點，則該二叉樹的最小高度是（）A.9B.10C.11D.123.若二叉樹有11個葉子結(jié)點，則該二叉樹中度為2的結(jié)點個數(shù)是（）A.10B.11C.12D.不確定,答案：CCA,二叉樹（真題檢測）,4.已知二叉樹如圖所示。請分別給出該二叉樹的先序遍歷、中序遍歷、后序遍歷結(jié)果。,先根序序列：ABDGEHCF中根序序列：DGBHEAFC后根序序列：GDHEBFCA,二叉樹（真題檢測）,5.（2017）已知二叉樹的前序遍歷序列為AEFBGCDHIKJ，中序遍歷序列是EFAGBCHKIJD，畫出此二叉樹，并寫出后序遍歷結(jié)果。,二叉樹（真題檢測）,6.（2018）根據(jù)所給的二叉樹，寫出四種遍歷序列（先、中、后、層），并畫出該二叉樹的中序線索二叉樹。,樹與森林,1樹的存儲結(jié)構(gòu)1.雙親表示法(順序存儲結(jié)構(gòu))用一組連續(xù)的存儲空間來存儲樹的結(jié)點，同時在每個結(jié)點中附加一個指示器(整數(shù)域)，用以指示雙親結(jié)點的位置(下標(biāo)值)。這種存儲結(jié)構(gòu)利用了任一結(jié)點的父結(jié)點唯一的性質(zhì)?？梢苑奖愕刂苯诱业饺我唤Y(jié)點的父結(jié)點，但求結(jié)點的子結(jié)點時需要掃描整個數(shù)組。,樹與森林,1樹的存儲結(jié)構(gòu)2.孩子鏈表表示法樹中每個結(jié)點有多個指針域，每個指針指向其一棵子樹的根結(jié)點。,樹與森林,1樹的存儲結(jié)構(gòu)3.孩子兄弟表示法(二叉樹表示法)以二叉鏈表作為樹的存儲結(jié)構(gòu)，其結(jié)點形式如圖6-17(a)所示。兩個指針域：分別指向結(jié)點的第一個子結(jié)點和下一個兄弟結(jié)點。,樹與森林,2森林與二叉樹的轉(zhuǎn)換1.樹轉(zhuǎn)換成二叉樹對于一般的樹，可以方便地轉(zhuǎn)換成一棵唯一的二叉樹與之對應(yīng)。其詳細步驟是：加虛線。在樹的每層按從“左至右”的順序在兄弟結(jié)點之間加虛線相連。去連線。除最左的第一個子結(jié)點外，父結(jié)點與所有其它子結(jié)點的連線都去掉。旋轉(zhuǎn)。將樹順時針旋轉(zhuǎn)450，原有的實線左斜。整型。將旋轉(zhuǎn)后樹中的所有虛線改為實線，并向右斜。該轉(zhuǎn)換過程如圖6-19所示。,樹與森林,這樣轉(zhuǎn)換后的二叉樹的特點是：二叉樹的根結(jié)點沒有右子樹，只有左子樹；左子結(jié)點仍然是原來樹中相應(yīng)結(jié)點的左子結(jié)點，而所有沿右鏈往下的右子結(jié)點均是原來樹中該結(jié)點的兄弟結(jié)點。,樹與森林,2森林與二叉樹的轉(zhuǎn)換2.二叉樹轉(zhuǎn)換成樹其步驟是：加虛線。若某結(jié)點i是其父結(jié)點的左子樹的根結(jié)點，則將該結(jié)點i的右子結(jié)點以及沿右子鏈不斷地搜索所有的右子結(jié)點，將所有這些右子結(jié)點與i結(jié)點的父結(jié)點之間加虛線相連，如圖6-20(a)所示。去連線。去掉二叉樹中所有父結(jié)點與其右子結(jié)點之間的連線，如圖6-20(b)所示。規(guī)整化。將圖中各結(jié)點按層次排列且將所有的虛線變成實線，如圖6-20(c)所示。,樹與森林,樹與森林,2森林與二叉樹的轉(zhuǎn)換3.森林轉(zhuǎn)換成二叉樹轉(zhuǎn)換步驟：將F=T1,T2,Tn中的每棵樹轉(zhuǎn)換成二叉樹。按給出的森林中樹的次序，從最后一棵二叉樹開始，每棵二叉樹作為前一棵二叉樹的根結(jié)點的右子樹，依次類推，則第一棵樹的根結(jié)點就是轉(zhuǎn)換后生成的二叉樹的根結(jié)點，如圖6-21所示。,樹與森林,2森林與二叉樹的轉(zhuǎn)換4.二叉樹轉(zhuǎn)換成森林轉(zhuǎn)換步驟：去連線。將二叉樹B的根結(jié)點與其右子結(jié)點以及沿右子結(jié)點鏈方向的所有右子結(jié)點的連線全部去掉，得到若干棵孤立的二叉樹，每一棵就是原來森林F中的樹依次對應(yīng)的二叉樹，如圖6-22(b)所示。二叉樹的還原。將各棵孤立的二叉樹按二叉樹還原為樹的方法還原成一般的樹，如圖6-22(c)所示。,樹與森林,樹與森林,3樹和森林的遍歷1.樹的遍歷由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。先序遍歷：先訪問根結(jié)點，然后依次先序遍歷完每棵子樹。如圖的樹，先序遍歷的次序是：ABCDEFGIJHK后序遍歷：先依次后序遍歷完每棵子樹，然后訪問根結(jié)點。如圖的樹，后序遍歷的次序是：CDBFGIJHEKA,說明：樹的先序遍歷實質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對二叉樹的先序遍歷相同。樹的后序遍歷實質(zhì)上與將樹轉(zhuǎn)換成二叉樹后對二叉樹的中序遍歷相同。,樹與森林,3樹和森林的遍歷2森林的遍歷設(shè)F=T1,T2,Tn是森林，對F的遍歷有二種方法。先序遍歷：按先序遍歷樹的方式依次遍歷F中的每棵樹。中序遍歷：按后序遍歷樹的方式依次遍歷F中的每棵樹。,樹的應(yīng)用,1二叉排序樹二叉排序樹，又叫二叉查找樹，它或者是一棵空樹；或者是具有以下性質(zhì)的二叉樹：1.若它的左子樹不空，則左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；2.若它的右子樹不空，則右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；3.它的左右子樹也分別為二叉排序樹。,樹的應(yīng)用,1二叉排序樹1.二叉排序樹查找要在二叉樹中找出查找最大最小元素是極簡單的事情，從根節(jié)點一直往左走，直到無路可走就可得到最小值；從根節(jié)點一直往右走，直到無路可走，就可以得到最大值。,樹的應(yīng)用,1二叉排序樹2.二叉排序樹插入插入新元素時，可以從根節(jié)點開始，遇鍵值較大者就向左，遇鍵值較小者就向右，一直到末端，就是插入點。,樹的應(yīng)用,1二叉排序樹3.二叉排序樹刪除對于二叉排序樹中的節(jié)點A，對它的刪除分為兩種情況：（1）如果A只有一個子節(jié)點，就直接將A的子節(jié)點連至A的父節(jié)點上，并將A刪除；,樹的應(yīng)用,1二叉排序樹2.二叉排序樹刪除如果A有兩個子節(jié)點，我們就以右子樹內(nèi)的最小節(jié)點取代A。,樹的應(yīng)用,2平衡二叉樹平衡二叉樹或者是空樹，或者是滿足下列性質(zhì)的二叉樹。：左子樹和右子樹深度之差的絕對值不大于1；：左子樹和右子樹也都是平衡二叉樹。平衡因子(BalanceFactor)：二叉樹上結(jié)點的左子樹的深度減去其右子樹深度稱為該結(jié)點的平衡因子。因此，平衡二叉樹上每個結(jié)點的平衡因子只可能是-1、0和1，否則，只要有一個結(jié)點的平衡因子的絕對值大于1，該二叉樹就不是平衡二叉樹。如果一棵二叉樹既是二叉排序樹又是平衡二叉樹，稱為平衡二叉排序樹(BalancedBinarySortTree)。,樹的應(yīng)用,2平衡二叉樹1.平衡化旋轉(zhuǎn)一般的二叉排序樹是不平衡的，若能通過某種方法使其既保持有序性，又具有平衡性，就找到了構(gòu)造平衡二叉排序樹的方法，該方法稱為平衡化旋轉(zhuǎn)。,樹的應(yīng)用,2平衡二叉樹1.平衡化旋轉(zhuǎn)LL型平衡化旋轉(zhuǎn)用b取代a的位置，a成為b的右子樹的根結(jié)點，b原來的右子樹作為a的左子樹。,樹的應(yīng)用,2平衡二叉樹1.平衡化旋轉(zhuǎn)LR型平衡化旋轉(zhuǎn)先以b進行一次逆時針旋轉(zhuǎn)(將以b為根的子樹旋轉(zhuǎn)為以c為根)，再以a進行一次順時針旋轉(zhuǎn)，如圖9-8所示。將整棵子樹旋轉(zhuǎn)為以c為根，b是c的左子樹，a是c的右子樹；c的右子樹移到a的左子樹位置，c的左子樹移到b的右子樹位置。,樹的應(yīng)用,2平衡二叉樹1.平衡化旋轉(zhuǎn)RL型平衡化旋轉(zhuǎn)先以b進行一次順時針旋轉(zhuǎn)，再以a進行一次逆時針旋轉(zhuǎn)，如圖9-9所示。即將整棵子樹(以a為根)旋轉(zhuǎn)為以c為根，a是c的左子樹，b是c的右子樹；c的右子樹移到b的左子樹位置，c的左子樹移到a的右子樹位置。,樹的應(yīng)用,2平衡二叉樹1.平衡化旋轉(zhuǎn)RR型平衡化旋轉(zhuǎn)用b取代a的位置，a作為b的左子樹的根結(jié)點，b原來的左子樹作為a的右子樹。,樹的應(yīng)用,3赫夫曼樹及其應(yīng)用赫夫曼(Huffman)樹又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。1.基本概念結(jié)點路徑：從樹中一個結(jié)點到另一個結(jié)點的之間的分支構(gòu)成這兩個結(jié)點之間的路徑。路徑長度：結(jié)點路徑上的分支數(shù)目稱為路徑長度。樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和。結(jié)點的帶權(quán)路徑長度：從該結(jié)點的到樹的根結(jié)點之間的路徑長度與結(jié)點的權(quán)(值)的乘積。權(quán)(值)：各種開銷、代價、頻度等的抽象稱呼。樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，記做：WPL=w1l1+w2l2+wnln=wili(i=1,2,n)其中：n為葉子結(jié)點的個數(shù)；wi為第i個結(jié)點的權(quán)值；li為第i個結(jié)點的路徑長度。,樹的應(yīng)用,3赫夫曼樹及其應(yīng)用,哈夫曼樹：給定一組具有確定權(quán)值的葉子結(jié)點，帶權(quán)路徑長度最小的二叉樹。例：給定4個葉子結(jié)點，其權(quán)值分別為2，3，4，7，可以構(gòu)造出形狀不同的多個二叉樹,WPL=32WPL=41WPL=30,樹的應(yīng)用,3赫夫曼樹及其應(yīng)用,2.哈夫曼樹的構(gòu)造,樹的應(yīng)用,3赫夫曼樹及其應(yīng)用所構(gòu)造的H