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

第1節(jié)

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

選修一樹(shù)01二叉樹(shù)02

了解樹(shù)、子樹(shù)、樹(shù)的度、樹(shù)的深度等概念。01

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

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

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

樹(shù)一

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

樹(shù)一

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

樹(shù)一

樹(shù)

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

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

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

樹(shù)一

樹(shù)

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

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

樹(shù)一

第1層第3層第4層第2層樹(shù)的示例根節(jié)點(diǎn)（開(kāi)始節(jié)點(diǎn)）：沒(méi)有前驅(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)

樹(shù)一

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

樹(shù)一

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

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

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

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

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

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

樹(shù)一

拓展鏈接圖（Graph）

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

有向圖

連通圖

非連通圖

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

樹(shù)一

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

)AA.樹(shù)

B.棧

C.隊(duì)列

D.鏈表

二叉樹(shù)二

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

二叉樹(shù)二

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

二叉樹(shù)二

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

二叉樹(shù)二

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

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

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

二叉樹(shù)二

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

二叉樹(shù)二

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

二叉樹(shù)一

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

二叉樹(shù)二

二叉樹(shù)的性質(zhì)0102二叉樹(shù)的第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的二叉樹(shù)最多有2k–1（k≥1）個(gè)節(jié)點(diǎn)?！?層至第k層上的最大節(jié)點(diǎn)數(shù)相加的結(jié)果是：20+21+…+2k–1=2k–1?！虼?k–1是深度為k的二叉樹(shù)的最多節(jié)點(diǎn)總數(shù)。

二叉樹(shù)二

03

甲、乙兩棵二叉樹(shù)

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

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

二叉樹(shù)二拓展鏈接哈夫曼樹(shù)

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

二叉樹(shù)二拓展鏈接

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

二叉樹(shù)二

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

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

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