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

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

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

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

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

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

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

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

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

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

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

11、左對象域指向其左子樹；，左對象域指向其左子樹；當(dāng)結(jié)點不存在左子樹時，左標(biāo)志域為當(dāng)結(jié)點不存在左子樹時，左標(biāo)志域為1，左對象域指向該結(jié)點的前驅(qū)結(jié)點；，左對象域指向該結(jié)點的前驅(qū)結(jié)點；(指遍歷指遍歷的的)當(dāng)結(jié)點存在右子樹時，右標(biāo)志域為當(dāng)結(jié)點存在右子樹時，右標(biāo)志域為0，右對象域指向其右孩子；，右對象域指向其右孩子；當(dāng)結(jié)點不存在右子樹時，右標(biāo)志域為當(dāng)結(jié)點不存在右子樹時，右標(biāo)志域為1，右對象域指向該結(jié)點的后繼結(jié)點；，右對象域指向該結(jié)點的后繼結(jié)點；(指遍歷指遍歷的的)三.遍歷二叉樹和線索二叉樹 NEXT Neusoft2. 線索二叉樹線索二叉樹 ASGKUT三.遍歷二叉樹和線索二叉樹 NEXT Neusoft

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

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

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

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

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

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

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

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

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

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

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

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