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

第1節(jié)

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

選修一樹01二叉樹02

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

通過具體任務(wù)的實(shí)踐活動，體驗(yàn)用樹型結(jié)構(gòu)描述生活中蘊(yùn)含樹型結(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)實(shí)世界中廣泛存在公司內(nèi)部管理的組織關(guān)系圖賦值語句的語法樹數(shù)據(jù)庫層次結(jié)構(gòu)圖

樹一

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

樹一

樹

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

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

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

樹一

樹

節(jié)點(diǎn)的度：某節(jié)點(diǎn)擁有的子樹個(gè)數(shù)

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

樹一

第1層第3層第4層第2層樹的示例根節(jié)點(diǎn)（開始節(jié)點(diǎn)）：沒有前驅(qū)的節(jié)點(diǎn)葉子節(jié)點(diǎn)（終端節(jié)點(diǎn)）：度為0分支節(jié)點(diǎn)（非終端節(jié)點(diǎn)）：度不為0內(nèi)部節(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)

樹一

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

樹一

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

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

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

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

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

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

樹一

拓展鏈接圖（Graph）

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

有向圖

連通圖

非連通圖

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

樹一

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

)AA.樹

B.棧

C.隊(duì)列

D.鏈表

二叉樹二

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

二叉樹二

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

二叉樹二

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

二叉樹二

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

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

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

二叉樹二

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

二叉樹二

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

二叉樹一

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

二叉樹二

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

二叉樹二

03

甲、乙兩棵二叉樹

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

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

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

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

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

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