數(shù)據(jù)結(jié)構(gòu)樹與二叉樹演示文稿

數(shù)據(jù)結(jié)構(gòu)java樹與二叉樹演示文稿現(xiàn)在是1頁\一共有51頁\編輯于星期五數(shù)據(jù)結(jié)構(gòu)java樹與二叉樹現(xiàn)在是2頁\一共有51頁\編輯于星期五1.樹的定義樹（tree）是由n(n≥0)個有限數(shù)據(jù)元素組成的數(shù)據(jù)集合，其中數(shù)據(jù)元素被稱為結(jié)點。同時，樹還必須滿足以下兩個條件：在樹中有一個特殊的結(jié)點被稱為根結(jié)點，它只有后繼結(jié)點，沒有前驅(qū)結(jié)點。除根結(jié)點以外，其余結(jié)點可以分為m（m≥0）個互不相交的集合T1，T2，…，Tm，其中每一個集合Ti（1≤i≤m）本身又是一棵樹。樹T1，T2，…，Tm稱為根結(jié)點的子樹。一.樹的定義和基本術(shù)語

現(xiàn)在是3頁\一共有51頁\編輯于星期五1.樹的定義一.樹的定義和基本術(shù)語

ACDBFEIGH現(xiàn)在是4頁\一共有51頁\編輯于星期五2.基本術(shù)語1）雙親結(jié)點、子結(jié)點、兄弟結(jié)點

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

現(xiàn)在是5頁\一共有51頁\編輯于星期五2.基本術(shù)語

3）結(jié)點的度結(jié)點的度是結(jié)點所擁有的子樹的棵數(shù)。如圖6.2中，A結(jié)點的度為3；C結(jié)點的度為1；H結(jié)點的度為0；4）樹的度樹的度是指樹中各個結(jié)點度的最大值。如圖6.2中，由于A結(jié)點的度為3，其余結(jié)點的度都小于3，所以圖6.2中樹的度為3。5）結(jié)點的層次約定根結(jié)點的層次為1，其余結(jié)點的層次都是在其雙親結(jié)點層次上加1。如圖6.2中，B結(jié)點的雙親結(jié)點為根結(jié)點A，根結(jié)點A的層次為1，所以B結(jié)點的層次為2；同理，E結(jié)點與F結(jié)點的層次是相同的，都為3。一.樹的定義和基本術(shù)語

現(xiàn)在是6頁\一共有51頁\編輯于星期五2.基本術(shù)語

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

CDBFEIGH現(xiàn)在是7頁\一共有51頁\編輯于星期五1.定義

二叉樹（binarytree）是n(n≥0)個結(jié)點組成的有限集合，并且每個結(jié)點最多有兩棵子樹。當n=0時，二叉樹被稱為空二叉樹二叉樹有以下五種基本形態(tài)：空二叉樹，如圖6.4所示；只有根結(jié)點的二叉樹，如圖6.5所示；只有根結(jié)點和左子樹的二叉樹，如圖6.6所示；只有根結(jié)點和右子樹的二叉樹，如圖6.7所示；有根結(jié)點、左子樹和右子樹的二叉樹，如圖6.8所示；二.二叉樹現(xiàn)在是8頁\一共有51頁\編輯于星期五2.滿二叉樹

滿二叉樹是指除了葉子結(jié)點以外所有結(jié)點都存在左子樹和右子樹，并且所有葉子結(jié)點都在同一層上的二叉樹。下圖是一棵滿二叉樹。

二.二叉樹ACBEDGF現(xiàn)在是9頁\一共有51頁\編輯于星期五3.完全二叉樹

完全二叉樹是指葉子結(jié)點只出現(xiàn)在最下層和次下層，且最下層的葉子結(jié)點集中在樹的左部的二叉樹。下圖是一棵完全二叉樹。

二.二叉樹ACBED現(xiàn)在是10頁\一共有51頁\編輯于星期五現(xiàn)在是11頁\一共有51頁\編輯于星期五1.遍歷二叉樹二叉樹的遍歷是指按照一定順序，依次訪問二叉樹中所有結(jié)點，并且每個結(jié)點僅被訪問一次。

二叉樹的遍歷一般可分為三種次序遍歷，分別是先根遍歷、中根遍歷和后根遍歷。先根遍歷：先訪問根結(jié)點，再訪問左子樹，最后訪問右子樹。中根遍歷：先訪問左子樹，再訪問根結(jié)點，最后訪問右子樹。后根遍歷：先訪問左子樹，再訪問右子樹，最后訪問根結(jié)點。三.遍歷二叉樹和線索二叉樹現(xiàn)在是12頁\一共有51頁\編輯于星期五1.遍歷二叉樹下圖中，以A為根結(jié)點的二叉樹先根遍歷的結(jié)果為ABDECFGH

ACBDGFEH三.遍歷二叉樹和線索二叉樹現(xiàn)在是13頁\一共有51頁\編輯于星期五1.遍歷二叉樹二叉樹先根遍歷代碼publicvoidpreOrder(BinaryTreeNoder){if(r!=null){System.out.print(r.getData()+"");preOrder(r.getLeft());preOrder(r.getRight());}}

三.遍歷二叉樹和線索二叉樹現(xiàn)在是14頁\一共有51頁\編輯于星期五2.線索二叉樹

線索二叉樹的結(jié)點由5個部分組成：數(shù)據(jù)域、左對象域、右對象域、左標志域、右標志域。如圖6.21為線索二叉樹的結(jié)點。（二叉樹不變的，所以各個的標志不變）當結(jié)點存在左子樹時，左標志域為0，左對象域指向其左子樹；當結(jié)點不存在左子樹時，左標志域為1，左對象域指向該結(jié)點的前驅(qū)結(jié)點；(指遍歷的)當結(jié)點存在右子樹時，右標志域為0，右對象域指向其右孩子；當結(jié)點不存在右子樹時，右標志域為1，右對象域指向該結(jié)點的后繼結(jié)點；(指遍歷的)三.遍歷二叉樹和線索二叉樹現(xiàn)在是15頁\一共有51頁\編輯于星期五2.線索二叉樹

ASGKUT三.遍歷二叉樹和線索二叉樹現(xiàn)在是16頁\一共有51頁\編輯于星期五2.線索二叉樹

0 A0

0 G0

0 S1

1 U1

1 T1

1 K1null三.遍歷二叉樹和線索二叉樹現(xiàn)在是17頁\一共有51頁\編輯于星期五1.樹的存儲結(jié)構(gòu)

樹的存儲結(jié)構(gòu)通常有順序存儲和鏈式存儲，分別使用數(shù)組和鏈表來存儲。四.樹和森林

現(xiàn)在是18頁\一共有51頁\編輯于星期五1.樹的存儲結(jié)構(gòu)

四.樹和森林

ACBDGFEH現(xiàn)在是19頁\一共有51頁\編輯于星期五1.樹的存儲結(jié)構(gòu)樹的雙親表示法

四.樹和森林

現(xiàn)在是20頁\一共有51頁\編輯于星期五1.樹的存儲結(jié)構(gòu)樹的孩子鏈表表示法

四.樹和森林

現(xiàn)在是21頁\一共有51頁\編輯于星期五2.樹轉(zhuǎn)換為二叉樹（1）加線四.樹和森林

ACBDGFEH現(xiàn)在是22頁\一共有51頁\編輯于星期五2.樹轉(zhuǎn)換為二叉樹（2）抹線四.樹和森林

ACBDGFEH現(xiàn)在是23頁\一共有51頁\編輯于星期五2.樹轉(zhuǎn)換為二叉樹（3）旋轉(zhuǎn)四.樹和森林

ACBDGFEH現(xiàn)在是24頁\一共有51頁\編輯于星期五2.森林轉(zhuǎn)換為二叉樹

森林四.樹和森林

CBDGFEH現(xiàn)在是25頁\一共有51頁\編輯于星期五2.森林轉(zhuǎn)換為二叉樹

（1）在森林最上層增加一個虛擬結(jié)點，并讓該結(jié)點指向森林中每棵樹的根結(jié)點

四.樹和森林

CBDGFEHX現(xiàn)在是26頁\一共有51頁\編輯于星期五2.森林轉(zhuǎn)換為二叉樹

（2）將樹轉(zhuǎn)換為二叉樹

四.樹和森林

CBDGFEHX現(xiàn)在是27頁\一共有51頁\編輯于星期五2.森林轉(zhuǎn)換為二叉樹

（3）去掉根結(jié)點后，該二叉樹即為森林轉(zhuǎn)換成的二叉樹

四.樹和森林

CBDGFEH現(xiàn)在是28頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

二叉樹四.樹和森林

ACBED現(xiàn)在是29頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

（1）增加一個虛擬根結(jié)點，虛擬根結(jié)點指向二叉樹的根結(jié)點

四.樹和森林

ACBEDX現(xiàn)在是30頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

（2）每個結(jié)點與其左孩子增加一條連線，結(jié)點與其左孩子的所有右孩子各增加一條連線

四.樹和森林

ACBEDX現(xiàn)在是31頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

（3）去掉每個結(jié)點之間原有連線。

四.樹和森林

ACBEDX現(xiàn)在是32頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

（4）去掉虛擬根結(jié)點

四.樹和森林

ACBED現(xiàn)在是33頁\一共有51頁\編輯于星期五3.二叉樹轉(zhuǎn)換為森林

（5）將連線逆時針旋轉(zhuǎn)，整理成多棵樹并列的森林

四.樹和森林

ACBED現(xiàn)在是34頁\一共有51頁\編輯于星期五4.樹的遍歷

樹的遍歷可以分為先根遍歷和后根遍歷。 樹的先根遍歷是首先訪問樹的根結(jié)點，然后從左至右逐一先序遍歷根的每一棵子樹。 樹的后根遍歷是首先從左至右逐一后根遍歷樹的每一棵子樹，最后訪問樹的根結(jié)點。四.樹和森林

現(xiàn)在是35頁\一共有51頁\編輯于星期五4.樹的遍歷

樹的先根遍歷結(jié)果為AQWPNSGCVF。樹的后根遍歷結(jié)果為WPNQGCSFVA。四.樹和森林

AVQWPFNSCG現(xiàn)在是36頁\一共有51頁\編輯于星期五5.森林的遍歷

森林的遍歷也分為先根遍歷和后根遍歷。 先根遍歷是從左至右對森林中的每一棵樹使用樹的先根遍歷方法逐一進行遍歷。 后根遍歷是從左至右對森林中的每一棵樹使用樹的后根遍歷方法逐一進行遍歷。四.樹和森林

現(xiàn)在是37頁\一共有51頁\編輯于星期五5.森林的遍歷森林的先根遍歷結(jié)果為：BDGEHCF。

四.樹和森林

CBDGFEH現(xiàn)在是38頁\一共有51頁\編輯于星期五1.哈夫曼樹

權(quán)值：賦予結(jié)點一個有意義的數(shù)字。

樹的路徑長度：從樹的根結(jié)點到每個結(jié)點的路徑長度之和。

結(jié)點的帶權(quán)路徑長度：結(jié)點到樹根結(jié)點之間的路徑長度與結(jié)點權(quán)值乘積。

樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和，通常記為WPL。五.哈夫曼樹及其應(yīng)用

現(xiàn)在是39頁\一共有51頁\編輯于星期五1.哈夫曼樹

哈夫曼樹就是由具有權(quán)值的葉子結(jié)點組成的帶權(quán)路徑長度（WPL）最小的二叉樹。哈夫曼算法的基本思想：1）對于給定n個數(shù)據(jù)W{w1,w2,…,wn},將其分別放入n個結(jié)點內(nèi)，并將這n個結(jié)點分別看作n棵二叉樹，表示為T={T1,T2,…,Tn,}。2）從T中選取根結(jié)點權(quán)值最小的兩棵二叉樹組成一棵新的二叉樹，并分別作為新二叉樹的左右子樹，新二叉樹根結(jié)點的權(quán)值為左右子樹根結(jié)點權(quán)值之和。3）從T中刪除第2步所使用的兩棵二叉樹，并將第2步所產(chǎn)生的二叉樹加入到T中。4）重復(fù)第2步與第3步，直到T中只有一棵二叉樹為止，這棵二叉樹就是數(shù)據(jù)W的哈夫曼樹。五.哈夫曼樹及其應(yīng)用

現(xiàn)在是40頁\一共有51頁\編輯于星期五1.哈夫曼樹

五.哈夫曼樹及其應(yīng)用

3597現(xiàn)在是41頁\一共有51頁\編輯于星期五1.哈夫曼樹

第1步，將數(shù)據(jù)W值放入結(jié)點內(nèi)，并將其看作5棵二叉樹{T1,T2,T3,T4,T5}。

T1 T2 T3 T4 T5

五.哈夫曼樹及其應(yīng)用

93751現(xiàn)在是42頁\一共有51頁\編輯于星期五1.哈夫曼樹

第2步，從T中選取權(quán)值最小的兩棵二叉樹，T5和T3組成一棵新的二叉樹

五.哈夫曼樹及其應(yīng)用

413現(xiàn)在是43頁\一共有51頁\編輯于星期五1.哈夫曼樹

第3步，從T中去掉T5和T3，并將第2步產(chǎn)生的二叉樹放入集合T中

五.哈夫曼樹及其應(yīng)用

947531現(xiàn)在是44頁\一共有51頁\編輯于星期五1.哈夫曼樹

第4步，從新集合T中選出兩個根結(jié)點最小的二叉樹，組成新的二叉樹

五.哈夫曼樹及其應(yīng)用

45319現(xiàn)在是45頁\一共有51頁\編輯于星期五1.哈夫曼樹

第5步，從T中去掉根結(jié)點權(quán)值為4和根結(jié)點權(quán)值為5的兩棵二叉樹，并將第4步產(chǎn)生的二叉樹放入集合T中

五.哈夫曼樹及其應(yīng)用

9745319現(xiàn)在是46頁\一共有51頁\編輯于星期五1.哈夫曼樹

第6步，從新集合T中選出兩個根結(jié)點最小的二叉樹，組成新的二叉樹

五.哈夫