資源簡介

(共24張PPT)
4
樹
第四章
選擇性必修1《數據與數據結構》
第四章 樹
4.1 樹與二叉樹
4.1.1 樹
4 . 1
樹與二叉樹
公司內部管理的組織大系圖
樹形結構
公司內部管理的組織
編譯系統中，源程序的語法結構
在數據庫系統中，樹形結構是數據庫層次模型的基礎
4.1.1 樹
4 . 1
樹與二叉樹
樹(Tree）可以描述為由n (n≥0)個節點(Node)構成的一個有限集合+節點關系。
節點：樹的元素【n=0為空樹】；
子樹：樹中某個節點下面的所有節點所構成的樹；
兩個節點之間存在一條邊；
一棵具有n個節點的樹，它有n-1條邊。
樹中共有13個節點、12條邊
節點B、G、H構成了節點A的一棵子樹。
子 樹
4.1.1 樹
節點的度：某節點擁有的子樹個數
樹的度：最大的節點的度
節點A的度為5，
節點B的度為2，
節點I的度為3，
因此樹的度為5。
節點的度和樹的度共同體現了樹的寬度(節點的分支數和樹的發散程度)。
線性表( 特殊的樹)——度為1
4.1.1 樹
根節點（開始節點）：沒有前驅的節點
葉子節點（終端節點）：度為0
分支節點（非終端節點）：度不為0
內部節點：除根節點之外的分支節點
父節點（雙親節點）：以邊相連的上端節點
孩子節點：以邊相連的下端節點
兄弟節點：擁有同一父節點
根節點
葉子節點
父節點
4.1.1 樹
4.1.1 樹
樹中節點層數：根節點層數為1，其余節點層數等于其父節點的層數加1
樹的高度/深度=最大層數
樹的高度/深度=4
4.1.1 樹
樹形結構（擁有多個節點）：非線性結構，
根節點（無前驅，有后繼），
葉子節點（存在多個，沒有后繼，只有前驅）， 其余的節點都只有一個直接前驅和多個直接后繼。
線性結構：
必存在著唯一的一個“第一個元素”和唯一的一個“最后的元素”;
除第一個元素以外，其他數據元素均有唯一的“前驅”，除最后元素以外，其他數據元素均有唯一的“后繼”。
4.1.1 樹
拓展鏈接
圖狀結構是一種比線性結構和樹形結構更為復雜的非線性結構，廣泛應用于計算機網絡、通信工程等諸多領域。在線性表中，一個數據元素只和它的前驅和后繼元素有關系。在樹中，一個節點只和它的父節點和孩子節點有關系。而在圖中，每個頂點都有可能和其他任意頂點有關系，這就使得圖的存儲和運算比前兩種數據結構更加復雜。圖中節點的關系既可以是單向的，也可以是雙向的，有無向圖和有向圖之分，又有連通圖和非連通圖之別，如圖所示。
1.如何管理計算機中的照片,使得瀏覽起來更加方便
2.若干個家庭一起組織自助游，準備階段需要考慮旅游路線的規劃、食宿安排以及旅途中各項娛樂活動的人員組隊等問題。如何用學過的數據結構知識來更好地幫助制訂相關計劃
4.1.1 樹
問題與討論
《必修1》· 計算機一般采用樹形目錄結構來管理文件
4.1.2 二叉樹
猜數字游戲：甲方事先在紙上寫出一個100以內的正整數，讓乙方猜，乙方每猜一次，甲方都會告訴乙方“猜大了”或是“猜小了”，直至猜出正確結果。
乙方如果采取“折半”的策略進行猜數字，就一定能夠在7次以內猜對結果。
二叉樹( Binary Tree)是一個具有n (n≥0)個節點的有限集合。
當n=0時，二叉樹是一棵空樹;
當n≠0時，則是一棵由根節點和兩棵互不相交的、分別稱作這個根節點的左子樹和右子樹組成的二叉樹，由于左、右子樹也是二叉樹，因此子樹也可以是空樹。
二叉樹的重要特征：它的所有節點的度都小于或者等于2
二叉樹的概念
①空二叉樹;
②只有根節點的單點樹:
③只有根節點和左子樹;
④只有根節點和右子樹;
⑤左右子樹均非空。
二叉樹的5種形態
(1）滿二叉樹
①每個節點的度數為2(具有兩個非空子樹)，或者度數為0(葉子節點)。
②所有葉子節點都在同一層。
(2）完全二叉樹
①至多只有最下兩層中的節點度數小于2。
②最下一層的葉子節點都依次排列在該層最左邊位置。
滿二叉樹VS完全二叉樹
滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹。
空二叉樹和只有根節點的二叉樹既是滿二叉樹，也是完全二叉樹。
完全二叉樹可看作是在滿二叉樹最下一層，從右向左去掉若干個節點后得到。
完全二叉樹中一個節點如果沒有左子節點，就一定沒有右子節點。
補充！
二叉樹的概念
①二叉樹的第k層上最多有(k≥1 )個節點。
當k=1時，只有1個根節點;【1】
當k=2時，由于節點的度最大為2，因此，第2層的節點數最多有2個節點；【2】
依次推出，…… 第k層上最多有【2】個節點。
②深度為k的二叉樹最多有-1(k≥1)個節點。
第1層至第m層上的最大節點數相加的結果是:
因此是深度為k的二叉樹的最多節點總數?！緷M二叉樹】
二叉樹的性質
③在任意一棵二叉樹中，若度為2的節點數量為，葉子節點（度為0的節點）數為，則。
度為0，1和2的節點數分別是和，總的節點數
n個節點的二叉樹的總邊數為n-1條。
二叉樹的總邊數與度之間的關系: n-1= 2
聯立等式 ，可得
二叉樹的性質
甲、乙兩棵二叉樹
在甲樹上，度為2的節點數是1，度為1的節點數是1，葉子節點數為2；
在乙樹上，度為2的節點數是2，度為1的節點數是1，葉子節點數為3。
哈夫曼樹
拓展鏈接
哈夫曼樹又稱最優二叉樹，它的相關概念如下。
路徑:樹中兩個節點之間所經過的分支,稱為它們之間的路徑。
路徑長度:一條路徑上的分支數,稱為該路徑的長度。
節點的權:給二叉樹中的節點賦一個數,該數稱為該節點的權。
節點帶權路徑長度:從根節點到一個節點的路徑長度與該節點的權值的乘積，稱為該節點的帶權路徑長度。
哈夫曼樹
拓展鏈接
樹的帶權路徑長度:一棵樹中所有葉子節點的帶權路徑長度之和，稱為該樹的帶權路徑長度WPL；
WPL的公式如下:
【n=葉子節點數， =第i個葉子節點的權值;=從根節點到該路徑的長度。】
最優二叉樹:帶權路徑長度WPL最小的二叉樹。在最優二叉樹中，權值較大的節點離根較近。
如圖4.1.12所示的三棵二叉樹，葉子節點的權值都分別為2，4，5，8。
從數據的組織處理效率來看，二叉樹的本質上是對數組和鏈表的一種折中處理，如何看待這種說法？
問題與討論
樹與二叉樹
樹與二叉樹
？ 思考與練習
1.試著用樹結構來描述自己家族成員的組成情況。
2.請畫出包含4個節點的所有形態的二叉樹。
3.已知某完全二叉樹有200個節點，求出該二叉樹的高度。
4.假設某二叉樹包含的節點數據分別為:1，5，8，3，10。請完成下列任務:
(1)畫出兩棵高度最大的二叉樹。
(2）畫出兩棵完全二叉樹，要求每個雙親節點的值大于其孩子節點的值。
樹的概念
二叉樹的概念
滿二叉樹、完全二叉樹
二叉樹的性質
課堂小結
學習評價
對自己和同伴的表現進行客觀的評價，并思考后續完善的方向。（5=優秀，4=超出一般水平，3=滿意，2=有待改進，1=不太理想）
評分項 自我評價 同學互評
能從新課導入中的感知生活中蘊含樹型結構的實例 5 4 3 2 1 5 4 3 2 1
能理樹、子樹、樹的度、樹的深度等概念。 5 4 3 2 1 5 4 3 2 1
能自主學習教材，并歸納出線性結與樹型結構在連接關系上的差異。 5 4 3 2 1 5 4 3 2 1
能理解二叉樹、滿二叉樹、完全二叉樹等概念。 5 4 3 2 1 5 4 3 2 1
能理解二叉樹的三種性質 5 4 3 2 1 5 4 3 2 1
課堂作業
1.思考教材“問題與討論”中的兩個問題。
謝謝觀看
制作者：XXXXXX

展開更多......

收起↑