1、2020/8/30,mayan,第六章 樹,樹 二叉樹 線索二叉樹 樹與森林 Huffman樹,2020/8/30,mayan,樹 -樹的定義和術(shù)語,樹：一棵樹 T，簡稱為樹，它是n (n0) 個(gè)結(jié)點(diǎn)的有限集合。當(dāng)n = 0時(shí)，T 稱為空樹；否則，T 是非空樹，記作 其中，r 是一個(gè)特定的稱為根(root)的結(jié)點(diǎn)，它沒有直接前驅(qū)；根以外的其他結(jié)點(diǎn)劃分為 m (m 0) 個(gè)互不相交的有限集合T1, T2, , Tm，每個(gè)集合又是一棵樹，并且稱之為根的子樹。,2020/8/30,mayan,樹 -樹的定義和術(shù)語,相關(guān)術(shù)語 子女：若結(jié)點(diǎn)的子樹非空，結(jié)點(diǎn)子樹的根即為該結(jié)點(diǎn)的子女。 雙親：若結(jié)點(diǎn)有子女，

2、該結(jié)點(diǎn)是子女雙親。 兄弟：同一結(jié)點(diǎn)的子女互稱為兄弟。 度：結(jié)點(diǎn)的子女個(gè)數(shù)即為該結(jié)點(diǎn)的度；樹中各個(gè)結(jié)點(diǎn)的度的最大值稱為樹的度。 分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)即為分支結(jié)點(diǎn)，亦稱為非終端結(jié)點(diǎn)。,2020/8/30,mayan,樹 -樹的定義和術(shù)語,葉結(jié)點(diǎn)：度為0的結(jié)點(diǎn)即為葉結(jié)點(diǎn)，亦稱為終端結(jié)點(diǎn)。 祖先：某結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑上的各個(gè)結(jié)點(diǎn)都是該結(jié)點(diǎn)的祖先。 子孫：某結(jié)點(diǎn)的所有下屬結(jié)點(diǎn)，都是該結(jié)點(diǎn)的子孫。 結(jié)點(diǎn)的層次：規(guī)定根結(jié)點(diǎn)在第一層，其子女結(jié)點(diǎn)的層次等于它的層次加一。以此類推。 深度：結(jié)點(diǎn)的深度即為結(jié)點(diǎn)的層次；離根最遠(yuǎn)結(jié)點(diǎn)的層次即為樹的深度。,2020/8/30,mayan,樹 -樹的定義和術(shù)語,高度：規(guī)

3、定葉結(jié)點(diǎn)的高度為1，其雙親結(jié)點(diǎn)的高度等于它的高度加一。 樹的高度：等于根結(jié)點(diǎn)的高度，即根結(jié)點(diǎn)所有子女高度的最大值加一。 有序樹：樹中結(jié)點(diǎn)的各棵子樹 T0, T1, 是有次序的，即為有序樹。 無序樹：樹中結(jié)點(diǎn)的各棵子樹之間的次序是不重要的，可以互相交換位置。 森林：森林是m（m0）棵樹的集合。,2020/8/30,mayan,樹 -樹的抽象數(shù)據(jù)類型,教材 p118-120,2020/8/30,mayan,二叉樹 -二叉樹的定義,一棵二叉樹是結(jié)點(diǎn)的一個(gè)有限集合，該集合或者為空，或者是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。,2020/8/30,mayan,二叉樹 -二叉

4、樹的性質(zhì),性質(zhì)1 若二叉樹結(jié)點(diǎn)的層次從 1 開始, 則在二叉樹的第 i (i1)層最多有 2i-1 個(gè)結(jié)點(diǎn)。 證明用數(shù)學(xué)歸納法 性質(zhì)2 深度為 k (k0) 的二叉樹最少有 k 個(gè)結(jié)點(diǎn)，最多有 2k-1個(gè)結(jié)點(diǎn)。 證明：因?yàn)槊恳粚幼钌僖?個(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,2020/8/30,mayan,二叉樹 -二叉樹的性質(zhì),性質(zhì)3 對(duì)任何一棵二叉樹，如果其葉結(jié)點(diǎn)有 n0 個(gè), 度為 2 的非葉結(jié)點(diǎn)有 n2 個(gè), 則有 n0n21 證明：若設(shè)度為 1 的結(jié)點(diǎn)有 n1 個(gè)，總結(jié)點(diǎn)數(shù)為n，總邊數(shù)為e，

5、則根據(jù)二叉樹的定義， n = n0+n1+n2 , e = 2n2+n1 = n-1 因此，有 2n2+n1 = n0+n1+n2-1則 n2 = n0-1 n0 = n2+1,2020/8/30,mayan,二叉樹 -二叉樹的性質(zhì),定義1 滿二叉樹 (Full Binary Tree) ：深度為k的滿二叉樹是有2k-1個(gè)結(jié)點(diǎn)的二叉樹。 定義2 完全二叉樹 (Complete Binary Tree)：若設(shè)二叉樹的深度為 k，則共有 k 層。除第 k 層外，其它各層 (1k-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第k層從右向左連續(xù)缺若干結(jié)點(diǎn)，這就是完全二叉樹。,2020/8/30,mayan,二叉樹

6、-二叉樹的性質(zhì),性質(zhì)4 具有 n (n0) 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 log2(n+1)。 證明： 設(shè)完全二叉樹的深度為k，則有2k-1-1 n 2k-1 即 2k-1 n+12k ，取對(duì)數(shù) k-1 log2(n+1) k 有 k= log2(n+1),2020/8/30,mayan,二叉樹 -二叉樹的性質(zhì),性質(zhì)5 如將一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點(diǎn)編號(hào)1, 2, , n，則有以下關(guān)系： 若i = 1, 則 i 無雙親； 若i 1, 則 i 的雙親為i2； 若2*i = n, 則 i 的左子女為 2*i； 若2*i+1 = n, 則 i 的右子女為2*i+1；

7、若 i 為奇數(shù), 且i != 1, 則其左兄弟為i-1； 若 i 為偶數(shù), 且i != n, 則其右兄弟為i+1； 結(jié)點(diǎn)i 所在的層次為log2i+1,2020/8/30,mayan,二叉樹 -二叉樹的抽象數(shù)據(jù)類型,教材 P121-123,2020/8/30,mayan,二叉樹 -二叉樹的數(shù)組存儲(chǔ)表示,教材p126定義,2020/8/30,mayan,二叉樹 -二叉樹的鏈表存儲(chǔ)表示,二叉鏈表和三叉鏈表的概念 二叉樹結(jié)點(diǎn)定義：每個(gè)結(jié)點(diǎn)有3個(gè)域，data域存儲(chǔ)結(jié)點(diǎn)數(shù)據(jù)，lchild和rchild分別存放指向左子女和右子女的指針。 二叉鏈表如下圖所示：,2020/8/30,mayan,二叉樹 -二叉

8、樹的鏈表存儲(chǔ)表示,每個(gè)結(jié)點(diǎn)增加一個(gè)指向雙親的指針parent，使得查找雙親也很方便。,2020/8/30,mayan,二叉樹 -二叉樹的鏈表存儲(chǔ)表示,整個(gè)二叉樹的鏈表有一個(gè)表頭指針，他指向二叉樹的根結(jié)點(diǎn)。 在含有n個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈指針域，三叉鏈表則有n+2個(gè)空鏈指針域。 2n-(n-1)=n+1 n+1+1=n+2,2020/8/30,mayan,二叉樹 -二叉樹的鏈表存儲(chǔ)表示,二叉樹的鏈表表示,2020/8/30,mayan,二叉樹 -二叉樹的二叉鏈表存儲(chǔ)表示,二叉樹的二叉鏈表存儲(chǔ)表示 typedef struct BiTNode TElemType data; struct

9、 BiTNode *lchild, *rchild;/ 左、右孩子指針 BiTNode, *BiTree; 二叉樹的三叉鏈表存儲(chǔ)表示 typedef struct TriTNode / 結(jié)點(diǎn)結(jié)構(gòu) TElemType data; struct TriTNode *lchild, *rchild; / 左右孩子指針 struct TriTNode *parent; /雙親指針 TriTNode, *TriTree;,基于二叉樹的二叉鏈表存儲(chǔ)表示的基本操作的函數(shù)原形見教材p127,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,二叉樹的遍歷（Binary Tree Traversal）就是按

10、某種次序訪問樹中的結(jié)點(diǎn)，要求每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。“訪問”的意思是對(duì)結(jié)點(diǎn)施行某些操作。 令L、R、D分別代表遍歷一個(gè)結(jié)點(diǎn)的左子樹、右子樹和訪問該結(jié)點(diǎn)的操作，則可能有DLR, LDR,LRD,DRL,RDL,RLD六種遍歷二叉樹的規(guī)則，若規(guī)定先左后右則有DLR（前序遍歷）、 LDR（中序遍歷）、 LRD（后序遍歷）三種。,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,三種遍歷算法： 先序遍歷：訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。 中序遍歷：中序遍歷左子樹；訪問根結(jié)點(diǎn)；中序遍歷右子樹。 后序遍歷：后序遍歷左子樹；后序遍歷右子樹；訪問根結(jié)點(diǎn)。,2020/8/30,mayan

11、,二叉樹 -二叉樹的遍歷,Status PreOrderTraverse( BiTree T, Status(*Visit)(ElemType) ) / 算法6.1.采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元 /素操作的應(yīng)用函數(shù)，先序遍歷二叉樹T的遞歸算 / 法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。 / 最簡單的Visit函數(shù)是： / Status PrintElement( ElemType e ) / 輸出元素e的值 / printf( e ); / 實(shí)用時(shí)，加上格式串 / return OK; / / 調(diào)用實(shí)例：PreOrderTraverse(T, PrintElement);,2020

12、/8/30,mayan,二叉樹 -二叉樹的遍歷,if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild, Visit) if (PreOrderTraverse(T-rchild, Visit) return OK; return ERROR; else return OK; / PreOrderTraverse,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,中序遍歷二叉樹T的非遞歸算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.2.采用二叉鏈

13、表存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù)元 /素操作的應(yīng)用函數(shù)。中序遍歷二叉樹T的非遞歸算 /法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,InitStack(S); Push(S, T); / 根指針進(jìn)棧 while (!StackEmpty(S) while (GetTop(S, p) / InOrderTraverse,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,中序遍歷二叉樹T的非遞歸算法 Status InOrderTraverse(BiTree T, Status (*Visit)(ElemType) / 算法6.3.采用二叉鏈表

14、存儲(chǔ)結(jié)構(gòu)，Visit是對(duì)數(shù)據(jù) /元素操作的應(yīng)用函數(shù)。中序遍歷二叉樹T的非遞歸 /算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit。,2020/8/30,mayan,二叉樹 -二叉樹的遍歷,InitStack(S); p = T; while (p | !StackEmpty(S) if (p) Push(S, p); p = p-lchild; else Pop(S, p); if (!Visit(p-data) return ERROR; p = p-rchild; return OK; / InOrderTraverse,2020/8/30,mayan,二叉樹 -以遞歸方式建立二叉樹,BiTree

15、CreateBiTree(BiTree scanf(%c, / CreateBiTree,2020/8/30,mayan,二叉樹,例1：給定一棵二叉樹的先序序列EBADCFHGIKJ和中序序列ABCDEFGHIJK，畫出這顆二叉樹。,2020/8/30,mayan,二叉樹,例2：給定一棵二叉樹的中序序列DCBGEAHFIJK和后序序列DCEGBFHKJIA，畫出這顆二叉樹。,2020/8/30,mayan,二叉樹,例3：給定一棵二叉樹的先序和后序序列不能確定一棵二叉樹。,2020/8/30,mayan,線索二叉樹 -線索二叉樹的概念,為什么提出線索二叉樹？ 遍歷的過程實(shí)質(zhì)上是對(duì)一個(gè)非線性結(jié)構(gòu)進(jìn)

16、行線性化的操作，使每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)）在這個(gè)線性序列中有且僅有一個(gè)直接前驅(qū)和直接后繼。二叉樹中只存儲(chǔ)了左右孩子的信息，因此，前驅(qū)和后繼的信息無法直接找到。就提出了線索二叉樹的概念。 又因?yàn)閚個(gè)結(jié)點(diǎn)的二叉鏈表中有n+1個(gè)空鏈域，從而得到線索二叉樹的存儲(chǔ)結(jié)構(gòu)如下。,2020/8/30,mayan,線索二叉樹 -線索二叉樹的概念,規(guī)定：若結(jié)點(diǎn)有左子樹，則lchild指示其左孩子，否則令lchild指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild指示其后繼。為避免混淆，增加兩個(gè)標(biāo)志域：LTag為0（1）表示lchild指向左孩子（前驅(qū)），RTag為0（1）表示r

17、child指向右孩子（后繼）。,2020/8/30,mayan,線索二叉樹 -線索二叉樹的概念,其中，指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索。加上線索的二叉樹稱為線索二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫線索化。,2020/8/30,mayan,線索二叉樹 -線索二叉樹的概念,2020/8/30,mayan,線索二叉樹-二叉樹的二叉線索存儲(chǔ)表示,typedef enum PointerTag Link, Thread ; / Link=0:指針，Thread=1:線索 typedef struct BiThrNod TElemType data; struct BiThrNode

18、*lchild, *rchild; / 左右指針 PointerTag LTag, RTag; / 左右標(biāo)志 BiThrNode, *BiThrTree;,2020/8/30,mayan,線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索，而前驅(qū)和后繼的信息只有在遍歷時(shí)才能得到，因此線索化的過程即為在遍歷的過程中修改空指針的過程。,線索二叉樹-通過中序遍歷建立中序線索化二叉樹,2020/8/30,mayan,線索二叉樹-通過中序遍歷建立中序線索化二叉樹,Status InOrderThreading(BiThrTree / InOrderThreading,2020/8/30,maya

19、n,線索二叉樹-通過中序遍歷建立中序線索化二叉樹,void InThreading(BiThrTree p) / 算法6.7 if (p) InThreading(p-lchild); / 左子樹線索化 if (!p-lchild) / 建前驅(qū)線索 p-LTag = Thread; p-lchild = pre; if (!pre-rchild) / 建后繼線索 pre-RTag = Thread; pre-rchild = p; pre = p; / 保持pre指向p的前驅(qū) InThreading(p-rchild); / 右子樹線索化 / InThreading,2020/8/30,may

20、an,線索二叉樹-中序遍歷二叉線索鏈表表示的二叉樹,Status InOrderTraverse_Thr(BiThrTree T, Status (*Visit)(ElemType) / 算法6.5 p = T-lchild; / p指向根結(jié)點(diǎn) while (p != T) / 空樹或遍歷結(jié)束時(shí)，p=T while (p-LTag=Link) p = p-lchild; if (!Visit(p-data) return ERROR; while (p-RTag=Thread / InOrderTraverse_Thr,2020/8/30,mayan,線索二叉樹-尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼,尋

21、找當(dāng)前結(jié)點(diǎn)在中序下的后繼,RTag,rchild,2020/8/30,mayan,線索二叉樹-尋找當(dāng)前結(jié)點(diǎn)在中序下的后繼,尋找當(dāng)前結(jié)點(diǎn)在中序下的前驅(qū),2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,雙親表示法（父指針表示法） 以一組連續(xù)的存儲(chǔ)單元來存放樹中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)有兩個(gè)域，一個(gè)是data域，用來存放數(shù)據(jù)元素，一個(gè)是parent域，用來存放指示其父結(jié)點(diǎn)位置的指針。 這種存儲(chǔ)表示適合經(jīng)常需要尋找父結(jié)點(diǎn)的應(yīng)用。,2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,樹的雙親表存儲(chǔ)表示 #define MAX_TREE_SIZE 100 typedef struct PTNode

22、 /結(jié)點(diǎn)結(jié)構(gòu) TElemType data; int parent; / 雙親位置域 PTNode; typedef struct /樹結(jié)構(gòu) PTNode nodesMAX_TREE_SIZE; int r, n; / 根結(jié)點(diǎn)的位置和結(jié)點(diǎn)個(gè)數(shù) PTree;,2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,孩子表示法（子女鏈表表示法） 為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)子女鏈表，并將這些結(jié)點(diǎn)的數(shù)據(jù)和對(duì)應(yīng)子女鏈表的頭指針放在一個(gè)向量中，就構(gòu)成了子女鏈表表示。 這種存儲(chǔ)表示適合需要頻繁尋找子女的應(yīng)用。無序樹情形鏈表中各結(jié)點(diǎn)順序任意，有序樹必須自左向右鏈接各個(gè)子女結(jié)點(diǎn)。,2020/8/30,mayan,

23、樹與森林 -樹的存儲(chǔ)表示,樹的孩子鏈表存儲(chǔ)表示 typedef struct CTNode /孩子結(jié)點(diǎn)結(jié)構(gòu) int child; struct CTNode *next; *ChildPtr; typedef struct /雙親結(jié)點(diǎn)結(jié)構(gòu) TElemType data; ChildPtr firstchild; / 孩子鏈的頭指針 CTBox; typedef struct /樹結(jié)構(gòu) CTBox nodesMAX_TREE_SIZE; int n, r; / 結(jié)點(diǎn)數(shù)和根結(jié)點(diǎn)的位置 CTree;,2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,孩子兄弟表示法（子女-兄弟鏈表表示法） 子

24、女-兄弟鏈表表示法也稱為樹的二叉樹表示。他的每個(gè)結(jié)點(diǎn)的度為2 ，是最節(jié)省存儲(chǔ)空間的樹的存儲(chǔ)表示。每個(gè)結(jié)點(diǎn)由三個(gè)域組成： firstChild 指向該結(jié)點(diǎn)的第一個(gè)子女結(jié)點(diǎn)。無序樹時(shí)，可任意指定一個(gè)結(jié)點(diǎn)為第一個(gè)子女。 nextSibling 指向該結(jié)點(diǎn)的下一個(gè)兄弟。任一結(jié)點(diǎn)在存儲(chǔ)時(shí)總是有順序的。,2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,孩子兄弟表示法（子女-兄弟鏈表表示法）,2020/8/30,mayan,樹與森林 -樹的存儲(chǔ)表示,樹的二叉鏈表存儲(chǔ)表示 typedef struct CSNode TElemType data; struct CSNode *firstchild,

25、 *nextsibling; CSNode, *CSTree;,2020/8/30,mayan,樹與森林 -森林與二叉樹的轉(zhuǎn)換,將一般樹化為二叉樹表示就是用樹的子女-兄弟表示來存儲(chǔ)樹的結(jié)構(gòu)。 森林與二叉樹表示的轉(zhuǎn)換可以借助樹的二叉樹表示來實(shí)現(xiàn)。,2020/8/30,mayan,樹與森林 -森林與二叉樹的轉(zhuǎn)換,森林轉(zhuǎn)化成二叉樹的規(guī)則 若 F 為空，即 n = 0，則對(duì)應(yīng)的二叉樹 B 為空樹。 若 F 不空，則 二叉樹 B 的根是 F 第一棵樹 T1 的根； 其左子樹為B (T11, T12, , T1m)，其中，T11, T12, , T1m 是 T1 的根的子樹； 其右子樹為 B (T2, T

26、3, , Tn)，其中，T2, T3, , Tn 是除 T1 外其它樹構(gòu)成的森林。,2020/8/30,mayan,樹與森林 -森林與二叉樹的轉(zhuǎn)換,二叉樹轉(zhuǎn)換為森林的規(guī)則 如果 B 為空，則對(duì)應(yīng)的森林 F 也為空。 如果 B 非空，則 F 中第一棵樹 T1 的根為 B 的根； T1 的根的子樹森林 T11, T12, , T1m 是由 B 的根的左子樹 LB 轉(zhuǎn)換而來； F 中除了 T1 之外其余的樹組成的森林 T2, T3, , Tn 是由 B 的根的右子樹 RB 轉(zhuǎn)換而成的森林。,2020/8/30,mayan,樹與森林 -森林與二叉樹的轉(zhuǎn)換,2020/8/30,mayan,樹與森林 -樹

27、的遍歷,深度優(yōu)先遍歷 先根次序遍歷：先訪問樹的根結(jié)點(diǎn)，然后先根遍歷根的每棵子樹。樹的先根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的前序遍歷結(jié)果相同。樹的先根遍歷可以借助對(duì)應(yīng)二叉樹的前序遍歷算法實(shí)現(xiàn)。 后根次序遍歷：先依次后根遍歷每棵子樹，然后訪問根結(jié)點(diǎn)。樹的后根遍歷結(jié)果與其對(duì)應(yīng)二叉樹表示的中序遍歷結(jié)果相同。樹的后根遍歷可以借助對(duì)應(yīng)二叉樹的中序遍歷算法實(shí)現(xiàn)。,2020/8/30,mayan,樹與森林 -森林的遍歷,森林的遍歷也分為深度優(yōu)先遍歷和廣度優(yōu)先遍歷，深度優(yōu)先遍歷又可分為先根次序遍歷和后根次序遍歷。 深度優(yōu)先遍歷 給定森林 F，若 F = ，則遍歷結(jié)束。否則 若F = T1 = r1, T11, , T

28、1k , T2, ., Tm，則可以導(dǎo)出先根遍歷、后根遍歷兩種方法。其中，r1是第一棵樹的根結(jié)點(diǎn)，T11, , T1k是第一棵樹的子樹森林，T2, .,Tm是除去第一棵樹之后剩余的樹構(gòu)成的森林。,2020/8/30,mayan,樹與森林 -森林的遍歷,森林的先根次序遍歷 若森林F = ，返回；否則訪問森林的根（也是第一棵樹的根）r1；先根遍歷森林第一棵樹的根的子樹森林T11, , T1k；先根遍歷森林中除第一棵樹外其他樹組成的森林T2, .,Tm。 森林的后根次序遍歷 若森林 F = ，返回；否則后根遍歷森林 F 第一棵樹的根結(jié)點(diǎn)的子樹森林T11, , T1k；訪問森林的根結(jié)點(diǎn) r1；后根遍歷

29、森林中除第一棵樹外其他樹組成的森林T2, ., Tm。,2020/8/30,mayan,樹與森林 -森林的遍歷,森林的先根次序遍歷和后根次序遍歷分別對(duì)應(yīng)為二叉樹的前序遍歷和中序遍歷。 廣度優(yōu)先遍歷 若森林 F 為空，返回； 否則依次遍歷各棵樹的根結(jié)點(diǎn)；依次遍歷各棵樹根結(jié)點(diǎn)的所有子女；依次遍歷這些子女結(jié)點(diǎn)的子女結(jié)點(diǎn)；,2020/8/30,mayan,Huffman樹 -相關(guān)概念,路徑長度 (Path Length) 兩個(gè)結(jié)點(diǎn)之間的路徑長度 PL 是連接兩結(jié)點(diǎn)的路徑上的分支數(shù)。 樹的外部路徑長度是各葉結(jié)點(diǎn)（外結(jié)點(diǎn)）到根結(jié)點(diǎn)的路徑長度之和 EPL。 樹的內(nèi)部路徑長度是各非葉結(jié)點(diǎn)（內(nèi)結(jié)點(diǎn)）到根結(jié)點(diǎn)的路

30、徑長度之和 IPL。 樹的路徑長度 PL = EPL + IPL。,2020/8/30,mayan,Huffman樹 -相關(guān)概念,n 個(gè)結(jié)點(diǎn)的二叉樹的路徑長度不小于下述數(shù)列前 n 項(xiàng)的和，即,2020/8/30,mayan,Huffman樹 -相關(guān)概念,其路徑長度最小者為 完全二叉樹滿足這個(gè)要求。 帶權(quán)路徑長度 (Weighted Path Length, WPL) 樹的帶權(quán)路徑長度為樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和。,2020/8/30,mayan,Huffman樹 -相關(guān)概念,2020/8/30,mayan,Huffman樹 -相關(guān)概念,Huffman樹 假設(shè)有n個(gè)權(quán)值w1,w2,wn，試構(gòu)造一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹為最優(yōu)二叉樹，即Hu