1、張乃孝 算法與數據結構C語言描述15.1樹與樹林5.2樹和樹林的存儲表示 5.3二 叉 樹 5.4二叉樹的存儲表示5.5哈夫曼算法及其應用張乃孝 算法與數據結構C語言描述2線性結構和非線性結構。 樹形結構是以分支關系定義的層次結構，在現實世界中廣泛存在，在計算機領域中也有廣泛應用。 本章重點討論二叉樹的存儲結構及其各種操作，并研究樹和森林與二叉樹之間的轉換關系。張乃孝 算法與數據結構C語言描述3 5.1.1 5.1.1 樹的定義樹的定義 5.1.2 5.1.2 基本術語基本術語 5.1.3 5.1.3 樹林樹林 5.1.4 5.1.4 樹的基本運算樹的基本運算 5.1.5 5.1.5 樹的周游

2、樹的周游 5.1.6 5.1.6 樹林的周游樹林的周游張乃孝 算法與數據結構C語言描述4樹樹(Tree)的例子：一個家族。A有子女B,C； B和 C分別有子女D,E,F和G,H;E有 子女I , J。 T=(N,R) ,其中 N=A, B, C, D, E, F, G, H, I, J R= A, B, A, C, B, D , B, E, B, F, C, G, C, H, E, I, E, J 張乃孝 算法與數據結構C語言描述5(c ) 凹入表（a）樹形表示ABCDEFIJGH張乃孝 算法與數據結構C語言描述6(A(B(D)(E(I)(J)(C(G)(H)(d) 嵌套括號表示法CDEIJF

3、GHAB(b) 文氏圖張乃孝 算法與數據結構C語言描述7 樹樹(Tree)：是包括n(n=0)個結點結點的有限集T。當T非空時，滿足：（1）有且僅有一個特別標出的稱為根根的 結點；（2）除除根結點根結點外，其余結點可分為m（m=0） 個互不相交非空的有限集T1, T2, , Tm, 其中 每一個集合本身又是一棵樹，稱為根的子樹子樹 (Subtree)。樹的遞歸定義：樹的遞歸定義：空樹空樹：不包括任何結點的樹。張乃孝 算法與數據結構C語言描述8樹結構的特點：樹結構的特點：（1）樹的根的結點沒前驅結點，除了根結點之外 的所有結點都有且只有一個前驅結點；（2）樹的結點可以有零個或多個后繼結點。 樹結

4、構描述的是層次關系。張乃孝 算法與數據結構C語言描述9 (a) 樹t (b) 樹t 圖5.2 樹t和樹t 張乃孝 算法與數據結構C語言描述10 父結點父結點，子結點，子結點，邊邊 若結點y是結點x的一棵子樹的根，則x稱作y的父結父結點點（或父母）；y稱作x的子結點子結點（或子女）；有序對稱作從x到y的邊邊。例如樹t中，C是E的父結點，E是C的子結點，是從C到E的邊（它對應著圖中的有向線段CE）。 兄弟結點兄弟結點具有同一父母的結點彼此稱作兄弟兄弟。樹t中B，C，D互為兄弟，F，G互為兄弟，等等。注意，E和F并不是兄弟。 張乃孝 算法與數據結構C語言描述11 祖先祖先，子孫子孫若結點y在以結點x

5、為根的一個子樹（或樹）中，且yx，則稱x是y的祖先祖先，y是x的子孫子孫。例如樹t中，A是其它各結點的祖先；C是E，H，I，J的祖先。 路徑路徑，路徑長度路徑長度如果x是y的一個祖先，又有xx0，x1，xny，滿足xi（i0，1，n-1）為xi+1的父結點，則稱x0，x1，xn為從x到y的一條路徑路徑。n稱為這條路徑的長度路徑的長度。路徑中相鄰的兩個結點可以表示成一條邊。 例如樹t中A，C，E，I，J是從A到J的一條路徑，其長度為4。 張乃孝 算法與數據結構C語言描述12 結點的層數結點的層數規定根的層數根的層數為0，其余結點的層數結點的層數等于其父母結點的層數加1。例如t中，0層的結點是A，

6、1層的結點有B，C，D，4層的結點是J。 樹的深度或高度樹的深度或高度樹中結點的最大層數稱為樹的深度樹的深度或樹的高度樹的高度。 例如樹t中，樹的深度為4。 張乃孝 算法與數據結構C語言描述13 結點的度數結點的度數、樹的度數樹的度數結點的子女個數叫作結點的度數度數。樹中度數最大的結點的度數叫作樹的度數樹的度數。例如t中A，C，E，J的度數分別為3，1，2，0；t的度數為3 樹葉樹葉、分支結點分支結點度數為0的結點稱作樹葉樹葉或終端結點終端結點；度數大于0的結點稱作分支結點分支結點或非終端結點非終端結點。例如樹t中B，F，G，H，J都是樹葉，其余結點都是分支結點。張乃孝 算法與數據結構C語言描

7、述14 無序樹無序樹、有序樹有序樹對子樹的次序不加區別的樹叫作無序樹無序樹。對子樹之間的次序加以區別的樹叫作有序樹有序樹。例如在圖5.2中，按無序樹的概念t和t是同一棵樹，按有序樹的概念則是不同的樹，本章討論的樹一般是有序樹。 結點的次序結點的次序 在有序樹中可以從左到右地規定結點的次序次序。按從左到右的順序，我們可以把一個結點的最左邊的子結點簡稱為最左子結點最左子結點，或直接稱為長子長子，而把長子右邊的結點稱為次子次子。例如在t中結點B是結點A的長子，結點C是結點A的次子，是結點B的兄弟。 張乃孝 算法與數據結構C語言描述15樹林樹林：是m（m=0）棵互不相交的樹所組成的集合。就邏輯結構而言

8、，任何一棵樹是一個二元組二元組Tree=(root,F) , 其中root稱為樹的根結點，F是m（m0）棵子樹構成的樹林，F=(T1, T2,Tm), 其中Ti=(ri,Fi)稱作根root的第i棵子樹；當m0時，在樹根和其子樹林之間存在下列關系: RF= | i=1,2,m, m0張乃孝 算法與數據結構C語言描述16 創建一棵空樹Tree createTree( Node p, Tree t1, Tree t2, , Tree ti ) i=1, 2, 3, 判斷某棵樹是否為空int isNull ( Tree t ) 求樹中的根結點，若為空樹，則返回一特殊值Node root ( Tree

9、 t ) 求某個指定結點的父結點，當指定結點為根時，返回一特殊值Node parent ( Node p ) 張乃孝 算法與數據結構C語言描述17 求樹中某個指定結點的最左子結點，當指定結點為樹葉時，返回一特殊值Node leftChild ( Node p ) 求樹中某個指定結點的右兄弟結點，當指定結點沒有右兄弟時，返回一特殊值Node rightSibling ( Node p ) 樹的周游：即按某種方式訪問樹中的所有結點，并使每個結點恰好被訪問一次。張乃孝 算法與數據結構C語言描述185.1.5 5.1.5 樹的周游樹的周游1. 周游的定義:按某一規律系統的訪問樹中的所有 結點，并使每個

10、結點恰好被訪問一次。2. 周游的方法：按深度方向和按寬度方向周游。 （I）按深度方向（以右圖為例）a. 先根次序b. 中根次序c. 后根次序張乃孝 算法與數據結構C語言描述19a. 先根次序 (1,2,3,5,8,9,6,10,4,7) （1） 訪問根結點； （2）從左到右按先根次序周游根結點的每棵子樹。 b. 中根次序 (2,1,8,5,9,3,10,6,7,4) （1）按中根次序周游根結點的最左子樹； （2）訪問根結點； （3）從左到右按中根次序周游根結點的其它各子樹。c. 后根次序 (2,8,9,5,10,6,3,7,4,1) （1）從左到右按后根次序周游根結點的每棵子樹; （2）訪問根

11、結點。張乃孝 算法與數據結構C語言描述20（II）按寬度方向周游 先訪問層數為0的結點，然后從左到右逐個訪 問層數為1的結點，依此類推，直到訪問完樹中 的全部結點。 層次序列（1，2，3，4，5，6，7，8，9，10）張乃孝 算法與數據結構C語言描述211. 先根（A, B, C, K, D, E, H, F, J, G )2. 后根 ( B, K, C, A, H, E, J, F, G, D )5.1.6 5.1.6 樹林的周游樹林的周游張乃孝 算法與數據結構C語言描述22 5.2.1 5.2.1 樹的存儲表示樹的存儲表示 5.2.2 5.2.2 樹林的存儲表示樹林的存儲表示 5.2.3

12、5.2.3 樹和樹林的其它表示法樹和樹林的其它表示法* *張乃孝 算法與數據結構C語言描述235.2.1 5.2.1 樹的存儲表示樹的存儲表示 樹的父指針表示法 樹的子表表示法 樹的長子-兄弟表示法張乃孝 算法與數據結構C語言描述24struct ParTreeNode/* 樹中結點結構 */ DataTypeinfo; /* 結點中的元素 */intparent; /* 結點的父結點位置 */;struct ParTree struct ParTreeNode nodelistMAXNUM; /* 存放樹中的結點 */ int n; /* 樹中結點的個數 */; typedef struct

13、 ParTree *PParTree;樹的父指針表示法用一組連續空間存儲樹的結點，并附設一個指示器指示其雙親結點的位置。結構類型如下：張乃孝 算法與數據結構C語言描述25 優點：a)容易找到父結點及其所有的祖先； b)能找到結點的子女和兄弟； 缺點：a)沒有表示出結點之間的左右次序； b)找結點的子女和兄弟比較費事。改進方法：按一種周游次序在數組中存放結點,。常見的一種方法是依次存放樹的先根序列，如下圖：張乃孝 算法與數據結構C語言描述26(a) (b) 圖5.5 一棵樹的父指針表示 張乃孝 算法與數據結構C語言描述27樹的子表表示法 結點表中的每一元素又包含一個子表，存放該結點的所有子結點。

14、結點表順序存放，子表用鏈接表示。struct EdgeNode /* 子表中節點的結構 */intnodeposition;struct EdgeNode*link;struct ChiTreeNode /* 結點表中節點的結構 */DataTypeinfo;struct EdgeNode*children;張乃孝 算法與數據結構C語言描述28子表表示的樹結構定義如下：struct ChiTree /* 樹結構 */ struct ChiTreeNode nodelistMAXNUM; introot; /* 根結點的位置 */ intn; /* 結點的個數 */typedef struct

15、ChiTree * PChiTree; 求某個結點的最左子女運算很容易實現，找到結點的全部子女也很容易，但求某個結點的父母和右兄弟實現起來比較費事。另一個缺點是：合并若干個子樹構成一個新樹時（createTree_chitree操作）也要考慮多個結點表的合并問題，由于這些結點表通常用順序方式表示，所以合并起來比較麻煩。 張乃孝 算法與數據結構C語言描述29 info parent 0 a 1 b 2 d 3 e 4 h 5 i 6 j 7 c 8 f 9 g 1 7 2 3 4 6 8 9 5 圖5.6 樹的子表表示法張乃孝 算法與數據結構C語言描述30 在樹的每個結點中，除信息域外，增加指向

16、其最左子女和右兄弟的指針。struct CSNode; /* 樹中結點結構 */typedef struct CSNode *PCSNode;/* 結點的指針類型 */struct CSNode /* 結點結構定義 */ DataType info;/* 結點中的元素 */PCSNode lchild; /* 結點的最左子女的指針 */PCSNode rsibling;/* 結點的右兄弟的指針 */; typedef struct CSNode *CSTree; /* 樹類型定義 */ 樹的長子-兄弟表示法張乃孝 算法與數據結構C語言描述31 t a b d c e h i j f g 圖5.

17、7 樹的長子兄弟表法張乃孝 算法與數據結構C語言描述325.2.2 5.2.2 樹林的存儲表示樹林的存儲表示 父指針表示法 子表表示法 長子-兄弟表示法張乃孝 算法與數據結構C語言描述33樹林的父結點表示方法 張乃孝 算法與數據結構C語言描述34 info parent 0 A 1 B 2 C 3 K 4 D 5 E 6 H 7 F 8 J 9 G 1 2 3 5 9 8 6 7 樹林的子表表示法張乃孝 算法與數據結構C語言描述35 t A B D C E H J K F G 樹林的長子兄弟表示法張乃孝 算法與數據結構C語言描述36 5.3.1 5.3.1 二叉樹的基本概念二叉樹的基本概念 5

18、.3.2 5.3.2 二叉樹的性質二叉樹的性質 5.3.3 5.3.3 二叉樹的基本運算二叉樹的基本運算 5.3.4 5.3.4 二叉樹的周游二叉樹的周游 5.3.5 5.3.5 樹、樹林與二叉樹的轉換樹、樹林與二叉樹的轉換張乃孝 算法與數據結構C語言描述37二叉樹： 它是結點的有限集合，這個集合或者為空集或者由一個根及兩棵不相交的分別稱作這個根的“左子樹”和“右子樹”的二叉樹組成。 它的每一個結點至多有兩棵子樹，并且子樹有左右之分，不能隨意顛倒。5.3.1 5.3.1 二叉樹的基本概念二叉樹的基本概念張乃孝 算法與數據結構C語言描述38二叉樹的基本形態：左子樹右子樹右子樹左子樹（1）空二叉樹

19、（2）只有一個根結點（3）有根結點 和左子樹（4）有根結點 和右子樹（5）有根結點 和左，右子樹張乃孝 算法與數據結構C語言描述39 二叉樹不是樹的特殊情形，它們是兩個概念。 樹和二叉樹之間最主要的差別是：二叉樹中結點的子樹要區分為左子樹和右子樹，即使在結點只有一棵子樹的情況下也要明確指出該子樹是左子樹還是右子樹。 （3）和（4）是兩棵不同的二叉樹，但作為樹，它們是相同的。 在二叉樹中可定義類似樹中的概念。張乃孝 算法與數據結構C語言描述40 滿二叉樹滿二叉樹：如果一棵二叉樹的任何結點或者是樹葉，或者有兩棵非空子樹，則此二叉樹稱作“滿二叉樹”。 完全二叉樹完全二叉樹：如果一棵二叉樹至多只有最下

20、面的兩層結點度數可以小于2，并且最下面一層的結點都集中在該層最左邊的若干位置上，則此二叉樹稱為“完全二叉樹”。完全二叉樹不一定是滿二叉樹。張乃孝 算法與數據結構C語言描述41滿二叉樹完全二叉樹張乃孝 算法與數據結構C語言描述42擴充二叉樹擴充二叉樹 ： 把原二叉樹的結點都變為度數為2的分支結點，也就是說，如果原結點的度數為2，則不變，度數為1，則增加一個分支，度數為0（樹葉）增加兩個分支。 張乃孝 算法與數據結構C語言描述43在擴充的二叉樹里，新增加的外部結點的個數比原來的內部結點個數多1。 “外部路徑長度”E：在擴充的二叉樹里從根到每個外部結點的路徑長度之和。“內部路徑長度”I：在擴充的二叉

21、樹里從根到每個內部結點的路徑長度之和。 E = I + 2n 其中，n是內部結點的個數。張乃孝 算法與數據結構C語言描述44證明：當n=1時，I=0, E=2, 此等式成立。 設有n個內部結點的擴充二叉樹，下式成立。 En=In+2n (1) 對于 n+1 個內部結點的擴充二叉樹，去掉一個 作為原來二叉樹路徑長度為K的內部結點，內部路徑長度變為： In=In+1-K (2) 外部路徑長度變為：En=En+1-2(K+1)+K= En+1 -K-2 即： En+1= En+K+2 En+1= (In+2n) +K+2= (In+1-K) +2n+K+2= In+1+2(n+1) 代入（1） 代入

22、（2）張乃孝 算法與數據結構C語言描述45abceef張乃孝 算法與數據結構C語言描述46性質性質1. 在非空二叉樹的第i層上至多有2i個結點（i0）。歸納： i=0, 結點數=1=20 . 假設對于j(0j i), 結點數至多有2j . 對于i=j+1, 結點數至多為 2* 2j=2j+1 .性質性質2. 深度為k的二叉樹至多有2k+1-1個結點（k 0）。 K k M= mi 2i = 2k+1-1 i=0 i=0 20 + 21 + 22 + 2k5.3.2 5.3.2 二叉樹的性質二叉樹的性質張乃孝 算法與數據結構C語言描述47性質性質3. 對任何一棵非空二叉樹T，如果葉結點數 為n0

23、， 度為2的結點數為n2，則n0=n2+1。 n0+n1+n2 = 所有 結點的度數和+1 = n1+ 2*n2 +1 性質性質4. 具有n個結點的完全二叉樹的深度k為log2n . n=20+21+22+2k-1+mk =2k-1+mk 2k-1n 2k+1-1 2k n 2k+1 k log2n k+1 k= log2n 張乃孝 算法與數據結構C語言描述48性質性質5. 如果對一棵有n個結點的完全二叉樹按層次次序 從1開始編號，則對任一結點i（1 in)，有： 1）i=1，序號結點i是根；i1, 其雙親結點是 i/2 。 2）2i n，序號為i的結點的左子女結點的序號為2i； 2in ,序

24、號為i的結點無左子女。 3）2i+1 n，序號為i的結點的右子女結點的序號 為2i+1; 2i+1 n,序號為i的結點無右子女。張乃孝 算法與數據結構C語言描述49性質5的證明：對于（2）和（3） 當i=1時， 2i=2 n ，左子女結點的序號為2。2i+1=3 n， 右子女結點的序號為3。 假設對于序號為j的結點，命題成立。 對于i=j+1，其左子女結點的序號等于j的右子女結點的序號加1，即：2j+1+1=2(j+1) 其右子女結點的序號等于：2(j+1)+1根據（2）和（3），知的父結點為i/2. 完全二叉樹的層次序列，反映了它的結構。張乃孝 算法與數據結構C語言描述50123jj+1 2

25、j 2j+1 2(j+1) 2(j+1)+1張乃孝 算法與數據結構C語言描述515.3.3 5.3.3 二叉樹的基本運算二叉樹的基本運算創建一棵空二叉樹；判斷某棵二叉樹是否為空；求二叉樹的根結點，若為空，則返回一特殊值；求二叉樹中某個指定結點的父結點，當指定結點為根時，返回一特殊值；求二叉樹中某個指定結點的左子女結點，當指定結點沒有左子女時，返回一特殊值；求二叉樹中某個指定結點的右子女結點，當指定結點沒有右子女時，返回一特殊值；二叉樹的周游。張乃孝 算法與數據結構C語言描述52二叉樹的周游二叉樹的周游(Traversing Binary Tree)： 按某條搜索路徑訪問二叉樹中的所有結點 ，使

26、得每個結點被訪問一次且僅被訪問一次。三種方式： 先根次序 (DLR) 對稱序 (LDR) 后根次序 (LRD)DLR張乃孝 算法與數據結構C語言描述53ABDCEFIHG 圖5.15 二叉樹先根次序A B D C E G F H I 后根次序D B G E H I F C A 對稱序（中根次序）D B A E G C H F I張乃孝 算法與數據結構C語言描述54 對右圖進行先根、后根和中根次序周游得到如下的結點序列： 先根：-ab+cd 前綴表示 后根：ab-cd+ 后綴表示 (波蘭表示法) 對稱序：a-b c+d 中綴表示-+abcd圖 5.16 表達式的二叉樹表示張乃孝 算法與數據結構C

27、語言描述551遞歸算法先根次序中根次序后根次序二. 非遞歸算法 (用自定義的棧來代替系統的棧)先根次序中根次序后根次序 1 2張乃孝 算法與數據結構C語言描述565.3.5 5.3.5 樹、樹林與二叉樹的轉換樹、樹林與二叉樹的轉換 1. 樹、樹林轉換為二叉樹執行步驟：（1）在所有相鄰的兄弟結點之間連一條線；（2）對每個非終端結點，只保留它到其最左子女的 連線，刪去它與其它子女的連線；（3）以根結點為軸心，將整棵樹進行旋轉。樹、樹林樹、樹林 二叉樹二叉樹張乃孝 算法與數據結構C語言描述57ABCKDEFGHJ圖5.20 樹林轉換為二叉樹張乃孝 算法與數據結構C語言描述58執行步驟：（1）若某結點

28、是其父母的左子女，則把該結點 的右子女，右子女的右子女， ,都與 該結點的父母用線連接起來； （2）去掉原二叉樹中所有父母到右子女的連線。張乃孝 算法與數據結構C語言描述59ABDCEKHFJG圖 5.22 二叉樹轉換為樹林張乃孝 算法與數據結構C語言描述60二叉樹的存儲表示 5.4.1 5.4.1 順序表示順序表示 5.4.2 5.4.2 鏈接表示鏈接表示 5.4.3 5.4.3 二叉樹的生成二叉樹的生成 5.4.4 5.4.4 線索二叉樹線索二叉樹* *張乃孝 算法與數據結構C語言描述61 用一組地址連續的存儲單元按層次次序依次存儲完全二叉樹的結點。完全二叉樹的層次序列反映了它的層次結構。

29、ABCGFEDHIJ A B C D E F G H I J 下標 0 1 2 3 4 5 6 7 8 9張乃孝 算法與數據結構C語言描述62 對于一般二叉樹，則應將其每個結點與完全二叉樹上的結點相對照，存儲在一維數組的相應分量中。圖514 一般二叉樹及其順序表示張乃孝 算法與數據結構C語言描述63采用順序表示，類型聲明如下： struct SeqBTree /* 順序樹類型定義 */ DataType nodelistMAXNODE;int n;/* 改造成完全二叉樹后，結點的個數 */ ；typedef struct SeqBTree *PSeqBTree;張乃孝 算法與數據結構C語言描述

30、64 二叉樹的鏈接表示是指用一個鏈表來存儲一棵二叉樹，二叉樹中的每一個結點用鏈表中的一個鏈結點來存儲，最常用的鏈接表示方式是左-右指針表示法（llink-rlink表示法，也稱做二叉鏈表），這種表示法在每個鏈結點中除存儲結點本身的數據外，再設置兩個指針字段：llink和rlink，分別存放結點的左子女和右子女所在鏈結點的存儲地址，當結點的某個子女為空時，則相應的指針為空指針。 張乃孝 算法與數據結構C語言描述65struct BinTreeNode;/* 二叉樹中結點 */typedef struct BinTreeNode *PBinTreeNode;/* 結點的指針類型 */struct

31、BinTreeNode DataType info;/* 數據域 */PBinTreeNode llink;/* 指向左子女 */PBinTreeNode rlink;/* 指向右子女 */;typedef struct BinTreeNode *BinTree; typedef BinTree *PBinTree; 張乃孝 算法與數據結構C語言描述66ABDCEFIHGt A B C E F I H G D 圖5.15 二叉樹的二叉鏈表表示張乃孝 算法與數據結構C語言描述67tA B D C E F I H G 圖5.15 三叉鏈表表示張乃孝 算法與數據結構C語言描述68 周游是二叉樹各種操

32、作的基礎，可以在周游過程中進行各種操作，如可以在周游過程中生成結點，從而建立一棵二叉樹。 例：讀入字符序列： ABDCEGFHI建立圖5.13所示的二叉樹，其中，表示空結點。算法5.5 按先根序列創建二叉樹張乃孝 算法與數據結構C語言描述69t A B C E F I H G D 圖5.15 二叉樹的二叉鏈表表示線索二叉樹線索二叉樹* * 張乃孝 算法與數據結構C語言描述70保存遍歷過程中得到的信息以供某些操作使用（1增加兩個指針（2利用結構中的空鏈域，并設立標志。線索線索：指向結點前驅或后繼的指針。線索二叉樹線索二叉樹：加上線索的二叉樹。線索化線索化：對二叉樹以某種次序遍歷使其變為線索二叉樹

33、的過程。按對稱序線索化二叉樹按對稱序線索化二叉樹: :按對稱序周游二叉樹，周游到那個結點對那個結點加線索。按對稱序周游對稱序穿線樹按對稱序周游對稱序穿線樹: :沿線索周游。張乃孝 算法與數據結構C語言描述71struct ThrTreeNode;typedef struct ThrTreeNode*PThrTreeNode;struct ThrTreeNode /*結點類型*/ DataType info;PThrTreeNode llink, rlink;int ltag, rtag;typedef struct ThrTreeNode *ThrTree, /*樹類型*/typedef Th

34、rTree *PThrTree; /*類型的指針類型*/張乃孝 算法與數據結構C語言描述72Struct SeqStack /*棧元素的類型為PThrTreeNode*/ PThrTreeNode sMAXNODE; int t; ;typedef Struct SeqStack *PSeqStack;算法算法5.6 按對稱序線索化二叉樹按對稱序線索化二叉樹算法算法5.7 按對稱序周游對稱序穿線樹按對稱序周游對稱序穿線樹張乃孝 算法與數據結構C語言描述73 對稱序穿線樹里的線索總是指向二叉樹中更高層的結點，也就是說是“向上”指的(如下圖）。利用該“向上”指的線索我們可以在對稱序穿線樹里找出指定結點在先根下的后繼結點和后根下的前驅結點。張乃孝 算法與數據結構C語言描述74哈夫曼算法及其應用 5.5.1 5.5.1 哈夫曼樹哈夫曼樹 5.5.2 5.5.2 哈夫曼哈夫曼(Huffman)(Huffman)算法算法 5.5.3 5.5.3 哈夫曼編碼哈夫曼編碼張乃孝 算法與數據結構C語言描述755.5.1 5.5.1 哈夫曼樹哈夫曼樹擴充二叉樹的外部路徑長度：其中：li為從根到第i個外部結點的路徑長度，m為外部結點的個數 1miiEl擴充二叉樹的帶權的外部路徑長度 其中：wi是第i個外部結點的權值，li為從根到第i個外部結點的路徑長度，m為外部結