4.1 樹與二叉樹（教學課件）-高中《信息技術》選修1數據與數據結構同步高效課堂（浙教版）

第1節(jié)

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

選修一樹01二叉樹02

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

通過具體任務的實踐活動，體驗用樹型結構描述生活中蘊含樹型結構的組織關系。03

了解二叉樹、滿二叉樹、完全二叉樹等概念。02PART01樹新課導入樹？邏輯上的樹生活中的樹新課導入常見的樹形結構

樹是一種非線性的數據結構，用它能很好地描述有分支和層次特性的數據集合。

樹一

樹形結構在現實世界中廣泛存在公司內部管理的組織關系圖賦值語句的語法樹數據庫層次結構圖

樹一

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

樹一

樹

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

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

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

樹一

樹

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

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

樹一

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

樹一

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

樹一

1線性結構：

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

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

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

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

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

樹一

拓展鏈接圖（Graph）

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

有向圖

連通圖

非連通圖

節(jié)點關系圖

樹一

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

)AA.樹

B.棧

C.隊列

D.鏈表

二叉樹二

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

二叉樹二

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

二叉樹二

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

二叉樹二

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

當n=0時，二叉樹是一棵空樹;（2）

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

二叉樹二

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

二叉樹二

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

二叉樹一

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

二叉樹二

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

二叉樹二

03

甲、乙兩棵二叉樹

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

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

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

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

二叉樹二拓展鏈接

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

二叉樹二

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

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

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