第 六 章 樹和二叉樹

1、第 六 章 樹和二叉樹樹和二叉樹 6.1 樹的定義和基本術(shù)語 6.2 二叉樹 6.2.1 二叉樹的定義 6.2.2 二叉樹的性質(zhì) 6.2.3 二叉樹的存儲結(jié)構(gòu) 6.3 遍歷二叉樹和線索二叉樹 6.3.1 遍歷二叉樹 6.3.2 線索二叉樹 6.4 樹和森林 6.4.1 樹的存儲結(jié)構(gòu) 6.4.2 森林與二叉樹的轉(zhuǎn)換 6.6 赫夫曼樹及其應(yīng)用 6.6.1 最優(yōu)二叉樹(赫夫曼樹) 非線性數(shù)據(jù)結(jié)構(gòu)。 樹的遞歸定義： 樹(tree)是n(n=0)個結(jié)點的有限集。 當n0時, (1)有且僅有一個特定的稱為根(root)的結(jié)點; (2)當n1時,其余結(jié)點可分為m(m0)個互不相 交的有限集T1,T2,.,T

2、m,其中每個集合本身又是一 棵樹。稱為子樹子樹(subtree)(subtree)。 第六章 樹和二叉樹 6.1 樹的定義和基本術(shù)語 樹的示例 空樹 n=0 層次 1 2 3 4 一般的樹 A BC D EFG H I JK L 只有根結(jié)點 的樹 n=1 A ADT Tree 數(shù)據(jù)對象數(shù)據(jù)對象D：D是具有相同特性的數(shù)據(jù)元素的集合。 數(shù)據(jù)關(guān)系數(shù)據(jù)關(guān)系R：若D為空集，則稱為空樹; 若D僅含一個數(shù)據(jù)元素，則R為空集，否則RH， H是如下二元關(guān)系： （1）在D中存在唯一的稱為根的數(shù)據(jù)元素root，它在關(guān) 系H下無前驅(qū)； （2）若Droot，則存在Droot的一個 劃分D1, D2, ., Dm （m0

3、），對任意jk（1j,km） 有DjDk= ，且對任意的i（1im），唯一存在數(shù)據(jù) 元素xiDi，有H; （3）對應(yīng)于Droot的劃分，H，.， 有唯一的一個劃分H1 , H2 ,., Hm （m0）， 對任意jk（1j,km）有HjHk= ，且對任意的i （1im），Hi 是Di上的二元關(guān)系，（Di ,Hi）是一棵 符合本定義的樹，稱為根root的子樹。 樹的抽象數(shù)據(jù)類型定義： INITTREE（T）； 操作結(jié)果：構(gòu)造空樹T。 DESTROYTREE（T）； 初始條件：樹T存在。 操作結(jié)果：銷毀樹T。 CREATETREE（T，DEFINITION）； 初始條件：DEFINITION給出樹T

4、的定義。 操作結(jié)果：按DEFINITION構(gòu)造樹T。 CLEARTREE（T）； 初始條件：樹T存在。 操作結(jié)果：將樹T清為空樹。 樹的抽象數(shù)據(jù)類型定義： 基本操作（之一）基本操作（之一） TREEEMPTY（T） 初始條件：樹T存在。 操作結(jié)果：若T為空樹，則返回TURE，否則FALSE。 TREEDEPTH（T） 初始條件：樹T存在。 操作結(jié)果：返回T的深度。 ROOT（T） 初始條件：樹T存在。 操作結(jié)果：返回T的根。 VALUE（T, CUR_E）； 初始條件：樹T存在，CURE是T中某個結(jié)點。 操作結(jié)果：返回CURE的值。 樹的抽象數(shù)據(jù)類型定義： 基本操作（之二）基本操作（之二） A

5、SSIGN（T，CUR_E，VALUE） 初始條件：樹T存在，CURE是T中某個結(jié)點。 操作結(jié)果：結(jié)點CUR_E賦值 為VALUE。 PARENT（T，CURE） 初始條件：樹T存在，CURE是T中某個結(jié)點。 操作結(jié)果：若CURE是T的非根結(jié)點，則返回它的雙親，否則函 數(shù)值為“空”。 LEFTCHILD（T，CURE） 初始條件：樹T存在，CURE是T中某個結(jié)點。 操作結(jié)果：若CURE是T的非葉子結(jié)點，則返回它的最左孩子， 否則返回“空”。 RIGHTSIBLING（T，CURE） 初始條件：樹T存在，CURE是T中某個結(jié)點。 操作結(jié)果：若CURE有右兄弟，則返回它的右兄弟，否則函數(shù)值 為“空

6、”。 樹的抽象數(shù)據(jù)類型定義： 基本操作（之三）基本操作（之三） INSERTCHILD（T，P，I，C）； 初始條件：樹T存在，P指向T中某個結(jié)點，1IP所指結(jié) 點的度1，非空樹C與T不相交。 操作結(jié)果：插入C為T中P指結(jié)點的第I棵子樹。 DELETECHILD（T，P，I）； 初始條件：樹T存在，P指向T中某個結(jié)點，1IP指結(jié)點 的度。 操作結(jié)果：刪除T中P所指結(jié)點的第I棵子樹。 TRAVERSETREE（T，VISIT（）； 初始條件：樹t存在，VISIT是對結(jié)點操作的應(yīng)用函數(shù)。 操作結(jié)果：按某種次序?qū)的每個結(jié)點調(diào)用函數(shù)VISIT（） 一次且至多一次。一旦VISIT（）失敗，則操作失敗。

7、 ADT TREE 樹 的 抽 象 數(shù) 據(jù) 類 型 定 義 ： 基本操作（之四）基本操作（之四） 子樹(subtree) 結(jié)點 結(jié)點的度(degree) 葉子(leaf)(終端結(jié)點) 分支結(jié)點(非終端結(jié)點) 樹的度 樹的基本術(shù)語（之一） A BC D FG H I L 孩子(child) 雙親(parent) 兄弟(sibling) 堂兄弟 祖先 子孫 樹的基本術(shù)語（之二） A BC D FG H I L 子樹(subtree) 層次(level) 深度(depth) 有序樹 無序樹 森林: m(m=0)棵互不相 交的樹的集合. 樹的基本術(shù)語（之三） A BC D FG H I L 二叉樹(b

8、inary tree): 度不超過2的有序樹。 二叉樹的五種基本形態(tài) 6.2 6.2 二叉樹二叉樹 6.2.1 二叉樹的定義 (a) 空二叉樹; (b)僅有根結(jié)點的二叉樹；(c)右子樹為空的二叉樹； (d)左、右子樹均為非空的二叉樹； (e)左子樹為空的二叉樹。 (a) A (b) A (c) A (d) A (e) 性質(zhì)性質(zhì)2 2：深度為k的二叉 樹至多有2k-1個結(jié)點 (k=1). k-1 Nk = 2i = 2k-1 i = 0 性質(zhì)性質(zhì)3 3:對任何一棵二叉 樹T, 如果其葉結(jié)點數(shù)為 n0, 度為2的結(jié)點數(shù)為n2, 則 n0 = n2 + 1. 6.2.2 二叉樹的性質(zhì) - 性質(zhì)性質(zhì)1

9、 1：在二叉樹的第i層上至多有2(i-1)個結(jié)點(i=1). 一般的二叉樹 A B D EFH I JK L 層次 1 2 3 4 一棵深度為k且有 2k-1 個結(jié)點的二叉樹稱為滿 二叉樹。 k = 3 k = 4 滿二叉樹的定義滿二叉樹的定義: 1 2 3 4 5 6 7 89 14 1011 15 1213 深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié) 點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng) 時，稱之為完全二叉樹。 完全二叉樹的定義完全二叉樹的定義: 1 2 3 45 6 完全二叉樹和非完全二叉樹舉例完全二叉樹和非完全二叉樹舉例: 1 2 3 4 5 6 7 89101

10、112 完全二叉樹 1 23 4 56 非完全二叉樹 完全二叉樹 性質(zhì)性質(zhì)4： 具有n個結(jié)點的完全二叉樹的深度為log2n*+1。 性質(zhì)性質(zhì)5： 如果對一棵有n個結(jié)點的完全二叉樹（其深度為 log2n*+1）的結(jié)點按層序編號（從第1層到第log2n*+1 層，每層從左到右），則對任一結(jié)點i（1in），有 （1）如果i1，則結(jié)點i是二叉樹的根，無雙親；如果i 1，則其雙親PARENT（i）是結(jié)點 i/2*。 （2）如果2in，則結(jié)點i無左孩子（結(jié)點i為葉子結(jié)點）， 否則其左孩子LCHILD（i）是結(jié)點2i。 （3）如果2i1n，則結(jié)點i無右孩子； 否則其右孩子RCHILD（i）是結(jié)點2i+1.

11、/-二叉樹的順序存儲表示- # define define MAX_TREE_SIZE 100 typedeftypedef TElemType SqBiTreeMAX_TREE_SIZE; SqBiTree bt; 上一節(jié)完全二叉樹的十二個結(jié)點的順序存儲為： 上一節(jié)非完全二叉樹的六個結(jié)點的順序存儲 （需7個存儲空間）為： 6.2.3 二叉樹的存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu) 一、順序存儲結(jié)構(gòu)一、順序存儲結(jié)構(gòu) 1 21 23 43 45 65 67 87 89 109 10 11 12 11 12 1 21 23 43 40 5 0 5 6 6 最壞情況最壞情況：深度為k的且只有k個結(jié)點的單支樹需要長

12、度為2k-1的一維數(shù)組。 typedef struct BiTNode TElemType data; struct BiTNode *lchild,*rchild; /左右孩子指針 BiTNode,*BiTree; 二、鏈式存儲結(jié)構(gòu) rchilddatalchild data parent lchild rchild datalchildrchildparent 鏈式存儲結(jié)構(gòu)示例 樹的二叉兩鏈表示。三叉鏈表示略 A B CD G EF A B CD EF G B D A E F G C 0 1 2 3 4 5 6 1 23 45 6 Status CreateBiTree(BiTree /按

13、先序次序輸入二叉樹中結(jié)點的值（一個字符）， 空格字符表示空樹， /構(gòu)造二叉鏈表表示的二叉樹T。 S t a t u s P r e O r d e r T r a v e r s e ( B i T r e e T, Status(*Visit)(TElemType e); /采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù) /先序遍歷二叉樹T，對每個結(jié)點調(diào)用函數(shù)Visit一次且僅一 次。 /一旦Visit( ) 失敗，則操作失敗。 基本操作的函數(shù)原型說明(一) S t a t u s I n O r d e r T r a v e r s e ( B i T r e e T , Sta

14、tus(*Visit)(TElemType e); /采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。 /中序遍歷二叉樹T，一旦Visit( ) 失敗，則操作失敗。 S t a t u s P o s t O r d e r T r a v e r s e ( B i T r e e T, Status(*Visit)(TElemType e); /采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。 /后序遍歷二叉樹T，一旦Visit( ) 失敗，則操作失敗。 S t a t u s L e v e l O r d e r Tr a v e r s e ( B i Tr e e

15、T, Status(*Visit)(TElemType e); /采用二叉鏈表存儲結(jié)構(gòu),Visit是對結(jié)點操作的應(yīng)用函數(shù)。 /層序遍歷二叉樹T，一旦Visit( ) 失敗，則操作失敗。 基本操作的函數(shù)原型說明(二) 6.3.1遍歷二叉樹 如果按某條搜索路徑巡 訪樹中每個結(jié)點，使得每 個結(jié)點均被訪問一次，而 且僅被訪問一次。 6.3遍歷二叉樹和線索二叉樹 A B CD G EF 若二叉樹為空，則空操作； 否則 （1）訪問根結(jié)點； （2）先序遍歷左子樹； （3）先序遍歷右子樹。 A B C D F E G 先序遍歷二叉樹的操作定義為： A B CDG E F Status PreOrderTrav

16、erse(BiTree T, Status(* Visit)(TElemType e) if (T) if (Visit(T-data) if (PreOrderTraverse(T-lchild,Visit) if (PreOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /PreOrderTraverse 先序遍歷二叉樹的遞歸算法 若二叉樹為空，則空操作； 否則 （1）中序遍歷左子樹； （2）訪問根結(jié)點； （3）中序遍歷右子樹。 C B D F A G E 中序遍歷二叉樹的操作定義為： A B CD

17、G E F 中序遍歷二叉樹得: a+b*(c-d)-e/f 中序遍歷二叉樹示例 - + a * e / - f b dc Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (InOrderTraverse(T-lchild,Visit) if (Visit(T-data) if (InOrderTraverse(T-rchild,Visit) return OK; return ERROR; else return OK; /InOrderTraverse 中序遍歷二叉樹的遞歸算法 若二叉樹為空，則空

18、操作；否 則 （1）后序遍歷左子樹； （2）后序遍歷右子樹； （3）訪問根結(jié)點。 C F D B G E A 后序遍歷二叉樹的操作定義為： A B CDG E F Status PostOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if (PostOrderTraverse(T-lchild,Visit) if (PostOrderTraverse(T-rchild,Visit) if (Visit(T-data) return OK; return ERROR; else return OK; /PostOrderTr

19、averse 后序遍歷二叉樹的遞歸算法 Status InOrderTraverse(BiTree T, Status(* Visit) (TElemType e) InitStack(S); Push(S,T); while(!StackEmpty(S) while(GetTop(S,p) Pop(S, p); if (!StackEmpty(S) Pop(S,p); if (!Visite(p-data) return ERROR; Push(S,p-rchild); return OK; /InOrderTraverse 中序遍歷二叉樹的非遞歸算法 C B D F A G E 中 序 遍

20、 歷 二 叉 樹 的 非 遞 歸 算 法 示意圖 A B CDG E F A B C NULL S GetTopdata = ch ; CreateBiTree(T-lchild); CreateBiTree(T-rchild); return OK; /CreateBiTree 構(gòu) 造 二 叉 鏈 表 表 示 的 二 叉 樹 的遞歸算法 構(gòu)造二叉鏈表 A B CD G EF 按下列次序輸入字符按下列次序輸入字符: ABCDEGF (其中其中表示空格字符表示空格字符) 可建立如右圖的二叉鏈表可建立如右圖的二叉鏈表. 遍 歷 是 非 線 性 結(jié) 構(gòu) 的 線 性 化 操 作 保留遍歷過程的順序信息

21、 - 線索二叉樹的表示: 若結(jié)點有左子樹，則其LCHILD域指示其左孩子， 否則令LCHILD域指示其前驅(qū)； 若結(jié)點有右子樹，則其RCHILD域指示其右孩子， 否則令RCHILD域指示其后繼。 6.3.2 線索二叉樹 0 lchild域指示其左孩子 ltag = 1 lchild域指示其前驅(qū) 0 rchild域指示其右孩子 rtag = 1 rchild域指示其后繼 線索二叉樹 線索化 線索鏈表 線索 線索二叉樹結(jié)點的結(jié)構(gòu): datalchildrchildrtagltag 中序線索二叉樹 - + a * e / - f b dc NIL NIL b * 11 + / f 00 e 如何在中序

22、線索二叉樹中找結(jié)點的后繼： rtag = 1時，rchild所指的結(jié)點即為后繼； rtag = 0時，其后繼為遍歷其右子樹時的第一個結(jié)點（最 左下結(jié)點）。 如結(jié)點 “*”的后繼是“c” 。 如何在中序線索二叉樹中找結(jié)點的前驅(qū)： ltag = 1時，lchild所指的結(jié)點即為前驅(qū)； ltag = 0時，其前驅(qū)為遍歷其左子樹時的最后一個結(jié)點 （最右下結(jié)點）。 如根結(jié)點 “-”的前驅(qū)是“d” 。 中序線索二叉樹中 查找結(jié)點的后繼和前驅(qū): 中序線索二叉樹 / 二叉樹的二叉線索存儲表示二叉樹的二叉線索存儲表示 typedef enum Link,Thread PointerTag; /Link=0:指針

23、指針,Thread=1:線索線索 typedef struct BiThrNode TElemType data; struct BiThrNode *lchild,*rchild; /左右孩子指針左右孩子指針 PointerTag LTag,RTag; /左右標左右標 志志 BiThrNode, *BiThrTree; Status InOrderThreading(BiThrTree Thrt-LTag=Link; Thrt-RTag=Thread; /建頭結(jié)點 Thrt-rchild=Thrt; /右指針回指 if (!T)Thrt-lchild=Thrt; /若二叉樹空，則左指針回指

24、else Thrt-lchild=T; pre=Thrt; InThreading(T); /中序遍歷進行中序線索化 pre-rchild=Thrt; pre-RTag=Thread; /最后一個結(jié)點線索化 Thrt-rchild=pre; return OK; /InOrderThreading 中序遍歷二叉樹T，并將其中序線索化: (為了記下遍歷過程中訪問結(jié)點的先后次序，附設(shè)一個全程指針 pre) void InThreading(BiThrTree p) / 一個全程指針pre if (p) InThreading(p-lchild); /左子樹線索化 if (!p-lchild) p-

25、LTag=Thread;p-lchild=pre; /前驅(qū)線索 if (!pre-rchild) pre-RTag=Thread; pre-rchild=p; /后繼線索 pre=p; /保持pre指向p的前驅(qū) InThreading(p-rchild); /右子樹線索化 /InThreading 中序遍歷進行中序線索化 例如: 將下列二叉鏈表改為中序線索鏈表 InfoABCDEFGHIJKLMN Ltag Lchild 24607010012 130000 Rtag Rchild 3500891100014000 1 2 3 4 5 6 7 8 9 10 11 12 13 14 上例樹的形態(tài)

26、 Info LtagLchildRtag Rchild A0203 B0405 C061Thrt D1Thrt12 E0708 F1109 G010011 H1511 I01213 J01317 K17014 L1619 M12110 N11115 Thrt 10 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B DEF C HIG KJ MN L Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit)(TElemType e) / T指向頭結(jié)點，頭結(jié)點的左鏈lchild 指向根結(jié)點， /可參見線索化算法。中序遍歷二

27、叉線索樹T的非遞歸算法， / 對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit. p=T-lchild; /p指向根結(jié)點 while(p!=T) /空樹或遍歷結(jié)束時，p=T while(p-LTag=Link)p=p-lchild;/p尋找最左下結(jié)點 if (!Visit(p-data) return ERROR; /訪問其左子樹為空的結(jié)點 while(p-RTag=Thread Visit(p-data); /訪問后繼結(jié)點 p=p-rchild; return OK; /InOrderTraverse_Thr 中序遍歷二叉線索樹T的非遞歸算法: b用鏈表實現(xiàn)二叉樹的幾種基本操作：初用鏈表實現(xiàn)二叉樹的幾種基本

28、操作：初 始化，遍歷始化，遍歷 b以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編以二叉鏈表作為二叉樹的存儲結(jié)構(gòu)，編 寫以下算法：寫以下算法： b（1）統(tǒng)計二叉樹的葉結(jié)點個數(shù)）統(tǒng)計二叉樹的葉結(jié)點個數(shù) b（2）分別以先序、中序以及后序遍歷）分別以先序、中序以及后序遍歷 二叉樹并輸出二叉樹的節(jié)點二叉樹并輸出二叉樹的節(jié)點 已知一算術(shù)表達式的中綴形式為 A+B*C-D/E， 后綴形式為ABC*+DE/-，其前綴形式為( ) A-A+B*C/DE B. -A+B*CD/E C-+*ABC/DE D. -+A*BC/DE 設(shè)有一表示算術(shù)表達式的二叉樹（見下圖）， 它所表示的算術(shù)表達式是（ ） A. A*B+C/(D*E

29、)+(F-G) B. (A*B+C)/(D*E)+(F-G) C. (A*B+C)/(D*E+（F-G）) D. A*B+C/D*E+F-G EFDG AB / + + * -C * 若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則 度為0的結(jié)點個數(shù)是（ ） A9 B11 C15 D不確定 具有10個葉結(jié)點的二叉樹中有（ ）個度為2的結(jié)點 A8 B9 C10 D1l 一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是 （ ） A 250 B 500 C254 D505 E以上答案都不對 某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為 B,D,C,A,F,G,E 則前序序列

30、是： AE,G,F,A,C,D,B BE,A,C,B,D,G,F CE,A,G,C,F,B,D D上面的都不對 一、雙親表示法（順序存儲） /-樹的雙親表存儲表示-/ #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int parent; /雙親位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n; /結(jié)點數(shù) PTree; 64 樹和森林樹和森林 6.4.1樹的存儲結(jié)構(gòu) 雙親表示法舉例 R A DEF C B GKH R -1 A 0 B 0 C 0

31、 D 1 E 1 F 3 G 6 H 6 K 6 0 1 2 3 4 5 6 7 8 9 數(shù)組下標數(shù)組下標: * 便于涉及雙親的操作；便于涉及雙親的操作； * 求結(jié)點的孩子時需要遍歷整棵樹。求結(jié)點的孩子時需要遍歷整棵樹。 #define MAX_TREE_SIZE 100 typedef struct PTNode TElemType data; int child1; /第1個孩子位置域 int child2; /第2個孩子位置域 . int childd; /第d個孩子位置域 PTNode; typedef struct PTNode nodesMAX_TREE_SIZE; int n;

32、/結(jié)點數(shù) PTree; 6.4.1樹的存儲結(jié)構(gòu) 二、孩子表示法（順序存儲） 孩子表示法舉例 R A DEF C B GKH 0 1 2 3 4 5 6 7 8 9 數(shù)組下標數(shù)組下標: * 便于涉及孩子的操作；求雙親不方便；便于涉及孩子的操作；求雙親不方便； * 采用同構(gòu)的結(jié)點，空間浪費。采用同構(gòu)的結(jié)點，空間浪費。 R 1 A 4 B 0 C 6 D 0 E 0 F 7 G 0 H 0 K 0 2 3 5 0 0 0 0 0 0 0 0 0 8 9 0 0 0 0 0 0 孩子鏈表存儲表示（鏈式存儲） typedef struct CTNode /孩子結(jié)點孩子結(jié)點 int child; stru

33、ct CTNode *next; *ChildPtr; typedef struct TElemType data; ChildPtr firstchild; /孩子鏈表頭指針孩子鏈表頭指針 CTBox; typedef struct CTBox nodesMAX_TREE_SIZE; int n, r; /結(jié)點數(shù)和根的位置結(jié)點數(shù)和根的位置 CTree; 孩子鏈表存儲表示舉例 R A DEF CB GKH 0 1 2 3 4 5 6 7 8 9 數(shù)組下標數(shù)組下標: * 便于涉及孩子的操作；便于涉及孩子的操作； * 求結(jié)點的雙親時不方便。求結(jié)點的雙親時不方便。 R A B / C D / E /

34、 F G / H / K / 1 2 3 / 4 5 / 6 / 7 8 9 / T.nodes ; T.n=10; T.r = 0; 例1: 設(shè)樹T以孩子鏈表為存儲結(jié)構(gòu), 尋找值為x的雙親結(jié)點的算法如下: Status parent(Ctree T, TElemType x) / 當值為當值為x的結(jié)點不存在時返回的結(jié)點不存在時返回-2; / 當值為當值為x的結(jié)點為根結(jié)點時返回的結(jié)點為根結(jié)點時返回-1, / 否則返回否則返回x結(jié)點的雙親結(jié)點的下標值結(jié)點的雙親結(jié)點的下標值. if(T.nodesT.r.data = x) return 1; /值為值為x的結(jié)點為根結(jié)點的結(jié)點為根結(jié)點; for(i

35、=0;ichild.data != x) p = p-next; if(p) return (i); / 找到找到x的雙親結(jié)點的雙親結(jié)點 return 2; / 值為值為x的結(jié)點不存在的結(jié)點不存在 例2: 刪除值為x的結(jié)點的第i棵子樹的算 法delete如下： void deletej(Ctree inext; i = s-child; free(s); deletej(T, i); / 遞歸刪除第遞歸刪除第i號結(jié)點及其子樹號結(jié)點及其子樹 Status delete(Ctree 當值為當值為x的結(jié)點為的結(jié)點為 /葉結(jié)點或無第葉結(jié)點或無第i 棵子樹時返回棵子樹時返回-1, 否則返回否則返回1.

36、for(k=0; k=T.n) return 2; / 值為值為x的結(jié)點不存在的結(jié)點不存在 p= T.nodesk.firstchild; j = 1; if(!p) return 1; / x結(jié)點為葉結(jié)點結(jié)點為葉結(jié)點 if(i=1) / 刪除長子時刪除長子時,特殊處理特殊處理 j =p-child; / 記住要刪除子樹的下標記住要刪除子樹的下標 T.nodesk.firstchild = p-next; free(p); else while(p-next j+; if(ji-1 | !p-next) return 1; / 無第無第i 棵子樹棵子樹 / p指向第指向第i-1 個兒子個兒子

37、j = p-next-child; / 記住要刪除子樹的下標記住要刪除子樹的下標 s = p-next; p-next = s-next; free(s); deletej(T, j); / 遞歸刪除第遞歸刪除第j號結(jié)點及其子樹號結(jié)點及其子樹 return 1; /-樹的二叉鏈表(孩子兄弟)存儲表示- typedef struct CSNode ELemType data; struct CSNode *firstchild,*nextsibling; CSNode, *CSTree; 三.孩子兄弟表示法 -樹的二叉樹表示法(二叉鏈表示法) R A DEF CB GKH R A D E C H

38、 F G B K 孩子兄弟表示法示例：孩子兄弟表示法示例： 如果F=T1,T2, ,Tm是森林,則可按如下規(guī)則轉(zhuǎn) 換成一棵二叉樹B=(root,LB,RB)。 (1)若F為空，即m=0,則B為空樹； (2)若F非空，即m0，則B的根root即為森林 中第一棵樹的根ROOT(T1)； B的左子樹LB是從T1中根結(jié)點的子樹森林 F1=T11,T12, ,T1m1轉(zhuǎn)換而成的二叉樹; 其右子對RB是從森林F=T2,T3, ,Tm 轉(zhuǎn)換 而成的二叉樹. 6.4.2 森林與二叉樹的轉(zhuǎn)換森林與二叉樹的轉(zhuǎn)換 一.森林轉(zhuǎn)換成二叉樹 如果B=(root,LB,RB)是一棵二叉樹,則可按如下規(guī) 則轉(zhuǎn)換成森林F=T1

39、,T2, ,Tm： (1)若B為空，則F為空； (2)若B非空，則F中第一棵樹T1的根ROOT(T1) 即為二叉樹B的根root； T1中的根結(jié)點的子樹森林 F1是由B的左子樹LB 轉(zhuǎn)換而成的森林; F中除T1之外其余樹組成的森林F=T2,T3, ， Tm是由B的右子樹RB轉(zhuǎn)換而成的森林。 二. 二叉樹轉(zhuǎn)換成森林 樹的兩種遍歷方法： 一、先根遍歷： （1）訪問樹的根結(jié)點； （2）依次先根遍歷每棵子樹。 R A D E B C F G H K 二、后根遍歷： （1）依次后根遍歷每棵子樹。 （2）訪問樹的根結(jié)點； D E A B G H K F C R 6.4.3 樹和森林的遍歷樹和森林的遍歷 R

40、 A DEF CB GKH 一、先序遍歷森林： 若森林非空，則 （1）訪問森林中第一棵樹的根結(jié)點； （2）先序遍歷第一棵樹的根結(jié)點的子樹森林； （3）先序遍歷除去第一棵樹之后的森林。 二、中序遍歷森林： 若森林非空，則 （1）中序遍歷第一棵樹的根結(jié)點的子樹森林； （2）訪問森林中第一棵樹的根結(jié)點； （3）中序遍歷除去第一棵樹之后的森林。 森林的兩種遍歷方法： 路徑長度路徑長度: 從樹中一個結(jié)點到另一個結(jié)點之 間的分支構(gòu)成這兩個結(jié)點之間的路徑,路徑上的 分支數(shù)目稱做路徑長度。 樹的路徑長度樹的路徑長度: 樹的路徑長度是從樹根到每一 結(jié)點的路徑長度之和。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度: 樹的帶

41、權(quán)路徑長度為樹中 所有葉子結(jié)點(k)的帶權(quán)路徑長度kk之和, 通常記作： n WPL= kk。 k=1 6.6 赫夫曼樹及其應(yīng)用 6.6.1最優(yōu)二叉樹(赫夫曼樹) 假設(shè)有n個權(quán)值1, 2, , n，試構(gòu)造一 棵有n個葉子結(jié)點的二叉樹,每個葉子結(jié)點帶權(quán) 為i, 則其中： 帶權(quán)路徑長度WPL最小的二叉樹稱做 最優(yōu)二叉樹最優(yōu)二叉樹 或赫夫曼樹赫夫曼樹. 最優(yōu)二叉樹 或赫夫曼(Huffman)樹的定義 例1：下面三棵二叉樹的四個葉子結(jié)點 a,b,c,d的權(quán)值為7、5、2、4 abcd 7 52 4 ab c d 7 5 2 4 cd a b 7 5 2 4 (a)WPL=7x2+5x2+2x2+4x2

42、 = 36 (b)WPL=7x3+5x3+2x1+4x2 = 46 (c)WPL=7x1+5x2+2x2+4x2 = 35 例2 最佳判定方法(p.144) (a)WPL=10 x4+30 x4+40 x3+15x2+5x1=315 (b)WPL=5x3+15x3+40 x2+30 x2+10 x2=220 10 c90 e d 5 15 40 ba 30 60 70 80 N N N N Y Y Y Y Y 10 7090 e c 5 40 15 ba 30 60 d 0),構(gòu)造赫夫曼樹HT,并求出n個 字符的赫夫曼編碼HC. if(n=1) return; m=2*n-1; HT=(Huf

43、fmanTree)malloc(m+1)*sizeof(HTNode); /0號單未用 for(p=HT,i=1;i=n;+i,+p,+w) *p=*w,0,0,0; for(;i=m;+i,+p) *p=0,0,0,0; 求赫夫曼編碼的算法如下: for(i=n+1;i=m;+i) /建赫夫曼樹 /在HT1.i-1選擇parent為0且weight最小的兩個結(jié)點, / 其序號分別為s1和s2. select(HT,i-1,s1,s2); HTs1.parent=i;HTs2.parent=i; HTi.lchild=s1;HTi.rchild=s2; HTi.weight=HTs1.weig

44、ht+HTs2.weight; /-從葉子到根逆向求每個字符的赫夫曼編碼- Hc=(HffmanCode)malloc(n+1*sizeof(char *); /分配n個字符編碼的頭指針向量 cd=(char *)malloc(n*sizeof(char);/分配求編碼的工作空間 cdn-1=/0; /編碼結(jié)束符. 求赫夫曼編碼的算法（續(xù)一）: for(i=1;i=n;+i)/逐個字符求赫夫曼編碼 start=n-1;/編碼結(jié)束符位置 for(c=i,f=HTi;f!=0;c=f,f=Htf.parent) /從葉子至根逆向求編碼 if(HTf.lchild=c) cd-start=0; el

45、se cd-start=1; Hci=(char *)malloc(n-start)*sizeof(char); /為第i個字符編碼分配空間 strcpy(HCi, /從cd復(fù)制編碼(串)到HC free(cd); /釋放工作空間 /HuffanCoding 求赫夫曼編碼的算法（續(xù)二）: /-無棧非遞歸遍歷赫夫曼樹,求赫夫曼編碼 HC=(HuffmanCode)malloc(n+1)*sizeof(char *); p=m;cdlen=0; for(i=1;i=m;+i) HTi.weight=0; /遍歷赫夫曼樹時用作結(jié)點狀態(tài)標志 while(p) if(HTp.weight=o)/向左 Htp.weight=1; if(HTp.lchild!=0)p=HTp.lchild;cdcdlen+=0; else if(HTp.rchild=0)/登記葉子結(jié)點的字符的編碼 HCp=(char *)malloc(cdlen+1) *sizeof(char); cdcdlen=0;strcpy(HCp,cd);/復(fù)制編碼(串) 求赫夫曼編碼的算法如下: else if (HTp.weight=1)/向右 HTp.weight=2; if (HTp.rchild!=0)p=HTp.rchild; cdcdlen+=1; else /HTp.w