4.1 樹與二叉樹（教學(xué)課件）-高中《信息技術(shù)》選修1數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)同步高效課堂（浙教版）

第1節(jié)

樹與二叉樹（1課時）第4章樹浙教版（2019）

選修一樹01二叉樹02

了解樹、子樹、樹的度、樹的深度等概念。01

通過具體任務(wù)的實踐活動，體驗用樹型結(jié)構(gòu)描述生活中蘊含樹型結(jié)構(gòu)的組織關(guān)系。03

了解二叉樹、滿二叉樹、完全二叉樹等概念。02PART01樹新課導(dǎo)入樹？邏輯上的樹生活中的樹新課導(dǎo)入常見的樹形結(jié)構(gòu)

樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，用它能很好地描述有分支和層次特性的數(shù)據(jù)集合。

樹一

樹形結(jié)構(gòu)在現(xiàn)實世界中廣泛存在公司內(nèi)部管理的組織關(guān)系圖賦值語句的語法樹數(shù)據(jù)庫層次結(jié)構(gòu)圖

樹一

樹（Tree）可以描述為由n（n≥0）個節(jié)點（Node）構(gòu)成的一個有限集合以及在該集合上定義的一種節(jié)點關(guān)系。ACDFBGHEJKLMI第1層第2層第3層第4層樹的示例

樹一

樹

節(jié)點:樹的元素【n=0為空樹】

子樹:樹中某個節(jié)點下面的所有節(jié)點所構(gòu)成的樹

兩個節(jié)點之間存在一條邊?一棵具有n個節(jié)點的樹，它有n-1條邊。子樹第1層第3層第4層第2層※樹中共有13個節(jié)點、12條邊?！?jié)點B、G、H構(gòu)成了節(jié)點A的一棵子樹。

樹一

樹

節(jié)點的度：某節(jié)點擁有的子樹個數(shù)

樹的度：最大的節(jié)點的度第1層第3層第4層第2層※節(jié)點A的度為5，※節(jié)點B的度為2，※節(jié)點I的度為3，因此樹的度為5。線性表(特殊的樹)——度為1節(jié)點的度和樹的度共同體現(xiàn)了樹的寬度(節(jié)點的分支數(shù)和樹的發(fā)散程度)。樹的示例

樹一

第1層第3層第4層第2層樹的示例根節(jié)點（開始節(jié)點）：沒有前驅(qū)的節(jié)點葉子節(jié)點（終端節(jié)點）：度為0分支節(jié)點（非終端節(jié)點）：度不為0內(nèi)部節(jié)點：除根節(jié)點之外的分支節(jié)點父節(jié)點（雙親節(jié)點）：以邊相連的上端節(jié)點孩子節(jié)點：以邊相連的下端節(jié)點兄弟節(jié)點：擁有同一父節(jié)點父節(jié)點根節(jié)點葉子節(jié)點

樹一

第1層第3層第4層第2層樹的高度/深度=4只需知道數(shù)據(jù)之間相互鏈接的順序樹中節(jié)點層數(shù)：根節(jié)點層數(shù)為1，其余節(jié)點層數(shù)等于其父節(jié)點的層數(shù)加1樹的高度/深度=最大層數(shù)

樹一

1線性結(jié)構(gòu)：

必存在著唯一的一個“第一個元素”和唯一的一個“最后的元素”；

除第一個元素以外，其他數(shù)據(jù)元素均有唯一的“前驅(qū)”，除最后元素以外，其他數(shù)據(jù)元素均有唯一的“后繼”。2樹形結(jié)構(gòu)（擁有多個節(jié)點）：非線性結(jié)構(gòu)，

根節(jié)點（無前驅(qū)，有后繼），

葉子節(jié)點（存在多個，沒有后繼，只有前驅(qū)），

其余的節(jié)點都只有一個直接前驅(qū)和多個直接后繼。

樹一

拓展鏈接圖（Graph）

圖狀結(jié)構(gòu)是一種比線性結(jié)構(gòu)和樹形結(jié)構(gòu)更為復(fù)雜的非線性結(jié)構(gòu)，廣泛應(yīng)用于計算機網(wǎng)絡(luò)、通信工程等諸多領(lǐng)域。在線性表中，一個數(shù)據(jù)元素只和它的前驅(qū)和后繼元素有關(guān)系。在樹中，一個節(jié)點只和它的父節(jié)點和孩子節(jié)點有關(guān)系。而在圖中，每個頂點都有可能和其他任意頂點有關(guān)系，這就使得圖的存儲和運算比前兩種數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜。無向圖

有向圖

連通圖

非連通圖

節(jié)點關(guān)系圖

樹一

只需知道數(shù)據(jù)之間相互鏈接的順序探討與討論1.諸葛亮家族的部分家譜如圖所示。和家譜圖結(jié)構(gòu)相似的數(shù)據(jù)結(jié)構(gòu)是(

)AA.樹

B.棧

C.隊列

D.鏈表

二叉樹二

樹的形態(tài)有很多，在實際的使用過程中，需要對樹的形態(tài)進(jìn)一步地進(jìn)行約束和簡化，以便于設(shè)計和操作。二叉樹是樹形結(jié)構(gòu)的一個重要類型，在實際應(yīng)用中，許多問題抽象出來的數(shù)據(jù)結(jié)構(gòu)往往就是二叉樹的形式。樹二叉

二叉樹二

甲方事先在紙上寫出一個100以內(nèi)的正整數(shù)，讓乙方猜，乙方每猜一次，甲方都會告訴乙方“猜大了”或是“猜小了”，直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字，就一定能夠在7次以內(nèi)猜對結(jié)果。猜數(shù)字游戲猜數(shù)字過程的抽象形態(tài)

二叉樹二

每個節(jié)點為乙方所猜的數(shù)字，每條邊為實際數(shù)字與所猜數(shù)字之間的大小關(guān)系，圖中僅呈現(xiàn)前4次的猜數(shù)字情況。

二叉樹二

二叉樹的概念二叉樹（BinaryTree）是一個具有n（n≥0）個節(jié)點的有限集合。（1）

當(dāng)n=0時，二叉樹是一棵空樹;（2）

當(dāng)n≠0時，則是一棵由根節(jié)點和兩棵互不相交的、分別稱作這個根節(jié)點的左子樹和右子樹組成的二叉樹，由于左、右子樹也是二叉樹，因此子樹也可以是空樹。

二叉樹二

二叉樹的概念二叉樹的重要特征：它的所有節(jié)點的度都小于或者等于2。五種不同形態(tài)的二叉樹二叉樹的示例從左到右分別是：①空二叉樹；②只有根節(jié)點的單點樹；③只有根節(jié)點和左子樹；④只有根節(jié)點和右子樹；⑤左右子樹均非空。

二叉樹二

滿二叉樹完全二叉樹①每個節(jié)點的度數(shù)為2(具有兩個非空子樹)，或者度數(shù)為0(葉子節(jié)點)。②所有葉子節(jié)點都在同一層。①至多只有最下兩層中的節(jié)點度數(shù)小于2。②最下一層的葉子節(jié)點都依次排列在該層最左邊位置。

二叉樹一

只需知道數(shù)據(jù)之間相互鏈接的順序探討與討論1.滿二叉樹和完全二叉樹有什么區(qū)別？①滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。②空二叉樹和只有根節(jié)點的二叉樹既是滿二叉樹，也是完全二叉樹。③完全二叉樹可看作是在滿二叉樹最下一層，從右向左去掉若干個節(jié)點后得到。④完全二叉樹中一個節(jié)點如果沒有左子節(jié)點，就一定沒有右子節(jié)點。

二叉樹二

二叉樹的性質(zhì)0102二叉樹的第k層上最多有2k–1（k≥1）個節(jié)點。※當(dāng)k=1時，只有1（20=1）個根節(jié)點；※當(dāng)k=2時，由于節(jié)點的度最大為2，因此，第2層的節(jié)點數(shù)最多有2（21=2）個節(jié)點。依次推出，第k層上最多有2k–1個節(jié)點。深度為k的二叉樹最多有2k–1（k≥1）個節(jié)點。※第1層至第k層上的最大節(jié)點數(shù)相加的結(jié)果是：20+21+…+2k–1=2k–1?！虼?k–1是深度為k的二叉樹的最多節(jié)點總數(shù)。

二叉樹二

03

甲、乙兩棵二叉樹

※在甲樹上，度為2的節(jié)點數(shù)是1，度為1的節(jié)點數(shù)是1，葉子節(jié)點數(shù)為2；

※在乙樹上，度為2的節(jié)點數(shù)是2，度為1的節(jié)點數(shù)是1，葉子節(jié)點數(shù)為3。

二叉樹二拓展鏈接哈夫曼樹

哈夫曼樹又稱最優(yōu)二叉樹，它的相關(guān)概念如下。路徑:樹中兩個節(jié)點之間所經(jīng)過的分支,稱為它們之間的路徑。路徑長度:一條路徑上的分支數(shù),稱為該路徑的長度。節(jié)點的權(quán):給二叉樹中的節(jié)點賦一個數(shù),該數(shù)稱為該節(jié)點的權(quán)。節(jié)點帶權(quán)路徑長度:從根節(jié)點到一個節(jié)點的路徑長度與該節(jié)點的權(quán)值的乘積，稱為該節(jié)點的帶權(quán)路徑長度。

二叉樹二拓展鏈接

三棵二叉樹的WPL分別為:①WPL=2x2+4x2+5x2+8x2=38②WPL=5x3+8x3+4x2+2x1=49③WPL=2x3+4x3+5x2+8x1=36由此可見，第三棵二叉樹是最優(yōu)二叉樹。

二叉樹二

只需知道數(shù)據(jù)之間相互鏈接的順序探討與討論1.已知一棵完全二叉樹共有200個節(jié)點，下列說法正確的是(

)A.該完全二叉樹的高度為7B.該完全二叉樹有99個葉子節(jié)點C.該完全二叉樹有100個度為2的節(jié)點D.該完全二叉樹有1個度為1的節(jié)點D課堂練習(xí)三只需知道數(shù)據(jù)之間相互鏈接的順序探討與討論1.某二叉樹如圖所示，下列說法正確的是(

)A.該二叉樹是完全二叉樹B.該二叉樹共有4個葉子節(jié)點C.節(jié)點D、F都是節(jié)點B的孩子節(jié)點D.該二叉樹后序遍歷的結(jié)果為DEBFCADDEABCF課堂練習(xí)三只需知道數(shù)據(jù)之間相互鏈接的順序探討與討論2.某二叉樹的前序遍歷結(jié)果為ABC,若該二叉樹不是滿二叉樹，則其后序遍歷結(jié)果為()A.ABC B.BCA C.CBA D.CABC3.已知某二叉樹的前序遍