樹與二叉樹的概念及其性質(zhì)課件浙教版高中信息技術(shù)選修1

樹與二叉樹01PART認(rèn)識樹與二叉樹Clickheretoaddyourtitle試分析左圖的數(shù)據(jù)結(jié)構(gòu)你是如何確定該數(shù)據(jù)結(jié)構(gòu)的？可從以下概念進(jìn)行分析描述：孩子、父節(jié)點(diǎn)（雙親節(jié)點(diǎn)）、兄弟、祖先、子孫樹的定義：由n(n≥0)個節(jié)點(diǎn)構(gòu)成的一個有限集合以及在該集合上定義的一種節(jié)點(diǎn)關(guān)系，集合中的元素稱為樹的節(jié)點(diǎn)，n=0的樹稱為空樹。樹的概念及性質(zhì)：（1）對于一顆具有n個節(jié)點(diǎn)的樹，它有n-1條邊（2）度：樹的一個節(jié)點(diǎn)所擁有的子樹的個數(shù)，最大結(jié)點(diǎn)的度稱為樹的度。（3）沒有前驅(qū)結(jié)點(diǎn)稱為根節(jié)點(diǎn)。度為0的結(jié)點(diǎn)稱為葉節(jié)點(diǎn)（終端節(jié)點(diǎn)）（4）樹中節(jié)點(diǎn)的層數(shù)從根算起，根的層數(shù)為1，其余節(jié)點(diǎn)層數(shù)等于其父節(jié)點(diǎn)的層數(shù)加1，樹中節(jié)點(diǎn)的最大層數(shù)稱為樹的高度或深度。練習(xí)分別找出這顆樹共有多少條邊？樹的度？樹的深度？根節(jié)點(diǎn)，葉子節(jié)點(diǎn)。C節(jié)點(diǎn)的父節(jié)點(diǎn)，兄弟節(jié)點(diǎn)，孩子節(jié)點(diǎn)？二叉樹在猜數(shù)字游戲中，甲方事先在紙上寫出一個100以內(nèi)的正整數(shù)，讓乙方猜，乙方每猜一次，甲方都會告訴乙方“猜大了”或是“猜小了”，直至猜出正確結(jié)果。乙方如果采取“折半”的策略進(jìn)行猜數(shù)字，就一定能夠在7次以內(nèi)猜對結(jié)果，具體過程可以抽象成下圖的二叉樹結(jié)構(gòu)。50251237618314375625668888296小小小小小小小大大大大大大大二叉數(shù)的基本概念二叉樹是n（n≥0）個結(jié)點(diǎn)的有限集合：①n=0時，二叉樹是一棵空樹。。②當(dāng)n

≠0時，二叉樹是由一個根結(jié)點(diǎn)和兩個互不相交的被稱為根的左子樹和右子樹組成。左子樹和右子樹又分別是一棵二叉樹。二叉數(shù)的特點(diǎn)①每個結(jié)點(diǎn)至多只有兩棵子樹。②左右子樹不能顛倒（二叉樹是有序樹）二叉數(shù)的五種狀態(tài)特殊的二叉樹—滿二叉樹滿二叉樹：每一層的節(jié)點(diǎn)數(shù)都達(dá)到最大值特殊的二叉樹--完全二叉樹當(dāng)且僅當(dāng)其每個結(jié)點(diǎn)都與高度為h的滿二叉樹中的結(jié)點(diǎn)一一對應(yīng)時，稱為完全二叉樹特點(diǎn)：①只有最后兩層可能有葉子結(jié)點(diǎn)②最多只有一個度為1的結(jié)點(diǎn)特殊的二叉樹不是完全二叉樹完全二叉樹如果某結(jié)點(diǎn)只有一個孩子，一定是左孩子該二叉樹是完全二叉樹嗎？二叉數(shù)的性質(zhì)

第

1

層：20第2層：21第

3

層：22第4層：23二叉數(shù)的性質(zhì)③在任意一棵二叉樹中，若度為2的節(jié)點(diǎn)數(shù)量為n2，

葉子節(jié)點(diǎn)數(shù)為n0，則n0＝n2＋1（葉子節(jié)點(diǎn)比分支節(jié)點(diǎn)多一個）哈夫曼樹特殊的二叉樹Teshudeerchashu哈夫曼樹特殊的二叉樹Teshudeerchashu練一練請從下列三棵二叉樹中找到最優(yōu)二叉樹①WPL=2*2+4*2+5*2+8*2=38②WPL=4*2+5*3+8*3+2*1=49