




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第三部分第三部分 數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)本章內(nèi)容 樹的基本概念 二叉樹的基本概念和性質(zhì) 二叉樹的存儲(chǔ)結(jié)構(gòu) 二叉樹的遍歷 樹、森林與二叉樹的轉(zhuǎn)換 2 210.1 樹的基本概念l 樹:是一類非常重要的非線性結(jié)構(gòu),適合于描述數(shù)據(jù)元素之間的層次關(guān)系。3 3l 樹是n(n0)個(gè)數(shù)據(jù)元素的有限集合T。它滿足以下兩個(gè)條件:P2671.有且僅有一個(gè)特定的稱為根的元素。 一棵樹中,有且僅有一個(gè)根結(jié)點(diǎn)。 根是只有后件沒有前件的結(jié)點(diǎn)。 除根結(jié)點(diǎn)外,其它結(jié)點(diǎn)均有且僅有一個(gè)前件。 每個(gè)結(jié)點(diǎn)均可以有任意多個(gè)后件,沒有后件的結(jié)點(diǎn)稱為葉子結(jié)點(diǎn)。 除根結(jié)點(diǎn)和葉子結(jié)點(diǎn)外,其余稱內(nèi)結(jié)點(diǎn)。2.其余元素分為m(m0)個(gè)互不相交的有限
2、集合T1、T2、Tm,其中每個(gè)集合又都是一棵樹并稱其為根的子樹。數(shù)學(xué)上的定義4 4A AB BE EF FK KL LC CG GMMD DHHNNI IJ JA AB BE EL L5 5樹的常用術(shù)語l 雙親、子女、兄弟、邊: 若結(jié)點(diǎn)y是結(jié)點(diǎn)x的一棵子樹的根,則x稱做y的“雙親”(parents),y稱做x的“子女”(child) 有序?qū)ΨQ做從x到y(tǒng)的“邊”。 具有同一雙親的結(jié)點(diǎn)稱為“兄弟”。l 路徑、路徑長(zhǎng)度: 若樹中存在著一個(gè)結(jié)點(diǎn)的序列k1 k2kj,使ki是ki+1(1i0,則ki雙親結(jié)點(diǎn)的編號(hào)為 (i-1)/2; 若i=0,則ki是根結(jié)點(diǎn)。 若2i+1n,則ki左子女結(jié)點(diǎn)的編號(hào)是2i
3、+1,否則ki無左子女。若2i+2n,則ki右子女結(jié)點(diǎn)的編號(hào)為2i+2,否則ki無右子女。1616二叉樹的存儲(chǔ)結(jié)構(gòu) l 順序存儲(chǔ)結(jié)構(gòu) 對(duì)完全二叉樹,利用性質(zhì)5,將其所有結(jié)點(diǎn)按編號(hào)順序依次存儲(chǔ)在一維數(shù)組里。 對(duì)一般二叉樹,需要加上一些并不存在的“虛結(jié)點(diǎn)”,轉(zhuǎn)換為完全二叉樹的形式。 1717l 二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈接存儲(chǔ)時(shí)結(jié)點(diǎn)的結(jié)構(gòu)lchilddatarchildA AB BC C F F D D E EG GHHrootroot存儲(chǔ)結(jié)構(gòu)邏輯結(jié)構(gòu)1818二叉樹的遍歷l 先序遍歷 :訪問根結(jié)點(diǎn)(D),先序遍歷左子樹(L),先序遍歷右子樹(R)。 ABDGECFl 中序遍歷:LDR DGBEAFCl 后序遍歷:LRD GDEBFCAl 層次遍歷:按層數(shù)由小到大、同一層從左到右順序依次訪問二叉樹的各個(gè)結(jié)點(diǎn)。 ABCDEFG1919樹、森林與二叉樹的轉(zhuǎn)換 l 樹到二叉樹的轉(zhuǎn)換1. 在所有的兄弟之間加一條連線;2. 對(duì)每個(gè)結(jié)點(diǎn),除了保留與最左邊子女的連線外,去掉與其他子女連線;3. 將保留下來的邊作為左子樹的邊,兄弟間的連線作為右子樹的邊。2020l 森林到二叉樹的轉(zhuǎn)換1. 先將森林中的每一棵樹變?yōu)槎鏄洌?. 然后將各二叉樹的根結(jié)點(diǎn)看成兄弟,用線把它們連到一起,3. 經(jīng)整理后可得到相應(yīng)的二叉樹。2121l 二叉樹到樹、森林的
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 山東歷史教研題目及答案
- 2025屆廣東省茂名市高三二模語文試題(解析版)
- 江蘇廣芯源電子科技有限公司年產(chǎn)1000萬片智能手表主板貼片、100萬只智能手表成品項(xiàng)目環(huán)評(píng)資料環(huán)境影響
- 2025年秋三年級(jí)上冊(cè)語文同步教案 4 古詩三首
- 運(yùn)動(dòng)館雙十一活動(dòng)策劃
- 飛機(jī)裝配工藝復(fù)習(xí)題1
- 供水應(yīng)急搶修管理制度
- 第5跖骨基底骨折護(hù)理查房講課件
- 供熱設(shè)施設(shè)備管理制度
- 35千伏電力工程監(jiān)理實(shí)施細(xì)則
- 以DeepSeek為代表的AI在能源行業(yè)的應(yīng)用前景預(yù)測(cè)
- 《錢學(xué)森》介紹課件
- 智慧樹知到《中國近現(xiàn)代史綱要(哈爾濱工程大學(xué))》2025章節(jié)測(cè)試附答案
- 單層泄爆屋面安裝施工方案
- LY/T 3408-2024林下經(jīng)濟(jì)術(shù)語
- 《動(dòng)物藥理》課件 第9章作用于血液循環(huán)系統(tǒng)的藥物
- 信息化建設(shè)項(xiàng)目質(zhì)量控制措施
- 新生兒肺動(dòng)脈高壓個(gè)案護(hù)理匯報(bào)
- CNAS-GL052:2022 電磁兼容檢測(cè)領(lǐng)域設(shè)備期間核查指南
- 校外培訓(xùn)機(jī)構(gòu)安全防范制度
評(píng)論
0/150
提交評(píng)論