版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
樹(shù)與二叉樹(shù)01PART認(rèn)識(shí)樹(shù)與二叉樹(shù)Clickheretoaddyourtitle試分析左圖的數(shù)據(jù)結(jié)構(gòu)你是如何確定該數(shù)據(jù)結(jié)構(gòu)的?可從以下概念進(jìn)行分析描述:孩子、父節(jié)點(diǎn)(雙親節(jié)點(diǎn))、兄弟、祖先、子孫樹(shù)的定義:由n(n≥0)個(gè)節(jié)點(diǎn)構(gòu)成的一個(gè)有限集合以及在該集合上定義的一種節(jié)點(diǎn)關(guān)系,集合中的元素稱為樹(shù)的節(jié)點(diǎn),n=0的樹(shù)稱為空樹(shù)。樹(shù)的概念及性質(zhì):(1)對(duì)于一顆具有n個(gè)節(jié)點(diǎn)的樹(shù),它有n-1條邊(2)度:樹(shù)的一個(gè)節(jié)點(diǎn)所擁有的子樹(shù)的個(gè)數(shù),最大結(jié)點(diǎn)的度稱為樹(shù)的度。(3)沒(méi)有前驅(qū)結(jié)點(diǎn)稱為根節(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱為葉節(jié)點(diǎn)(終端節(jié)點(diǎn))(4)樹(shù)中節(jié)點(diǎn)的層數(shù)從根算起,根的層數(shù)為1,其余節(jié)點(diǎn)層數(shù)等于其父節(jié)點(diǎn)的層數(shù)加1,樹(shù)中節(jié)點(diǎn)的最大層數(shù)稱為樹(shù)的高度或深度。練習(xí)分別找出這顆樹(shù)共有多少條邊?樹(shù)的度?樹(shù)的深度?根節(jié)點(diǎn),葉子節(jié)點(diǎn)。C節(jié)點(diǎn)的父節(jié)點(diǎn),兄弟節(jié)點(diǎn),孩子節(jié)點(diǎn)?二叉樹(shù)在猜數(shù)字游戲中,甲方事先在紙上寫出一個(gè)100以內(nèi)的正整數(shù),讓乙方猜,乙方每猜一次,甲方都會(huì)告訴乙方“猜大了”或是“猜小了”,直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字,就一定能夠在7次以內(nèi)猜對(duì)結(jié)果,具體過(guò)程可以抽象成下圖的二叉樹(shù)結(jié)構(gòu)。50251237618314375625668888296小小小小小小小大大大大大大大二叉數(shù)的基本概念二叉樹(shù)是n(n≥0)個(gè)結(jié)點(diǎn)的有限集合:①n=0時(shí),二叉樹(shù)是一棵空樹(shù)。。②當(dāng)n
≠0時(shí),二叉樹(shù)是由一個(gè)根結(jié)點(diǎn)和兩個(gè)互不相交的被稱為根的左子樹(shù)和右子樹(shù)組成。左子樹(shù)和右子樹(shù)又分別是一棵二叉樹(shù)。二叉數(shù)的特點(diǎn)①每個(gè)結(jié)點(diǎn)至多只有兩棵子樹(shù)。②左右子樹(shù)不能顛倒(二叉樹(shù)是有序樹(shù))二叉數(shù)的五種狀態(tài)特殊的二叉樹(shù)—滿二叉樹(shù)滿二叉樹(shù):每一層的節(jié)點(diǎn)數(shù)都達(dá)到最大值特殊的二叉樹(shù)--完全二叉樹(shù)當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)都與高度為h的滿二叉樹(shù)中的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí),稱為完全二叉樹(shù)特點(diǎn):①只有最后兩層可能有葉子結(jié)點(diǎn)②最多只有一個(gè)度為1的結(jié)點(diǎn)特殊的二叉樹(shù)不是完全二叉樹(shù)完全二叉樹(shù)如果某結(jié)點(diǎn)只有一個(gè)孩子,一定是左孩子該二叉樹(shù)是完全二叉樹(shù)嗎?二叉數(shù)的性質(zhì)
第
1
層:20第2層:21第
3
層:22第4層:23二叉數(shù)的性質(zhì)③在任意一棵二叉樹(shù)中,若度為2的節(jié)點(diǎn)數(shù)量為n2,
葉子節(jié)點(diǎn)數(shù)為n0,則n0=n2+1(葉子節(jié)點(diǎn)比分支節(jié)點(diǎn)多一個(gè))哈夫曼樹(shù)特殊的二叉樹(shù)Teshudeerchashu哈夫曼樹(shù)特殊的二叉樹(shù)Teshudeerchashu練一練請(qǐng)從下列三棵二叉樹(shù)中找到最優(yōu)二叉樹(shù)①WPL=2*2+4*2+5*2+8*2=38②WPL=4*2+5*3+8*3+2*1=49
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(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ì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 魯教版五四制六年級(jí)下冊(cè)《Unit 7 Why do you like pandas》2024年同步練習(xí)卷(Section B)
- 2024秋五年級(jí)英語(yǔ)上冊(cè) Module 7 Unit 2 This little girl can't walk第4課時(shí)教案 外研版(三起)
- 2024秋三年級(jí)英語(yǔ)上冊(cè) Module 8 Unit 1 Is it a monster第2課時(shí)教案 外研版(三起)
- 2024工地門衛(wèi)勞動(dòng)合同范本
- 2024秋九年級(jí)英語(yǔ)下冊(cè) Module 6 Eating together Unit 2 Knives and forks are used for most Western food教案(新版)外研版
- 2024秋八年級(jí)英語(yǔ)上冊(cè) Unit 1 Where did you go on vacation Section A (1a-2d)教案(新版)人教新目標(biāo)版
- 2024委托借款合同示范范本
- 2024年五年級(jí)英語(yǔ)下冊(cè) Unit 9 Hes kind to children第1課時(shí)教案 湘少版
- 2024土地轉(zhuǎn)租合同注意事項(xiàng)
- 2024商鋪裝修合同的模板
- 知恩于心,感恩于行!-感恩主題教育
- 第四章模壓成型工藝課件
- 美縫施工合同樣本
- 三年級(jí)上冊(cè)二一位數(shù)乘兩位數(shù)三位數(shù)的乘法西師大版三年級(jí)數(shù)學(xué)上冊(cè)一位數(shù)乘兩位數(shù)(筆算不進(jìn)位)
- SAP 各模塊表邏輯關(guān)系圖詳解
- 合格供應(yīng)商名錄、評(píng)價(jià)表
- DB11T 1630-2019城市綜合管廊工程施工及質(zhì)量驗(yàn)收規(guī)范
- 碧桂園總部、區(qū)域、各公司架構(gòu)
- 教師禮儀培訓(xùn)
- GB/T 4490-2021織物芯輸送帶寬度和長(zhǎng)度
- GB/T 26310.3-2010原鋁生產(chǎn)用煅后石油焦檢測(cè)方法第3部分:表觀油含量的測(cè)定加熱法
評(píng)論
0/150
提交評(píng)論