資源簡介

(共37張PPT)
樹與二叉樹
1 樹
本節(jié)要點：
2 二叉樹
1.1 樹的概念
1.2 樹的特點
2.1 二叉樹的概念
2.2 二叉樹的分類
2.3 二叉樹的性質(zhì)
樹？
生活中的樹
邏輯上的樹
常見的樹形結(jié)構(gòu)
1.公司組織架構(gòu)
2.知識點匯總
3.動物分類
共同特征：一對多的非線性關系
1.1 樹的概念
樹：一種非線性數(shù)據(jù)結(jié)構(gòu)，
是有 n（n>=0）個節(jié)點構(gòu)成的有限集合
空樹：節(jié)點n=0的樹
1.2 樹的特點
1.2 樹的特點
當n>0時，n個節(jié)點的樹有n-1條邊
子樹：樹中某個節(jié)點下面的所有節(jié)點所構(gòu)成的樹
邊
節(jié)點
T1
T2
T3
T4
11個節(jié)點，10條邊
1.2 樹的特點
節(jié)點的度: 節(jié)點所擁有的子樹個數(shù)
樹的度：最大的節(jié)點的度（樹的寬度）
A的度: _____
B的度: _____
C的度：____
樹的度：___
3
2
0
4
1.2 樹的特點
高度或深度：樹中節(jié)點的最大層數(shù)
樹的高度：___
①
②
③
④
4
根節(jié)點：（開始節(jié)點）沒有前驅(qū)節(jié)點
葉子節(jié)點：（終端節(jié)點）沒有后繼節(jié)點，度為0
1.2 樹的特點
A是根節(jié)點
E、F、C、H、I、J、K是葉子節(jié)點
分支節(jié)點：度不為0的節(jié)點
內(nèi)部節(jié)點：除根節(jié)點外的分支節(jié)點
1.2 樹的特點
A、B、D、G是分支節(jié)點
B、D、G是內(nèi)部節(jié)點
父節(jié)點：對于兩個以邊直接連接的節(jié)點，
上端節(jié)點稱為下端節(jié)點的父節(jié)點或雙親節(jié)點
1.2 樹的特點
A是B、C、D的父節(jié)點
1.2 樹的特點
B、C、D是A的孩子節(jié)點
B、C、D互為兄弟節(jié)點
孩子節(jié)點：下端節(jié)點稱為上端節(jié)點的孩子節(jié)點
兄弟節(jié)點: 擁有同一個父節(jié)點的同層節(jié)點
1.2 樹的特點
學習任務一
填一填：
1.該樹有___個節(jié)點，___條邊，該樹的度是_____,高度是___
2.該樹的葉子節(jié)點是________,內(nèi)部節(jié)點是______________
3.度為1的節(jié)點數(shù)有__個，B的孩子節(jié)點是___, Q的兄弟節(jié)點是__
12
11
3
6
E F Z P C H
B G R Q D
3
E F G
P
小明寫了一個100以內(nèi)的正整數(shù)，讓小紅猜；
小紅每猜一次，
小明會告訴她“猜大了”還是“猜小了”，
直到猜出正確的結(jié)果。
請問小紅采用什么方法，
能用最少的次數(shù)猜出正確結(jié)果？
猜數(shù)游戲
答：用折半猜數(shù)法 效率最高
猜數(shù)游戲

50
小

75

25
大
小

12
大

37
小

62
大

88
. . . . . . . . . . . .
二叉樹
2.1 二叉樹的概念
二叉樹是一個具有 n（n>=0）個節(jié)點的有限集合。
當 n=0時，二叉樹是一棵空樹；
當 n>0時，則是由根節(jié)點、左子樹和右子樹組成
由于左、右子樹也是二叉樹，因此子樹也可以是空樹
二叉樹的典型特征：所有節(jié)點的度都小于等于2
二叉樹的5種形態(tài)：
2.1 二叉樹的概念
①
②
③
④
⑤
左子樹
右子樹
左子樹
右子樹
學習任務二
畫一畫：
有3個節(jié)點的二叉樹有幾種不同的形態(tài)？
學習任務二
畫一畫：
有3個節(jié)點的二叉樹共有5種不同的形態(tài)















①
②
③
④
⑤
2.2 二叉樹的分類
所有的葉子節(jié)點都在最底層，
除了葉子節(jié)點外，每個結(jié)點的度是 2
滿二叉樹
以下3個二叉樹的共同特點是？
2.2 二叉樹的分類
至多只有最下兩層中的節(jié)點的度數(shù)小于2，
且最后一層的葉子結(jié)點都依次從左到右分布
完全二叉樹
在滿二叉樹基礎上去掉幾個節(jié)點：
學習任務三
A.
B.
C.
D.
判一判： 下列4棵樹是否為完全二叉樹？
√
完全二叉樹：至多只有最下兩層中的節(jié)點的度數(shù)小于2，且最后一層的葉子結(jié)點都依次從左到右分布
滿二叉樹 VS 完全二叉樹
1.滿二叉樹一定是完全二叉樹
但完全二叉樹不一定是滿二叉樹
2.滿二叉樹在最后一層從最后一個節(jié)點開始，
從右向左連續(xù)去掉任意個節(jié)點，即為完全二叉樹
2.2 二叉樹的分類
學習任務四
選一選：下列哪些是滿二叉樹，哪些是完全二叉樹？
②
③
④
⑤
①
②是滿二叉樹
⑤是完全二叉樹
二叉樹有哪些性質(zhì)呢？
因為滿二叉樹在同層二叉樹中
擁有的節(jié)點數(shù)最多
我們以滿二叉樹為例來探究下
2.3 二叉樹的性質(zhì)
2.3 二叉樹的性質(zhì)
第①層：1個
第②層：2個
第③層：4個
第④層：8個
1.滿二叉樹中每層的節(jié)點數(shù)分別是？
. . . . . .第k層有幾個節(jié)點？
第k層：2k-1個
20
21
22
23
2.3 二叉樹的性質(zhì)
性質(zhì)1：
二叉樹的第k層上最多有2k-1個節(jié)點
2.3 二叉樹的性質(zhì)
2.不同深度的滿二叉樹共有幾個節(jié)點數(shù)？
深度為2
共有3個節(jié)點
深度為3
共有7個節(jié)點
深度為4
共有15個節(jié)點
. . . . . .深度為k的滿二叉樹共有幾個節(jié)點？
2k-1個
2.3 二叉樹的性質(zhì)
性質(zhì)2：
深度為k的二叉樹最多有2k-1個節(jié)點
2.3 二叉樹的性質(zhì)
n0=4
n1=1
n2=3
n0=2
n1=1
n2=1
n0=3
n1=2
n2=2
n0=4
n1=3
n2=3
我們發(fā)現(xiàn)：n0=n2+1
①
②
③
④
3.數(shù)一數(shù)度為0、1、2的節(jié)點數(shù)分別是多少？
2.3 二叉樹的性質(zhì)
性質(zhì)3：
在任意一棵二叉樹中，度為2的節(jié)點數(shù)n2和度為0的節(jié)點數(shù)n0的關系是：n0=n2+1
2.3 二叉樹的性質(zhì)
性質(zhì)1：
二叉樹的第k層上最多有2k-1個節(jié)點
性質(zhì)2：
深度為k的二叉樹最多有2k-1個節(jié)點
性質(zhì)3：
在任意一棵二叉樹中，度為2的節(jié)點數(shù)n2和度為0的節(jié)點數(shù)n0的關系是：n0=n2+1
節(jié)點數(shù)n滿足等式：n=n0+n1+n2 ①
邊數(shù)B滿足等式： B=n-1 ②
B=n0*0+n1*1+n2*2 ③
由①②③可推導出 n0=n2+1
請?zhí)骄孔C明：
在任意一棵二叉樹中，都滿足 n0=n2+1
學習任務五
課堂小結(jié)
謝 謝！

展開更多......

收起↑