4.1樹課件-浙教版高中信息技術(shù)選修1

4.1樹情景導(dǎo)入PART1樹的概念與特性一樹的概念樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合樹在計(jì)算機(jī)領(lǐng)域中也有廣泛應(yīng)用，在編譯系統(tǒng)中，用樹表示源程序的語法結(jié)構(gòu)。在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)，也是各種索引和目錄的主要組織形式。一樹的概念樹是由n（n≧0）個節(jié)點(diǎn)構(gòu)成的一個有限集合以及在該集合上定義的一種節(jié)點(diǎn)關(guān)系。節(jié)點(diǎn)：集合中的元素?？諛洌簄=0的樹。子樹：樹中某個節(jié)點(diǎn)下面的所有節(jié)點(diǎn)所構(gòu)成的樹。邊：一顆具有n個節(jié)點(diǎn)的樹有n-1條邊。二基本術(shù)語·節(jié)點(diǎn)的度：樹的一個節(jié)點(diǎn)所擁有的子樹個數(shù)?！涞亩龋鹤畲蟮墓?jié)點(diǎn)的度。二基本術(shù)語·根節(jié)點(diǎn)：沒有前驅(qū)的節(jié)點(diǎn)?！と~子節(jié)點(diǎn)：度為0的節(jié)點(diǎn)?！し种Ч?jié)點(diǎn)：度不為0的節(jié)點(diǎn)?！じ腹?jié)點(diǎn)或雙親節(jié)點(diǎn)：上端節(jié)點(diǎn)稱為下端節(jié)點(diǎn)的父節(jié)點(diǎn)。·孩子節(jié)點(diǎn)：下端節(jié)點(diǎn)稱為上端節(jié)點(diǎn)的孩子節(jié)點(diǎn)·兄弟節(jié)點(diǎn)：具有同一父節(jié)點(diǎn)的節(jié)點(diǎn)二基本術(shù)語·節(jié)點(diǎn)的層數(shù)：樹中節(jié)點(diǎn)從根開始計(jì)算，根的層數(shù)為1，其他節(jié)點(diǎn)的層數(shù)等于父節(jié)點(diǎn)層數(shù)加1·樹的高度或深度：樹中節(jié)點(diǎn)的最大層數(shù)。根的層數(shù)為1。第1層第2層第3層第4層樹的深度二基本術(shù)語·森林：0個或多個不相交的樹的集合ABC練習(xí)【例1】(1)該樹共有個

節(jié)點(diǎn)，

條邊。(2)根節(jié)點(diǎn)的名稱是

它有

個孩子節(jié)點(diǎn)，節(jié)點(diǎn)E.(選填:是/不是)根節(jié)點(diǎn)的孩子節(jié)點(diǎn).(3)節(jié)點(diǎn)A和節(jié)點(diǎn)B的度分別是

,整棵樹的度是

。(4)該樹的分支節(jié)點(diǎn)的數(shù)量是

，葉子節(jié)點(diǎn)的數(shù)量是

。(5)節(jié)點(diǎn)C的層數(shù)是

，樹的深度是

。(6)節(jié)點(diǎn)D的父節(jié)點(diǎn)是

，兄弟節(jié)點(diǎn)是

，孩子節(jié)點(diǎn)是

。109A3不是3、334623AB、CI、JPART2二叉樹一二叉樹的概念二叉樹是一種特殊的樹，是由n（n≧0）個節(jié)點(diǎn)構(gòu)成的一個有限集合，且各個節(jié)點(diǎn)的度小于或等于2，二叉樹的子樹有左右之分，其次序不能任意顛倒（有序樹）。ABCDEFGHABCDEFGH≠二二叉樹的形態(tài)AABAC(1)空二叉樹(2)只有根節(jié)點(diǎn)的單點(diǎn)樹(3)只有根節(jié)點(diǎn)和左子樹(4)只有根節(jié)點(diǎn)和右子樹ABC(5)左右子樹均非空三特殊二叉樹1.完全二叉樹設(shè)二叉樹的深度為h，除第h層外，其它各層(1～h-1)的結(jié)點(diǎn)數(shù)都達(dá)到最大個數(shù)，第h層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹。ABCDEGHIFJ(1～h-1)層

第h層三特殊二叉樹2.滿二叉樹每一層都是滿的，每個節(jié)點(diǎn)的度要么是2，要么為0，而且所有葉子節(jié)點(diǎn)都在同一層。ABCDEGF練習(xí)【例2】觀察如圖所示的二叉樹示意圖，下列說法正確的是( ）A.這是一棵完全二叉樹B.這是一棵滿二叉樹C.這棵二叉樹的深度是4D.這棵二叉樹的度是4C四二叉樹的性質(zhì)1.二叉樹的第i層上最多有

（i>=1）個節(jié)點(diǎn)。2.深度為h的二叉樹最多有

（h>=1）個節(jié)點(diǎn)。3.在任意一棵二叉樹中，若其葉子節(jié)點(diǎn)的數(shù)量為n0，度為2的節(jié)點(diǎn)數(shù)量為n2，則

。ABCDEGHIFJ

ABCDEGF四二叉樹的性質(zhì)4.具有n個結(jié)點(diǎn)的完全二叉樹的深度

。5.給定n個節(jié)點(diǎn)，能構(gòu)成

種不同的二叉樹。ABCDEGHIFJABCDEGF

練習(xí)【舉一反三1】已知二叉樹T共有10個節(jié)點(diǎn),其中度為1的節(jié)點(diǎn)數(shù)量為3,則葉子節(jié)點(diǎn)數(shù)量為()A.3B.4C.5D.6B練習(xí)【舉一反三2】某棵樹有5個節(jié)點(diǎn),樹的度和深度均為3,請畫出這棵樹所有可能的形態(tài)。練習(xí)【舉一反三3】已知某二叉樹總共有7個節(jié)點(diǎn),其中葉子節(jié)點(diǎn)的個數(shù)為4,葉子節(jié)點(diǎn)的數(shù)據(jù)分別為1,2,3,4;每個雙親節(jié)點(diǎn)的數(shù)據(jù)值均為其孩子節(jié)點(diǎn)數(shù)據(jù)值之和。(1)該二叉樹的深度為

。(2)該二叉樹根節(jié)點(diǎn)的數(shù)據(jù)值為

。(3)若考慮葉子節(jié)點(diǎn)不同的排列情況,則該二叉樹有

種畫法。(4)請畫出2棵符合條件的二叉樹。31024練習(xí)一棵完全二叉樹上有1001個節(jié)點(diǎn)，其中葉子節(jié)點(diǎn)的個數(shù)是（

）A.250B.500C.505D.501D練習(xí)一棵高度為4的完全二叉樹上至少有（

）個節(jié)點(diǎn)A.15B.7C.8D.168PART3哈夫曼樹一哈夫曼樹4382路徑：樹中兩個節(jié)點(diǎn)之間所經(jīng)過的分支路徑長度：一條路徑上的分支數(shù)節(jié)點(diǎn)的權(quán)：給二叉樹中的節(jié)點(diǎn)賦一個值節(jié)點(diǎn)帶權(quán)路徑長度：從根節(jié)點(diǎn)到一個節(jié)點(diǎn)的路徑長度與該節(jié)點(diǎn)的權(quán)值的乘積樹的帶權(quán)路徑長度：一棵樹中所有葉子節(jié)點(diǎn)的帶權(quán)路徑長度之和WPL的公式：最優(yōu)二叉樹：在具有n個帶權(quán)葉子節(jié)點(diǎn)的所有二叉樹中，稱帶權(quán)路徑長度WPL最小的二叉樹為最優(yōu)二叉樹。在最優(yōu)二叉樹中權(quán)值較大的節(jié)點(diǎn)離根節(jié)點(diǎn)較近。

練習(xí)如圖所示三棵樹中哪棵樹