數(shù)據(jù)結(jié)構(gòu)(java)-第6章樹(shù)與二叉樹(shù)

1、基本內(nèi)容1.樹(shù)的定義和基本術(shù)語(yǔ)樹(shù)的定義和基本術(shù)語(yǔ) 第第6章章 樹(shù)與二叉樹(shù)樹(shù)與二叉樹(shù) 2.二叉樹(shù)二叉樹(shù) 3.遍歷二叉樹(shù)和線索二叉樹(shù)遍歷二叉樹(shù)和線索二叉樹(shù) 4.樹(shù)和森林樹(shù)和森林 5.哈夫曼樹(shù)及其應(yīng)用哈夫曼樹(shù)及其應(yīng)用 NEXT Neusoft1.樹(shù)的定義樹(shù)的定義樹(shù)（樹(shù)（tree）是由）是由n(n0)個(gè)有限數(shù)據(jù)元素組成的數(shù)據(jù)集合，其中個(gè)有限數(shù)據(jù)元素組成的數(shù)據(jù)集合，其中數(shù)據(jù)元素被稱(chēng)為結(jié)點(diǎn)。同時(shí)，樹(shù)還必須滿(mǎn)足以下數(shù)據(jù)元素被稱(chēng)為結(jié)點(diǎn)。同時(shí)，樹(shù)還必須滿(mǎn)足以下兩個(gè)條件兩個(gè)條件： 在樹(shù)中有一個(gè)特殊的結(jié)點(diǎn)被稱(chēng)為根結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，在樹(shù)中有一個(gè)特殊的結(jié)點(diǎn)被稱(chēng)為根結(jié)點(diǎn)，它只有后繼結(jié)點(diǎn)，沒(méi)有前驅(qū)結(jié)點(diǎn)。沒(méi)有前驅(qū)結(jié)點(diǎn)。1

2、. 除根結(jié)點(diǎn)以外，其余結(jié)點(diǎn)可以分為除根結(jié)點(diǎn)以外，其余結(jié)點(diǎn)可以分為m（m0）個(gè)互不相交的）個(gè)互不相交的集合集合T1，T2，Tm，其中每一個(gè)集合，其中每一個(gè)集合Ti（1im）本身）本身又是一棵樹(shù)。樹(shù)又是一棵樹(shù)。樹(shù)T1，T2，Tm稱(chēng)為根結(jié)點(diǎn)的子樹(shù)。稱(chēng)為根結(jié)點(diǎn)的子樹(shù)。一.樹(shù)的定義和基本術(shù)語(yǔ) NEXT Neusoft1.樹(shù)的定義樹(shù)的定義一.樹(shù)的定義和基本術(shù)語(yǔ) ACDBFEIGHNEXT Neusoft2. 基本術(shù)語(yǔ)基本術(shù)語(yǔ) 1）雙親結(jié)點(diǎn)、子結(jié)點(diǎn)、兄弟結(jié)點(diǎn)雙親結(jié)點(diǎn)、子結(jié)點(diǎn)、兄弟結(jié)點(diǎn) 如圖如圖6.2中，中，B結(jié)點(diǎn)為結(jié)點(diǎn)為E結(jié)點(diǎn)的雙親結(jié)點(diǎn)；結(jié)點(diǎn)的雙親結(jié)點(diǎn)；A結(jié)點(diǎn)為結(jié)點(diǎn)為D結(jié)點(diǎn)的雙親結(jié)點(diǎn)；結(jié)點(diǎn)的雙親結(jié)點(diǎn)；D結(jié)點(diǎn)

3、結(jié)點(diǎn)為為I結(jié)點(diǎn)的雙親結(jié)點(diǎn)結(jié)點(diǎn)的雙親結(jié)點(diǎn) 如圖如圖6.2中，中，E結(jié)點(diǎn)為結(jié)點(diǎn)為B結(jié)點(diǎn)的子結(jié)點(diǎn)；結(jié)點(diǎn)的子結(jié)點(diǎn)；D結(jié)點(diǎn)為結(jié)點(diǎn)為A結(jié)點(diǎn)的子結(jié)點(diǎn)；結(jié)點(diǎn)的子結(jié)點(diǎn)；H結(jié)點(diǎn)為結(jié)點(diǎn)為D結(jié)點(diǎn)的子結(jié)點(diǎn)結(jié)點(diǎn)的子結(jié)點(diǎn) 如圖如圖6.2中，中，B結(jié)點(diǎn)和結(jié)點(diǎn)和C、D結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)；結(jié)點(diǎn)結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)；結(jié)點(diǎn)G和和H不為兄弟結(jié)點(diǎn)。不為兄弟結(jié)點(diǎn)。 2）葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)，如圖沒(méi)有后繼的結(jié)點(diǎn)稱(chēng)為葉子結(jié)點(diǎn)，如圖6.2中的中的E、F、G、H、I結(jié)點(diǎn)。結(jié)點(diǎn)。一.樹(shù)的定義和基本術(shù)語(yǔ) NEXT Neusoft2. 基本術(shù)語(yǔ)基本術(shù)語(yǔ) 3）結(jié)點(diǎn)的度結(jié)點(diǎn)的度結(jié)點(diǎn)的度是結(jié)點(diǎn)所擁有的子樹(shù)的棵數(shù)。如圖結(jié)點(diǎn)的度是結(jié)點(diǎn)所擁有的子樹(shù)

4、的棵數(shù)。如圖6.2中，中，A結(jié)點(diǎn)的度為結(jié)點(diǎn)的度為3；C結(jié)點(diǎn)結(jié)點(diǎn)的度為的度為1；H結(jié)點(diǎn)的度為結(jié)點(diǎn)的度為0；4）樹(shù)的度樹(shù)的度樹(shù)的度是指樹(shù)中各個(gè)結(jié)點(diǎn)度的最大值。如圖樹(shù)的度是指樹(shù)中各個(gè)結(jié)點(diǎn)度的最大值。如圖6.2中，由于中，由于A結(jié)點(diǎn)的度為結(jié)點(diǎn)的度為3，其，其余結(jié)點(diǎn)的度都小于余結(jié)點(diǎn)的度都小于3，所以圖，所以圖6.2中樹(shù)的度為中樹(shù)的度為3。5）結(jié)點(diǎn)的層次結(jié)點(diǎn)的層次約定根結(jié)點(diǎn)的層次為約定根結(jié)點(diǎn)的層次為1，其余結(jié)點(diǎn)的層次都是在其雙親結(jié)點(diǎn)層次上加，其余結(jié)點(diǎn)的層次都是在其雙親結(jié)點(diǎn)層次上加1。如。如圖圖6.2中，中，B結(jié)點(diǎn)的雙親結(jié)點(diǎn)為根結(jié)點(diǎn)結(jié)點(diǎn)的雙親結(jié)點(diǎn)為根結(jié)點(diǎn)A，根結(jié)點(diǎn)，根結(jié)點(diǎn)A的層次為的層次為1，所以，所以B結(jié)

5、結(jié)點(diǎn)的層次為點(diǎn)的層次為2；同理，；同理，E結(jié)點(diǎn)與結(jié)點(diǎn)與F結(jié)點(diǎn)的層次是相同的，都為結(jié)點(diǎn)的層次是相同的，都為3。一.樹(shù)的定義和基本術(shù)語(yǔ) NEXT Neusoft2. 基本術(shù)語(yǔ)基本術(shù)語(yǔ) 6）樹(shù)的高度樹(shù)的高度樹(shù)的高度是指樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。如圖樹(shù)的高度是指樹(shù)中結(jié)點(diǎn)的最大層次數(shù)。如圖6.2中，由于結(jié)點(diǎn)中，由于結(jié)點(diǎn)E、F、G、H、I的層次數(shù)都為的層次數(shù)都為3，其余結(jié)點(diǎn)的層次數(shù)都小于，其余結(jié)點(diǎn)的層次數(shù)都小于3，所以圖，所以圖6.2中樹(shù)的高度為中樹(shù)的高度為3。7）森林森林森林是森林是m（m0）棵互不相交的樹(shù)的集合。如圖）棵互不相交的樹(shù)的集合。如圖6.3即為一個(gè)森林。即為一個(gè)森林。一.樹(shù)的定義和基本術(shù)語(yǔ) CD

6、BFEIGHNEXT Neusoft1.定義定義 二叉樹(shù)二叉樹(shù)（binary tree）是）是n(n0)個(gè)結(jié)點(diǎn)組成的有限集合，并且每個(gè)結(jié)點(diǎn)最個(gè)結(jié)點(diǎn)組成的有限集合，并且每個(gè)結(jié)點(diǎn)最多有兩棵子樹(shù)。多有兩棵子樹(shù)。當(dāng)當(dāng)n=0時(shí)，二叉樹(shù)被稱(chēng)為空二叉樹(shù)時(shí)，二叉樹(shù)被稱(chēng)為空二叉樹(shù) 二叉樹(shù)有以下五種基本形態(tài)：二叉樹(shù)有以下五種基本形態(tài)：空二叉樹(shù)，如圖空二叉樹(shù)，如圖6.4所示；所示；只有根結(jié)點(diǎn)的二叉樹(shù)，如圖只有根結(jié)點(diǎn)的二叉樹(shù)，如圖6.5所示；所示；只有根結(jié)點(diǎn)和左子樹(shù)的二叉樹(shù)，如圖只有根結(jié)點(diǎn)和左子樹(shù)的二叉樹(shù)，如圖6.6所示；所示；只有根結(jié)點(diǎn)和右子樹(shù)的二叉樹(shù)，如圖只有根結(jié)點(diǎn)和右子樹(shù)的二叉樹(shù)，如圖6.7所示；所示；有根結(jié)點(diǎn)

7、、左子樹(shù)和右子樹(shù)的二叉樹(shù)，如圖有根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)的二叉樹(shù)，如圖6.8所示；所示；二.二叉樹(shù)NEXT Neusoft2.滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù) 滿(mǎn)二叉樹(shù)滿(mǎn)二叉樹(shù)是指除了葉子結(jié)點(diǎn)以外所有結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有是指除了葉子結(jié)點(diǎn)以外所有結(jié)點(diǎn)都存在左子樹(shù)和右子樹(shù)，并且所有葉子結(jié)點(diǎn)都在同一層上的二叉樹(shù)。下圖是一棵滿(mǎn)二叉樹(shù)。葉子結(jié)點(diǎn)都在同一層上的二叉樹(shù)。下圖是一棵滿(mǎn)二叉樹(shù)。 二.二叉樹(shù)ACBEDGFNEXT Neusoft3.完全二叉樹(shù)完全二叉樹(shù) 完全二叉樹(shù)完全二叉樹(shù)是指葉子結(jié)點(diǎn)只出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集是指葉子結(jié)點(diǎn)只出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點(diǎn)集中在樹(shù)的左部的二叉

8、樹(shù)。下圖是一棵完全二叉樹(shù)。中在樹(shù)的左部的二叉樹(shù)。下圖是一棵完全二叉樹(shù)。 二.二叉樹(shù)ACBEDNEXT NeusoftNEXT Neusoft1.遍歷二叉樹(shù)遍歷二叉樹(shù)二叉樹(shù)的遍歷二叉樹(shù)的遍歷是指按照一定順序，依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，并且每個(gè)結(jié)是指按照一定順序，依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(wèn)一次。點(diǎn)僅被訪問(wèn)一次。二叉樹(shù)的遍歷一般可分為二叉樹(shù)的遍歷一般可分為三種次序遍歷三種次序遍歷，分別是先根遍歷、中根遍歷和后根，分別是先根遍歷、中根遍歷和后根遍歷。遍歷。先根遍歷先根遍歷：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。：先訪問(wèn)根結(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)。中根遍歷中根遍歷：先

9、訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。：先訪問(wèn)左子樹(shù)，再訪問(wèn)根結(jié)點(diǎn)，最后訪問(wèn)右子樹(shù)。后根遍歷后根遍歷：先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。：先訪問(wèn)左子樹(shù)，再訪問(wèn)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft1.遍歷二叉樹(shù)遍歷二叉樹(shù)下圖中，以下圖中，以A為根結(jié)點(diǎn)的二叉樹(shù)先根遍歷的結(jié)果為為根結(jié)點(diǎn)的二叉樹(shù)先根遍歷的結(jié)果為ABDECFGH ACBDGFEH三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft1.遍歷二叉樹(shù)遍歷二叉樹(shù)二叉樹(shù)先根遍歷代碼二叉樹(shù)先根遍歷代碼public void preOrder(BinaryTreeNode r) if (r !=

10、null) System.out.print(r.getData() + ); preOrder(r.getLeft(); preOrder(r.getRight(); 三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft2. 線索二叉樹(shù)線索二叉樹(shù) 線索二叉樹(shù)的結(jié)點(diǎn)由線索二叉樹(shù)的結(jié)點(diǎn)由5個(gè)部分組成：數(shù)據(jù)域、左對(duì)象域、右對(duì)象域、左標(biāo)志域、右標(biāo)個(gè)部分組成：數(shù)據(jù)域、左對(duì)象域、右對(duì)象域、左標(biāo)志域、右標(biāo)志域。如圖志域。如圖6.21為線索二叉樹(shù)的結(jié)點(diǎn)。為線索二叉樹(shù)的結(jié)點(diǎn)。（二叉樹(shù)不變的，所以各個(gè)的標(biāo)志不變）（二叉樹(shù)不變的，所以各個(gè)的標(biāo)志不變）當(dāng)結(jié)點(diǎn)存在左子樹(shù)時(shí)，左標(biāo)志域?yàn)楫?dāng)結(jié)點(diǎn)存在左子樹(shù)時(shí)，左標(biāo)志域?yàn)?，

11、左對(duì)象域指向其左子樹(shù)；，左對(duì)象域指向其左子樹(shù)；當(dāng)結(jié)點(diǎn)不存在左子樹(shù)時(shí)，左標(biāo)志域?yàn)楫?dāng)結(jié)點(diǎn)不存在左子樹(shù)時(shí)，左標(biāo)志域?yàn)?，左對(duì)象域指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；，左對(duì)象域指向該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；(指遍歷指遍歷的的)當(dāng)結(jié)點(diǎn)存在右子樹(shù)時(shí)，右標(biāo)志域?yàn)楫?dāng)結(jié)點(diǎn)存在右子樹(shù)時(shí)，右標(biāo)志域?yàn)?，右對(duì)象域指向其右孩子；，右對(duì)象域指向其右孩子；當(dāng)結(jié)點(diǎn)不存在右子樹(shù)時(shí)，右標(biāo)志域?yàn)楫?dāng)結(jié)點(diǎn)不存在右子樹(shù)時(shí)，右標(biāo)志域?yàn)?，右對(duì)象域指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)；，右對(duì)象域指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)；(指遍歷指遍歷的的)三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft2. 線索二叉樹(shù)線索二叉樹(shù) ASGKUT三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft

12、2. 線索二叉樹(shù)線索二叉樹(shù) 0 A 0 0 G 0 0 S 1 1 U 1 1 T 1 1 K 1 null三.遍歷二叉樹(shù)和線索二叉樹(shù) NEXT Neusoft1.樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu) 樹(shù)的存儲(chǔ)結(jié)構(gòu)通常有樹(shù)的存儲(chǔ)結(jié)構(gòu)通常有順序存儲(chǔ)順序存儲(chǔ)和和鏈?zhǔn)酱鎯?chǔ)鏈?zhǔn)酱鎯?chǔ)，分別使用數(shù)組和鏈，分別使用數(shù)組和鏈表來(lái)存儲(chǔ)。表來(lái)存儲(chǔ)。四.樹(shù)和森林 NEXT Neusoft1.樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu) 四.樹(shù)和森林 ACBDGFEHNEXT Neusoft1.樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的雙親表示法樹(shù)的雙親表示法 四.樹(shù)和森林 NEXT Neusoft1.樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的存儲(chǔ)結(jié)構(gòu)樹(shù)的孩子鏈表表示法樹(shù)的孩子鏈表表示法

13、 四.樹(shù)和森林 NEXT Neusoft2.樹(shù)轉(zhuǎn)換為二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù)（1）加線）加線四.樹(shù)和森林 ACBDGFEHNEXT Neusoft2.樹(shù)轉(zhuǎn)換為二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù)（2）抹線）抹線四.樹(shù)和森林 ACBDGFEHNEXT Neusoft2.樹(shù)轉(zhuǎn)換為二叉樹(shù)樹(shù)轉(zhuǎn)換為二叉樹(shù)（3）旋轉(zhuǎn)旋轉(zhuǎn)四.樹(shù)和森林 ACBDGFEHNEXT Neusoft2.森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù) 森林森林四.樹(shù)和森林 CBDGFEHNEXT Neusoft2.森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù) （1）在森林最上層增加一個(gè)虛擬結(jié)點(diǎn)，并讓該結(jié)點(diǎn)指向森林中每棵樹(shù)的根結(jié)點(diǎn)）在森林最上層增加一個(gè)虛擬結(jié)點(diǎn)，并讓該結(jié)點(diǎn)指向森林

14、中每棵樹(shù)的根結(jié)點(diǎn) 四.樹(shù)和森林 CBDGFEHXNEXT Neusoft2.森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù) （2）將樹(shù)轉(zhuǎn)換為二叉樹(shù)）將樹(shù)轉(zhuǎn)換為二叉樹(shù) 四.樹(shù)和森林 CBDGFEHXNEXT Neusoft2.森林轉(zhuǎn)換為二叉樹(shù)森林轉(zhuǎn)換為二叉樹(shù) （3）去掉根結(jié)點(diǎn)后，該二叉樹(shù)即為森林轉(zhuǎn)換成的二叉樹(shù)）去掉根結(jié)點(diǎn)后，該二叉樹(shù)即為森林轉(zhuǎn)換成的二叉樹(shù) 四.樹(shù)和森林 CBDGFEHNEXT Neusoft3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 二叉樹(shù)二叉樹(shù)四.樹(shù)和森林 ACBEDNEXT Neusoft3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 （1）增加一個(gè)虛擬根結(jié)點(diǎn)，虛擬根結(jié)點(diǎn)指向二叉樹(shù)的根結(jié)點(diǎn)）增加一個(gè)虛擬根

15、結(jié)點(diǎn)，虛擬根結(jié)點(diǎn)指向二叉樹(shù)的根結(jié)點(diǎn) 四.樹(shù)和森林 ACBEDXNEXT Neusoft3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 （2）每個(gè)結(jié)點(diǎn)與其左孩子增加一條連線，結(jié)點(diǎn)與其左孩子的所有右孩子各增加一條）每個(gè)結(jié)點(diǎn)與其左孩子增加一條連線，結(jié)點(diǎn)與其左孩子的所有右孩子各增加一條連線連線 四.樹(shù)和森林 ACBEDXNEXT Neusoft3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 （3）去掉每個(gè)結(jié)點(diǎn)之間原有連線。）去掉每個(gè)結(jié)點(diǎn)之間原有連線。 四.樹(shù)和森林 ACBEDXNEXT Neusoft3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 （4）去掉虛擬根結(jié)點(diǎn)）去掉虛擬根結(jié)點(diǎn) 四.樹(shù)和森林 ACBEDNEXT Neusof

16、t3.二叉樹(shù)轉(zhuǎn)換為森林二叉樹(shù)轉(zhuǎn)換為森林 （5）將連線逆時(shí)針旋轉(zhuǎn)，整理成多棵樹(shù)并列的森林）將連線逆時(shí)針旋轉(zhuǎn)，整理成多棵樹(shù)并列的森林 四.樹(shù)和森林 ACBEDNEXT Neusoft4.樹(shù)的遍歷樹(shù)的遍歷 樹(shù)的遍歷樹(shù)的遍歷可以分為先根遍歷和后根遍歷。可以分為先根遍歷和后根遍歷。樹(shù)的先根遍歷是首先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后從左至右逐一先序遍歷根的每一棵子樹(shù)的先根遍歷是首先訪問(wèn)樹(shù)的根結(jié)點(diǎn)，然后從左至右逐一先序遍歷根的每一棵子樹(shù)。樹(shù)。樹(shù)的后根遍歷是首先從左至右逐一后根遍歷樹(shù)的每一棵子樹(shù)，最后訪問(wèn)樹(shù)的根結(jié)樹(shù)的后根遍歷是首先從左至右逐一后根遍歷樹(shù)的每一棵子樹(shù)，最后訪問(wèn)樹(shù)的根結(jié)點(diǎn)。點(diǎn)。四.樹(shù)和森林 NEXT Neus

17、oft4.樹(shù)的遍歷樹(shù)的遍歷 樹(shù)的先根遍歷結(jié)果為樹(shù)的先根遍歷結(jié)果為AQWPNSGCVF。樹(shù)的后根遍歷結(jié)果為樹(shù)的后根遍歷結(jié)果為WPNQGCSFVA。四.樹(shù)和森林 AVQWPFNSCGNEXT Neusoft5.森林的遍歷森林的遍歷 森林的遍歷森林的遍歷也分為先根遍歷和后根遍歷。也分為先根遍歷和后根遍歷。先根遍歷是從左至右對(duì)森林中的每一棵樹(shù)使用樹(shù)的先根遍歷方法逐一進(jìn)行遍歷。先根遍歷是從左至右對(duì)森林中的每一棵樹(shù)使用樹(shù)的先根遍歷方法逐一進(jìn)行遍歷。后根遍歷是從左至右對(duì)森林中的每一棵樹(shù)使用樹(shù)的后根遍歷方法逐一進(jìn)行遍歷。后根遍歷是從左至右對(duì)森林中的每一棵樹(shù)使用樹(shù)的后根遍歷方法逐一進(jìn)行遍歷。四.樹(shù)和森林 NEX

18、T Neusoft5.森林的遍歷森林的遍歷 森林的先根遍歷結(jié)果為：森林的先根遍歷結(jié)果為：BDGEHCF。 四.樹(shù)和森林 CBDGFEHNEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 權(quán)值權(quán)值：賦予結(jié)點(diǎn)一個(gè)有意義的數(shù)字。：賦予結(jié)點(diǎn)一個(gè)有意義的數(shù)字。 樹(shù)的路徑長(zhǎng)度樹(shù)的路徑長(zhǎng)度：從樹(shù)的根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。：從樹(shù)的根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：結(jié)點(diǎn)到樹(shù)根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)權(quán)值乘積。：結(jié)點(diǎn)到樹(shù)根結(jié)點(diǎn)之間的路徑長(zhǎng)度與結(jié)點(diǎn)權(quán)值乘積。 樹(shù)的帶權(quán)路徑長(zhǎng)度樹(shù)的帶權(quán)路徑長(zhǎng)度：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為：樹(shù)中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通

19、常記為WPL。五.哈夫曼樹(shù)及其應(yīng)用 NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 哈夫曼樹(shù)哈夫曼樹(shù)就是由具有權(quán)值的葉子結(jié)點(diǎn)組成的帶權(quán)路徑長(zhǎng)度（就是由具有權(quán)值的葉子結(jié)點(diǎn)組成的帶權(quán)路徑長(zhǎng)度（WPL）最小的二叉樹(shù)。）最小的二叉樹(shù)。哈夫曼算法的基本思想：哈夫曼算法的基本思想：1）對(duì)于給定）對(duì)于給定n個(gè)數(shù)據(jù)個(gè)數(shù)據(jù)Ww1,w2,wn,將其分別放入將其分別放入n個(gè)結(jié)點(diǎn)內(nèi)，并將這個(gè)結(jié)點(diǎn)內(nèi)，并將這n個(gè)結(jié)點(diǎn)分個(gè)結(jié)點(diǎn)分別看作別看作n棵二叉樹(shù)，表示為棵二叉樹(shù)，表示為T(mén)=T1,T2, ,Tn,。2）從）從T中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹(shù)組成一棵新的二叉樹(shù)，并分別作為新二中選取根結(jié)點(diǎn)權(quán)值最小的兩棵二叉樹(shù)組成一棵新的二叉

20、樹(shù)，并分別作為新二叉樹(shù)的左右子樹(shù)，新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。叉樹(shù)的左右子樹(shù)，新二叉樹(shù)根結(jié)點(diǎn)的權(quán)值為左右子樹(shù)根結(jié)點(diǎn)權(quán)值之和。3）從）從T中刪除第中刪除第2步所使用的兩棵二叉樹(shù)，并將第步所使用的兩棵二叉樹(shù)，并將第2步所產(chǎn)生的二叉樹(shù)加入到步所產(chǎn)生的二叉樹(shù)加入到T中。中。4）重復(fù)第）重復(fù)第2步與第步與第3步，直到步，直到T中只有一棵二叉樹(shù)為止，這棵二叉樹(shù)就是數(shù)據(jù)中只有一棵二叉樹(shù)為止，這棵二叉樹(shù)就是數(shù)據(jù)W的哈的哈夫曼樹(shù)。夫曼樹(shù)。五.哈夫曼樹(shù)及其應(yīng)用 NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 五.哈夫曼樹(shù)及其應(yīng)用 3597NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第1步，將數(shù)

21、據(jù)步，將數(shù)據(jù)W值放入結(jié)點(diǎn)內(nèi)，并將其看作值放入結(jié)點(diǎn)內(nèi)，并將其看作5棵二叉樹(shù)棵二叉樹(shù)T1,T2,T3,T4,T5。 T1 T2 T3 T4 T5 五.哈夫曼樹(shù)及其應(yīng)用 93751NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第2步，從步，從T中選取權(quán)值最小的兩棵二叉樹(shù)，中選取權(quán)值最小的兩棵二叉樹(shù)，T5和和T3組成一棵新的二叉樹(shù)組成一棵新的二叉樹(shù) 五.哈夫曼樹(shù)及其應(yīng)用 413NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第3步，從步，從T中去掉中去掉T5和和T3，并將第，并將第2步產(chǎn)生的二叉樹(shù)放入集合步產(chǎn)生的二叉樹(shù)放入集合T中中 五.哈夫曼樹(shù)及其應(yīng)用 947531NEXT Neusoft1.哈夫

22、曼樹(shù)哈夫曼樹(shù) 第第4步，從新集合步，從新集合T中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，組成新的二叉樹(shù)中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，組成新的二叉樹(shù) 五.哈夫曼樹(shù)及其應(yīng)用 45319NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第5步，從步，從T中去掉根結(jié)點(diǎn)權(quán)值為中去掉根結(jié)點(diǎn)權(quán)值為4和根結(jié)點(diǎn)權(quán)值為和根結(jié)點(diǎn)權(quán)值為5的兩棵二叉樹(shù)，并將第的兩棵二叉樹(shù)，并將第4步產(chǎn)步產(chǎn)生的二叉樹(shù)放入集合生的二叉樹(shù)放入集合T中中 五.哈夫曼樹(shù)及其應(yīng)用 9745319NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第6步，從新集合步，從新集合T中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，組成新的二叉樹(shù)中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，組成新的二叉樹(shù)

23、五.哈夫曼樹(shù)及其應(yīng)用 1697NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第7步，從步，從T中去掉根結(jié)點(diǎn)權(quán)值為中去掉根結(jié)點(diǎn)權(quán)值為7和根結(jié)點(diǎn)權(quán)值為和根結(jié)點(diǎn)權(quán)值為9的兩棵二叉樹(shù)，并將第的兩棵二叉樹(shù)，并將第6步產(chǎn)步產(chǎn)生的二叉樹(shù)放入集合生的二叉樹(shù)放入集合T中中 五.哈夫曼樹(shù)及其應(yīng)用 453191697NEXT Neusoft1.哈夫曼樹(shù)哈夫曼樹(shù) 第第8步，從新集合步，從新集合T中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，即根結(jié)點(diǎn)權(quán)值為中選出兩個(gè)根結(jié)點(diǎn)最小的二叉樹(shù)，即根結(jié)點(diǎn)權(quán)值為9和根結(jié)點(diǎn)和根結(jié)點(diǎn)權(quán)值為權(quán)值為16的兩棵二叉樹(shù)，組成新的二叉樹(shù)，并放入集合的兩棵二叉樹(shù)，組成新的二叉樹(shù)，并放入集合T中中 五.哈夫曼樹(shù)及其應(yīng)用 45319169725NEXT Neusof