樹(shù)與二叉樹(shù)的概念及其性質(zhì)課件浙教版高中信息技術(shù)選修1

樹(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)系，集合中的元素稱(chēng)為樹(shù)的節(jié)點(diǎn)，n=0的樹(shù)稱(chēng)為空樹(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)的度稱(chēng)為樹(shù)的度。（3）沒(méi)有前驅(qū)結(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱(chēng)為葉節(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ù)稱(chēng)為樹(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ù)字游戲中，甲方事先在紙上寫(xiě)出一個(gè)100以?xún)?nèi)的正整數(shù)，讓乙方猜，乙方每猜一次，甲方都會(huì)告訴乙方“猜大了”或是“猜小了”，直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字，就一定能夠在7次以?xún)?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è)互不相交的被稱(chēng)為根的左子樹(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í)，稱(chēng)為完全二叉樹(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