數據結構(java)-第6章樹與二叉樹

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

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

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

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

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

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

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

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

9、：先訪問左子樹，再訪問根結點，最后訪問右子樹。：先訪問左子樹，再訪問根結點，最后訪問右子樹。后根遍歷后根遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結點。：先訪問左子樹，再訪問右子樹，最后訪問根結點。三.遍歷二叉樹和線索二叉樹 NEXT Neusoft1.遍歷二叉樹遍歷二叉樹下圖中，以下圖中，以A為根結點的二叉樹先根遍歷的結果為為根結點的二叉樹先根遍歷的結果為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. 線索二叉樹線索二叉樹 線索二叉樹的結點由線索二叉樹的結點由5個部分組成：數據域、左對象域、右對象域、左標志域、右個部分組成：數據域、左對象域、右對象域、左標志域、右標志域。如圖標志域。如圖6.21為線索二叉樹的結點。為線索二叉樹的結點。（二叉樹不變的，所以各個的標志不變）（二叉樹不變的，所以各個的標志不變）當結點存在左子樹時，左標志域為當結點存在左子樹時，左標志域為

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

12、ft2. 線索二叉樹線索二叉樹 0 A 0 0 G 0 0 S 1 1 U 1 1 T 1 1 K 1 null三.遍歷二叉樹和線索二叉樹 NEXT Neusoft1.樹的存儲結構樹的存儲結構 樹的存儲結構通常有樹的存儲結構通常有順序存儲順序存儲和和鏈式存儲鏈式存儲，分別使用數組和鏈，分別使用數組和鏈表來存儲。表來存儲。四.樹和森林 NEXT Neusoft1.樹的存儲結構樹的存儲結構 四.樹和森林 ACBDGFEHNEXT Neusoft1.樹的存儲結構樹的存儲結構樹的雙親表示法樹的雙親表示法 四.樹和森林 NEXT Neusoft1.樹的存儲結構樹的存儲結構樹的孩子鏈表表示法樹的孩子鏈表表

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

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

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

16、oft3.二叉樹轉換為森林二叉樹轉換為森林 （5）將連線逆時針旋轉，整理成多棵樹并列的森林）將連線逆時針旋轉，整理成多棵樹并列的森林 四.樹和森林 ACBEDNEXT Neusoft4.樹的遍歷樹的遍歷 樹的遍歷樹的遍歷可以分為先根遍歷和后根遍歷。可以分為先根遍歷和后根遍歷。樹的先根遍歷是首先訪問樹的根結點，然后從左至右逐一先序遍歷根的每一棵子樹的先根遍歷是首先訪問樹的根結點，然后從左至右逐一先序遍歷根的每一棵子樹。樹。樹的后根遍歷是首先從左至右逐一后根遍歷樹的每一棵子樹，最后訪問樹的根結樹的后根遍歷是首先從左至右逐一后根遍歷樹的每一棵子樹，最后訪問樹的根結點。點。四.樹和森林 NEXT Ne

17、usoft4.樹的遍歷樹的遍歷 樹的先根遍歷結果為樹的先根遍歷結果為AQWPNSGCVF。樹的后根遍歷結果為樹的后根遍歷結果為WPNQGCSFVA。四.樹和森林 AVQWPFNSCGNEXT Neusoft5.森林的遍歷森林的遍歷 森林的遍歷森林的遍歷也分為先根遍歷和后根遍歷。也分為先根遍歷和后根遍歷。先根遍歷是從左至右對森林中的每一棵樹使用樹的先根遍歷方法逐一進行遍歷。先根遍歷是從左至右對森林中的每一棵樹使用樹的先根遍歷方法逐一進行遍歷。后根遍歷是從左至右對森林中的每一棵樹使用樹的后根遍歷方法逐一進行遍歷。后根遍歷是從左至右對森林中的每一棵樹使用樹的后根遍歷方法逐一進行遍歷。四.樹和森林 N

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

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

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

21、將數據步，將數據W值放入結點內，并將其看作值放入結點內，并將其看作5棵二叉樹棵二叉樹T1,T2,T3,T4,T5。 T1 T2 T3 T4 T5 五.哈夫曼樹及其應用 93751NEXT Neusoft1.哈夫曼樹哈夫曼樹 第第2步，從步，從T中選取權值最小的兩棵二叉樹，中選取權值最小的兩棵二叉樹，T5和和T3組成一棵新的二叉樹組成一棵新的二叉樹 五.哈夫曼樹及其應用 413NEXT Neusoft1.哈夫曼樹哈夫曼樹 第第3步，從步，從T中去掉中去掉T5和和T3，并將第，并將第2步產生的二叉樹放入集合步產生的二叉樹放入集合T中中 五.哈夫曼樹及其應用 947531NEXT Neusoft1.

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

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