




版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領
文檔簡介
數(shù)據結構java樹與二叉樹演示文稿現(xiàn)在是1頁\一共有51頁\編輯于星期五數(shù)據結構java樹與二叉樹現(xiàn)在是2頁\一共有51頁\編輯于星期五1.樹的定義樹(tree)是由n(n≥0)個有限數(shù)據元素組成的數(shù)據集合,其中數(shù)據元素被稱為結點。同時,樹還必須滿足以下兩個條件:在樹中有一個特殊的結點被稱為根結點,它只有后繼結點,沒有前驅結點。除根結點以外,其余結點可以分為m(m≥0)個互不相交的集合T1,T2,…,Tm,其中每一個集合Ti(1≤i≤m)本身又是一棵樹。樹T1,T2,…,Tm稱為根結點的子樹。一.樹的定義和基本術語
現(xiàn)在是3頁\一共有51頁\編輯于星期五1.樹的定義一.樹的定義和基本術語
ACDBFEIGH現(xiàn)在是4頁\一共有51頁\編輯于星期五2.基本術語1)雙親結點、子結點、兄弟結點
如圖6.2中,B結點為E結點的雙親結點;A結點為D結點的雙親結點;D結點為I結點的雙親結點如圖6.2中,E結點為B結點的子結點;D結點為A結點的子結點;H結點為D結點的子結點如圖6.2中,B結點和C、D結點互為兄弟結點;結點G和H不為兄弟結點。2)葉子結點沒有后繼的結點稱為葉子結點,如圖6.2中的E、F、G、H、I結點。一.樹的定義和基本術語
現(xiàn)在是5頁\一共有51頁\編輯于星期五2.基本術語
3)結點的度結點的度是結點所擁有的子樹的棵數(shù)。如圖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,所以B結點的層次為2;同理,E結點與F結點的層次是相同的,都為3。一.樹的定義和基本術語
現(xiàn)在是6頁\一共有51頁\編輯于星期五2.基本術語
6)樹的高度樹的高度是指樹中結點的最大層次數(shù)。如圖6.2中,由于結點E、F、G、H、I的層次數(shù)都為3,其余結點的層次數(shù)都小于3,所以圖6.2中樹的高度為3。7)森林森林是m(m≥0)棵互不相交的樹的集合。如圖6.3即為一個森林。一.樹的定義和基本術語
CDBFEIGH現(xiàn)在是7頁\一共有51頁\編輯于星期五1.定義
二叉樹(binarytree)是n(n≥0)個結點組成的有限集合,并且每個結點最多有兩棵子樹。當n=0時,二叉樹被稱為空二叉樹二叉樹有以下五種基本形態(tài):空二叉樹,如圖6.4所示;只有根結點的二叉樹,如圖6.5所示;只有根結點和左子樹的二叉樹,如圖6.6所示;只有根結點和右子樹的二叉樹,如圖6.7所示;有根結點、左子樹和右子樹的二叉樹,如圖6.8所示;二.二叉樹現(xiàn)在是8頁\一共有51頁\編輯于星期五2.滿二叉樹
滿二叉樹是指除了葉子結點以外所有結點都存在左子樹和右子樹,并且所有葉子結點都在同一層上的二叉樹。下圖是一棵滿二叉樹。
二.二叉樹ACBEDGF現(xiàn)在是9頁\一共有51頁\編輯于星期五3.完全二叉樹
完全二叉樹是指葉子結點只出現(xiàn)在最下層和次下層,且最下層的葉子結點集中在樹的左部的二叉樹。下圖是一棵完全二叉樹。
二.二叉樹ACBED現(xiàn)在是10頁\一共有51頁\編輯于星期五現(xiàn)在是11頁\一共有51頁\編輯于星期五1.遍歷二叉樹二叉樹的遍歷是指按照一定順序,依次訪問二叉樹中所有結點,并且每個結點僅被訪問一次。
二叉樹的遍歷一般可分為三種次序遍歷,分別是先根遍歷、中根遍歷和后根遍歷。先根遍歷:先訪問根結點,再訪問左子樹,最后訪問右子樹。中根遍歷:先訪問左子樹,再訪問根結點,最后訪問右子樹。后根遍歷:先訪問左子樹,再訪問右子樹,最后訪問根結點。三.遍歷二叉樹和線索二叉樹現(xiàn)在是12頁\一共有51頁\編輯于星期五1.遍歷二叉樹下圖中,以A為根結點的二叉樹先根遍歷的結果為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.線索二叉樹
線索二叉樹的結點由5個部分組成:數(shù)據域、左對象域、右對象域、左標志域、右標志域。如圖6.21為線索二叉樹的結點。(二叉樹不變的,所以各個的標志不變)當結點存在左子樹時,左標志域為0,左對象域指向其左子樹;當結點不存在左子樹時,左標志域為1,左對象域指向該結點的前驅結點;(指遍歷的)當結點存在右子樹時,右標志域為0,右對象域指向其右孩子;當結點不存在右子樹時,右標志域為1,右對象域指向該結點的后繼結點;(指遍歷的)三.遍歷二叉樹和線索二叉樹現(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.樹的存儲結構
樹的存儲結構通常有順序存儲和鏈式存儲,分別使用數(shù)組和鏈表來存儲。四.樹和森林
現(xiàn)在是18頁\一共有51頁\編輯于星期五1.樹的存儲結構
四.樹和森林
ACBDGFEH現(xiàn)在是19頁\一共有51頁\編輯于星期五1.樹的存儲結構樹的雙親表示法
四.樹和森林
現(xiàn)在是20頁\一共有51頁\編輯于星期五1.樹的存儲結構樹的孩子鏈表表示法
四.樹和森林
現(xiàn)在是21頁\一共有51頁\編輯于星期五2.樹轉換為二叉樹(1)加線四.樹和森林
ACBDGFEH現(xiàn)在是22頁\一共有51頁\編輯于星期五2.樹轉換為二叉樹(2)抹線四.樹和森林
ACBDGFEH現(xiàn)在是23頁\一共有51頁\編輯于星期五2.樹轉換為二叉樹(3)旋轉四.樹和森林
ACBDGFEH現(xiàn)在是24頁\一共有51頁\編輯于星期五2.森林轉換為二叉樹
森林四.樹和森林
CBDGFEH現(xiàn)在是25頁\一共有51頁\編輯于星期五2.森林轉換為二叉樹
(1)在森林最上層增加一個虛擬結點,并讓該結點指向森林中每棵樹的根結點
四.樹和森林
CBDGFEHX現(xiàn)在是26頁\一共有51頁\編輯于星期五2.森林轉換為二叉樹
(2)將樹轉換為二叉樹
四.樹和森林
CBDGFEHX現(xiàn)在是27頁\一共有51頁\編輯于星期五2.森林轉換為二叉樹
(3)去掉根結點后,該二叉樹即為森林轉換成的二叉樹
四.樹和森林
CBDGFEH現(xiàn)在是28頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
二叉樹四.樹和森林
ACBED現(xiàn)在是29頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
(1)增加一個虛擬根結點,虛擬根結點指向二叉樹的根結點
四.樹和森林
ACBEDX現(xiàn)在是30頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
(2)每個結點與其左孩子增加一條連線,結點與其左孩子的所有右孩子各增加一條連線
四.樹和森林
ACBEDX現(xiàn)在是31頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
(3)去掉每個結點之間原有連線。
四.樹和森林
ACBEDX現(xiàn)在是32頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
(4)去掉虛擬根結點
四.樹和森林
ACBED現(xiàn)在是33頁\一共有51頁\編輯于星期五3.二叉樹轉換為森林
(5)將連線逆時針旋轉,整理成多棵樹并列的森林
四.樹和森林
ACBED現(xiàn)在是34頁\一共有51頁\編輯于星期五4.樹的遍歷
樹的遍歷可以分為先根遍歷和后根遍歷。 樹的先根遍歷是首先訪問樹的根結點,然后從左至右逐一先序遍歷根的每一棵子樹。 樹的后根遍歷是首先從左至右逐一后根遍歷樹的每一棵子樹,最后訪問樹的根結點。四.樹和森林
現(xiàn)在是35頁\一共有51頁\編輯于星期五4.樹的遍歷
樹的先根遍歷結果為AQWPNSGCVF。樹的后根遍歷結果為WPNQGCSFVA。四.樹和森林
AVQWPFNSCG現(xiàn)在是36頁\一共有51頁\編輯于星期五5.森林的遍歷
森林的遍歷也分為先根遍歷和后根遍歷。 先根遍歷是從左至右對森林中的每一棵樹使用樹的先根遍歷方法逐一進行遍歷。 后根遍歷是從左至右對森林中的每一棵樹使用樹的后根遍歷方法逐一進行遍歷。四.樹和森林
現(xiàn)在是37頁\一共有51頁\編輯于星期五5.森林的遍歷森林的先根遍歷結果為:BDGEHCF。
四.樹和森林
CBDGFEH現(xiàn)在是38頁\一共有51頁\編輯于星期五1.哈夫曼樹
權值:賦予結點一個有意義的數(shù)字。
樹的路徑長度:從樹的根結點到每個結點的路徑長度之和。
結點的帶權路徑長度:結點到樹根結點之間的路徑長度與結點權值乘積。
樹的帶權路徑長度:樹中所有葉子結點的帶權路徑長度之和,通常記為WPL。五.哈夫曼樹及其應用
現(xiàn)在是39頁\一共有51頁\編輯于星期五1.哈夫曼樹
哈夫曼樹就是由具有權值的葉子結點組成的帶權路徑長度(WPL)最小的二叉樹。哈夫曼算法的基本思想:1)對于給定n個數(shù)據W{w1,w2,…,wn},將其分別放入n個結點內,并將這n個結點分別看作n棵二叉樹,表示為T={T1,T2,…,Tn,}。2)從T中選取根結點權值最小的兩棵二叉樹組成一棵新的二叉樹,并分別作為新二叉樹的左右子樹,新二叉樹根結點的權值為左右子樹根結點權值之和。3)從T中刪除第2步所使用的兩棵二叉樹,并將第2步所產生的二叉樹加入到T中。4)重復第2步與第3步,直到T中只有一棵二叉樹為止,這棵二叉樹就是數(shù)據W的哈夫曼樹。五.哈夫曼樹及其應用
現(xiàn)在是40頁\一共有51頁\編輯于星期五1.哈夫曼樹
五.哈夫曼樹及其應用
3597現(xiàn)在是41頁\一共有51頁\編輯于星期五1.哈夫曼樹
第1步,將數(shù)據W值放入結點內,并將其看作5棵二叉樹{T1,T2,T3,T4,T5}。
T1 T2 T3 T4 T5
五.哈夫曼樹及其應用
93751現(xiàn)在是42頁\一共有51頁\編輯于星期五1.哈夫曼樹
第2步,從T中選取權值最小的兩棵二叉樹,T5和T3組成一棵新的二叉樹
五.哈夫曼樹及其應用
413現(xiàn)在是43頁\一共有51頁\編輯于星期五1.哈夫曼樹
第3步,從T中去掉T5和T3,并將第2步產生的二叉樹放入集合T中
五.哈夫曼樹及其應用
947531現(xiàn)在是44頁\一共有51頁\編輯于星期五1.哈夫曼樹
第4步,從新集合T中選出兩個根結點最小的二叉樹,組成新的二叉樹
五.哈夫曼樹及其應用
45319現(xiàn)在是45頁\一共有51頁\編輯于星期五1.哈夫曼樹
第5步,從T中去掉根結點權值為4和根結點權值為5的兩棵二叉樹,并將第4步產生的二叉樹放入集合T中
五.哈夫曼樹及其應用
9745319現(xiàn)在是46頁\一共有51頁\編輯于星期五1.哈夫曼樹
第6步,從新集合T中選出兩個根結點最小的二叉樹,組成新的二叉樹
五.哈夫
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
- 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
- 6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 中國五氧化二釩行業(yè)市場調查報告
- 健康生活遠離疾病課件
- 健康游戲課件幼兒園
- 2025年公用事業(yè)行業(yè)投資策略分析報告:能源轉型開啟降本周期
- 營銷策劃管理崗管理辦法
- 蔡甸區(qū)礦產開采管理辦法
- 蚌埠柴油車管理辦法細則
- 西藏新投資項目管理辦法
- 衢江區(qū)項目報備管理辦法
- 西安養(yǎng)老社會化管理辦法
- 2025年湖北省工業(yè)建筑集團有限公司人員招聘筆試模擬試題附答案詳解
- 四川省金釩科技有限責任公司巴洞鐵礦開采工程環(huán)評報告
- (2025)時政熱點必考題庫(附答案)
- 林地轉租合同協(xié)議書范本
- 審計人員廉潔協(xié)議書
- 共同合作融資服務協(xié)議5篇
- 個人車位租賃合同(含充電樁安裝)
- 防溺水技能培訓課件
- 美的集團數(shù)字化轉型之路
- 執(zhí)業(yè)藥師聘任協(xié)議書
- 部編版六年級下冊語文全冊教案(含教學反思)
評論
0/150
提交評論