4.1樹與二叉樹課件浙教版高中信息技術(shù)選修1

4樹第四章選擇性必修1《數(shù)據(jù)與數(shù)據(jù)結(jié)構(gòu)》制作者：鄒修鴻第四章樹4.1樹與二叉樹4.1.1樹4.1樹與二叉樹公司內(nèi)部管理的組織大系圖樹形結(jié)構(gòu)公司內(nèi)部管理的組織編譯系統(tǒng)中，源程序的語法結(jié)構(gòu)在數(shù)據(jù)庫系統(tǒng)中，樹形結(jié)構(gòu)是數(shù)據(jù)庫層次模型的基礎(chǔ)4.1.1樹4.1樹與二叉樹樹(Tree）可以描述為由n(n≥0)個(gè)節(jié)點(diǎn)(Node)構(gòu)成的一個(gè)有限集合+節(jié)點(diǎn)關(guān)系。節(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條邊。樹中共有13個(gè)節(jié)點(diǎn)、12條邊節(jié)點(diǎn)B、G、H構(gòu)成了節(jié)點(diǎn)A的一棵子樹。子樹4.1.1樹節(jié)點(diǎn)的度：某節(jié)點(diǎn)擁有的子樹個(gè)數(shù)樹的度：最大的節(jié)點(diǎn)的度節(jié)點(diǎn)A的度為5，節(jié)點(diǎn)B的度為2，節(jié)點(diǎn)I的度為3，因此樹的度為5。節(jié)點(diǎn)的度和樹的度共同體現(xiàn)了樹的寬度(節(jié)點(diǎn)的分支數(shù)和樹的發(fā)散程度)。線性表(特殊的樹)——度為14.1.1樹根節(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)4.1.1樹4.1.1樹樹中節(jié)點(diǎn)層數(shù)：根節(jié)點(diǎn)層數(shù)為1，其余節(jié)點(diǎn)層數(shù)等于其父節(jié)點(diǎn)的層數(shù)加1樹的高度/深度=最大層數(shù)樹的高度/深度=44.1.1樹樹形結(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è)直接后繼。線性結(jié)構(gòu)：

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

除第一個(gè)元素以外，其他數(shù)據(jù)元素均有唯一的“前驅(qū)”，除最后元素以外，其他數(shù)據(jù)元素均有唯一的“后繼”。4.1.1樹拓展鏈接

圖狀結(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)系，這就使得圖的存儲(chǔ)和運(yùn)算比前兩種數(shù)據(jù)結(jié)構(gòu)更加復(fù)雜。圖中節(jié)點(diǎn)的關(guān)系既可以是單向的，也可以是雙向的，有無向圖和有向圖之分，又有連通圖和非連通圖之別，如圖所示。1.如何管理計(jì)算機(jī)中的照片,使得瀏覽起來更加方便?2.若干個(gè)家庭一起組織自助游，準(zhǔn)備階段需要考慮旅游路線的規(guī)劃、食宿安排以及旅途中各項(xiàng)娛樂活動(dòng)的人員組隊(duì)等問題。如何用學(xué)過的數(shù)據(jù)結(jié)構(gòu)知識(shí)來更好地幫助制訂相關(guān)計(jì)劃?4.1.1樹問題與討論《必修1》·計(jì)算機(jī)一般采用樹形目錄結(jié)構(gòu)來管理文件4.1.2二叉樹猜數(shù)字游戲：甲方事先在紙上寫出一個(gè)100以內(nèi)的正整數(shù)，讓乙方猜，乙方每猜一次，甲方都會(huì)告訴乙方“猜大了”或是“猜小了”，直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字，就一定能夠在7次以內(nèi)猜對(duì)結(jié)果。二叉樹(BinaryTree)是一個(gè)具有n(n≥0)個(gè)節(jié)點(diǎn)的有限集合。當(dāng)n=0時(shí)，二叉樹是一棵空樹;當(dāng)n≠0時(shí)，則是一棵由根節(jié)點(diǎn)和兩棵互不相交的、分別稱作這個(gè)根節(jié)點(diǎn)的左子樹和右子樹組成的二叉樹，由于左、右子樹也是二叉樹，因此子樹也可以是空樹。

二叉樹的重要特征：它的所有節(jié)點(diǎn)的度都小于或者等于2二叉樹的概念①空二叉樹;②只有根節(jié)點(diǎn)的單點(diǎn)樹:③只有根節(jié)點(diǎn)和左子樹;④只有根節(jié)點(diǎn)和右子樹;⑤左右子樹均非空。二叉樹的5種形態(tài)(1）滿二叉樹①每個(gè)節(jié)點(diǎn)的度數(shù)為2(具有兩個(gè)非空子樹)，或者度數(shù)為0(葉子節(jié)點(diǎn))。②所有葉子節(jié)點(diǎn)都在同一層。(2）完全二叉樹①至多只有最下兩層中的節(jié)點(diǎn)度數(shù)小于2。②最下一層的葉子節(jié)點(diǎn)都依次排列在該層最左邊位置。滿二叉樹VS完全二叉樹滿二叉樹是完全二叉樹，但完全二叉樹不一定是滿二叉樹?？斩鏄浜椭挥懈?jié)點(diǎn)的二叉樹既是滿二叉樹，也是完全二叉樹。完全二叉樹可看作是在滿二叉樹最下一層，從右向左去掉若干個(gè)節(jié)點(diǎn)后得到。完全二叉樹中一個(gè)節(jié)點(diǎn)如果沒有左子節(jié)點(diǎn)，就一定沒有右子節(jié)點(diǎn)。補(bǔ)充！二叉樹的概念

二叉樹的性質(zhì)

二叉樹的性質(zhì)甲、乙兩棵二叉樹在甲樹上，度為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)路徑長度。哈夫曼樹拓展鏈接

從數(shù)據(jù)的組織處理效率來看，二叉樹的本質(zhì)上是對(duì)數(shù)組和鏈表的一種折中處理，如何看待這種說法？問題與討論樹與二叉樹樹與二叉樹？

思考與練習(xí)1.試著用樹結(jié)構(gòu)來描述自己家族成員的組成情況。2.請(qǐng)畫出包含4個(gè)節(jié)點(diǎn)的所有形態(tài)的二叉樹。3.已知某完全二叉樹有200個(gè)節(jié)點(diǎn)，求出該二叉樹的高度。4.假設(shè)某二叉樹包含的節(jié)點(diǎn)數(shù)據(jù)分別為:1，5，8，3，10。請(qǐng)完成下列任務(wù):(1)畫出兩棵高度最大的二叉樹。(2）畫出兩棵完全二叉樹，要求每個(gè)雙親節(jié)點(diǎn)的值大于其孩子節(jié)點(diǎn)的值。樹的概念二叉樹的概念滿二叉樹、完全二叉樹二叉樹的性質(zhì)課堂小結(jié)學(xué)習(xí)評(píng)價(jià)對(duì)自己和同伴的表現(xiàn)進(jìn)行客觀的評(píng)價(jià)，并思考后續(xù)完善的方向。（5=優(yōu)秀，4=超出一般水平，3=滿意，2=有待改進(jìn)，1=不太理想）評(píng)分項(xiàng)自我評(píng)價(jià)同學(xué)互評(píng)能從新課導(dǎo)入中的感知生活中蘊(yùn)含樹型結(jié)構(gòu)的實(shí)例5432154321能理樹、子樹、樹的度、樹的深度等概念。5432154321能自主學(xué)習(xí)教材，并歸納出線性結(jié)與樹型結(jié)構(gòu)在連接關(guān)系上的差異。54321543