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

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

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

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

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

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

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

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

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

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

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

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

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

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

二.二叉樹(shù)ACBED現(xiàn)在是10頁(yè)\一共有51頁(yè)\編輯于星期五現(xiàn)在是11頁(yè)\一共有51頁(yè)\編輯于星期五1.遍歷二叉樹(shù)二叉樹(shù)的遍歷是指按照一定順序，依次訪問(wèn)二叉樹(shù)中所有結(jié)點(diǎn)，并且每個(gè)結(jié)點(diǎn)僅被訪問(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)右子樹(shù)，最后訪問(wèn)根結(jié)點(diǎn)。三.遍歷二叉樹(shù)和線索二叉樹(shù)現(xiàn)在是12頁(yè)\一共有51頁(yè)\編輯于星期五1.遍歷二叉樹(shù)下圖中，以A為根結(jié)點(diǎn)的二叉樹(shù)先根遍歷的結(jié)果為ABDECFGH

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

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

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

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

0 A0

0 G0

0 S1

1 U1

1 T1

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

樹(shù)的存儲(chǔ)結(jié)構(gòu)通常有順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)，分別使用數(shù)組和鏈表來(lái)存儲(chǔ)。四.樹(shù)和森林

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

四.樹(shù)和森林

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

四.樹(shù)和森林

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

四.樹(shù)和森林

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

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

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

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

森林四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

二叉樹(shù)四.樹(shù)和森林

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

（1）增加一個(gè)虛擬根結(jié)點(diǎn)，虛擬根結(jié)點(diǎn)指向二叉樹(shù)的根結(jié)點(diǎn)

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

四.樹(shù)和森林

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

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

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

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

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

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

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

四.樹(shù)和森林

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

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

樹(shù)的路徑長(zhǎng)度：從樹(shù)的根結(jié)點(diǎn)到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。

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

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

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

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

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

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

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

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

T1 T2 T3 T4 T5

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

五.哈夫