資源簡介

(共41張PPT)
課時1　樹與二叉樹
第四章　樹
1.了解二叉樹的基本概念和特點，并能結合實例進行分析。2.了解滿二叉樹和完全二叉樹的特點，并能正確區分滿二叉樹和完全二叉樹。3.理解二叉樹的性質，并能利用二叉樹的性質解決實際問題。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.樹(Tree)的幾個基本概念
樹是一種_________的數據結構，用它能很好地描述有分支和層次特性的數據集合。
(1)樹可以描述為由n(n≥0)個節點構成的一個____________以及在該集合上定義的一種______關系。
(2)節點(Node)：集合中的元素稱為樹的節點，_________的樹稱為空樹。
根節點：在樹形結構中，____________的節點稱為根節點(Root)，又稱為開始節點。
父節點、孩子節點：在樹形結構中，對于兩個以邊直接連接的節點，上端節點稱為下端節點的父節點(Parent)，下端節點為孩子節點(Child)，簡稱為子節點。
(3)子樹：樹中某個節點下面所有節點所構成的樹稱為該節點的子樹。
非線性
有限集合
節點
n＝0
沒有前驅
(4)邊：樹的兩個節點之間如果有一條邊連接，那么稱為這兩個節點之間存在一條邊。
對于一棵有n個節點的樹，它有_________條邊。
(5)度(Degree)
節點的度：樹的一個節點所擁有的____________稱為該節點的度。
樹的度：________________________稱為樹的度。
節點的度和樹的度是指寬度。
(6)葉子：度為___的節點稱為葉子節點(Leaf)，又稱為終端節點。
(7)樹的深度(高度)：樹中節點的層數(Level)從根開始計算，根的層數為___，其余節點的層數等于父節點的層數加1。樹中節點的____________稱為樹的高度或深度(Depth)。
n－1
子樹個數
節點的度的最大值
0
1
最大層數
2.二叉樹
(1)二叉樹的定義
二叉樹是指除根節點外的所有節點可分為兩個互不相交的有限集合，分別稱為左子樹和右子樹，左子樹和右子樹也是二叉樹。
二叉樹的子樹有左右之分，且左右子樹的次序不能顛倒。
(2)二叉樹的高度(深度)
二叉樹中節點的____________稱為二叉樹的深度或高度。
最大層數
(3)二叉樹的五種形態
單點樹
只有根和右子樹
左右子樹均非空
3.特殊的二叉樹
(1)滿二叉樹
符合滿二叉樹的兩個條件為：
①每個節點的度數均_______________；
②所有葉子節點都在_________。
(2)完全二叉樹
符合完全二叉樹的兩個條件為：
①只有____________中的節點度數小于2；
②最下一層的葉子節點都依次排列在該層_________位置。
為2或為0
同一層
最下二層
最左邊
正確區分滿二叉樹和完全二叉樹的方法：
(1)滿二叉樹的判斷方法：指葉子節點都在最下面一層上，除葉節點外其他每個節點的度數為2。
(2)完全二叉樹的判斷方法：可將一棵二叉樹先變為滿二叉樹，然后從上到下，同層從左到右的次序從1開始連續編號，如果能按從大到小的順序連續刪除該滿二叉樹的若干節點后得到該二叉樹，則該二叉樹為完全二叉樹。
4.二叉樹的性質
(1)二叉樹的第k層上最多有__________ (k≥1)個節點。
(2)深度為k的二叉樹最多有__________(k≥1)個節點。
(3)在任意一棵二叉樹中，葉子節點數比度為2的節點數_________。
2k－1
2k－1
多1個
例題精析
2
例1 有一棵樹，如圖所示。
C
解析　本題主要考查的是節點的度和樹的度。節點a有三個子節點b、c、d，因此節點a的度為3；樹的度是指寬度，即樹中節點的度的最大值，樹中節點g的度最大，節點g的度為4，因此樹的度為4，答案為C。
則該樹中節點a的度和樹的度分別為(　　)
A.3，3 B.4，3
C.3，4 D.3，10
變式訓練　有一棵樹，如圖所示。
解析　本題主要考查的是樹的深度。樹中節點的最大層數稱為樹的高度或深度，根的層數為1，因此樹的深度為5，答案為C。
C
則該樹深度為(　　)
A.3 B.4 C.5 D.6
例2 若樹的根的高度為1，則二叉樹的第p層上的節點數最多為(　　)
解析　本題主要考查的是二叉樹的性質。當二叉樹為滿二叉樹時，每一層上的節點數最多，第p層上的節點數為2p－1個，因此答案為B。
B
A.2p－1個 B.2p－1 個 C.2p 個 D.2p－1個
變式訓練　若樹的根的高度為1，則高度為h的二叉樹中節點數最多為(　　)
解析　高度為h的滿二叉樹的節點數為2h－1個，因此答案為C。
C
A.2h－1個 B.2h－1 個 C.2h－1個 D.2h＋1個
例3 有一棵深度為h的滿二叉樹，共有n個節點，其中葉子節點為m個，則下列等式成立的是(　　)
A.n＝m＋h B.m＝2h－1＋1 C.2m＝n＋1 D.n＝2h＋1
解析　本題主要考查的是滿二叉樹的性質。深度為h的滿二叉樹的節點總數為2h－1，因此n＝2h－1；在滿二叉樹中，葉子節點數為2h－1，因此，m＝2h－1；在滿二叉樹中，只有度為2的節點和度為0的葉節點，且葉子節點比度為2的節點數多1個，度為2的節點數為n－m，可得到n－m＋1＝m，即2m＝n＋1，因此，答案為C。
C
變式訓練　將一棵有1000個節點的完全二叉樹從上到下，從左到右依次進行編號，根節點的編號為1，則編號為35的節點的右孩子的編號為(　　)
A.36 B.70 C.71 D.72
解析　本題主要考查的是完全二叉樹的特點。在一棵的完全二叉樹中，若父節點的編號為n，則它的左孩子的編號為2*n，右孩子的編號為2*n＋1，則編號為35的節點的右孩子的編號為71，因此答案為C。
C
隨堂檢測
3
1.下列數據結構中屬于非線性結構的是(　　)
D
解析　樹是一種非線性的數據結構，用于描述有分支和層次的數據集合。
A.鏈表 B.隊列 C.棧 D.樹
A.父節點 B.葉節點 C.根節點 D.空節點
C
解析　在樹中，沒有前驅節點的節點稱為根節點，也稱開始節點，因此答案為C。
3.如果節點A有3個兄弟節點，而且B是A的父節點，那么B的度是(　　)
B
解析　節點B是節點A和三個兄弟節點的父節點，也就是節點B有4個孩子節點，即節點B的度數為4，因此選B。
A.3 B.4 C.5 D.6
4.按照二叉數的定義，具有3個節點的二叉樹形態有(　　)
C
解析　具有3個節點的二叉樹有以下五種：
A.3種 B.4種 C.5種 D.6種
因此，答案為C。
5.若樹的根的高度為1，則具有120個節點的完全二叉樹的高度為(　　)
A.5 B.6 C.7 D.8
C
解析　高度為h的滿二叉樹的節點數為2h－1個，完全二叉樹是將滿二叉樹最后一層的葉子節點進行刪除得到的，高度為7的滿二叉樹的節點數為27－1個(127個節點)，可知該完全二叉樹的高度為7，因此答案為C。
6.有如圖所示的二叉樹，圈中數字表示葉子節點的權。則該二叉樹的帶權路徑長度WPL為(　　)
C
解析　本題主要考查的是二叉樹的帶權路徑長度WPL的計算。WPL＝5*1＋6*2＋(8＋7)*3＝62，因此答案為C。
A.26 B.41
C.62 D.88
4
鞏固與提升
基礎鞏固
能力提升
1.樹最適合用來表示下面哪種類型的數據(　　)
D
解析　樹能很好地描述有分支和層次特性的數據集合。
A.有序數據元素
B.無序數據元素
C.元素之間無聯系的數據
D.元素之間具有分支層次關系的數據
A.父節點 B.葉節點 C.根節點 D.空節點
B
解析　在樹中，沒有子節點的節點稱為葉節點，也稱終端節點，因此答案為B。
3.具有3個節點的二叉樹形態有5種，可推測出具有4個節點的二叉樹形態共有(　　)
B
解析　可先畫出3個節點的二叉樹形態，然后求得二叉樹的形態總數，具有4個節點的二叉樹形態共有14種，因此，答案為B。
A.13種 B.14種 C.15種 D.16種
4.下列有關二叉樹的說法，正確的是(　　)
B
解析　本題主要考查的是二叉樹的度。二叉樹的度為最大節點的度，二叉樹中的節點的度最大為2，最小為0(葉節點)，因此正確答案為B。
A.二叉樹的度為2
B.一棵二叉樹的度可以小于2
C.至少有一個節點的度為2
D.任一節點的度均為2
5.一棵度為3，深度為4的樹的節點個數至多為(　　)
C
解析　度為3的樹，即每個分支節點最多有3個孩子節點，按照每個分支節點均有3個孩子節點，即每一層都是上一層節點數的3倍，則前4層的節點數應分別為1，3，9，27，共40個節點，答案為C。
A.31 B.32 C.40 D.42
6.在一棵度為2的樹中，度為2的節點數為15，度為1的節點數為30，則葉子節點(度為0的節點)的個數為(　　)
A.15 B.16 C.17 D.47
B
解析　設度為0的節點數為n0，總節點數為n，則由樹中總結點數、不同度數的節點個數及總邊數之間的關系可以列出以下兩個等式：(1)n＝n0＋n1＋n2＝n0＋30＋15；(2)n－1＝1*n1＋2*n2＝30＋30，可得n＝61，n0＝16，答案為B。
7.一棵高度為h的滿二叉樹，從上到下，同層從左到右的次序從1開始連續編號，若某子節點的右孩子的編號為x(x>1)，則該子節點的編號為(　　)
A.2*x＋1 B.2*x－1 C.x/2 D.x∥2
D
解析　在一棵滿二叉樹中，若父節點的編號為x，則它的左孩子的節點編號為2*x，右孩子的節點編號為2*x＋1，同理，若某子節點的右孩子的編號為x，則該子節點的編號為x∥2，因此答案為D。
8.已知一棵二叉樹有13個節點，樹中度為1的節點數為2，則該樹度為2的節點數為(　　)
A.4 B.5 C.6 D.11
B
解析　本題考查二叉樹性質。根據二叉樹的性質，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。
9.下列關于二叉樹的說法中，正確的是(　　)
D
解析　滿二叉樹一定是完全二叉樹，但完全二叉樹不一定是滿二叉樹，因此A選項錯誤；二叉樹的度是指二叉樹中最大節點的度，而二叉樹的深度是指二叉樹中節點的最大層數，因此B選項錯誤；二叉樹的子樹有左右之分，且左右子樹的次序不能顛倒，因此C選項錯誤；二叉樹中所有節點的度都小于或等于2，因此答案為D。
A.完全二叉樹一定是滿二叉樹
B.二叉樹的深度是指二叉樹中最大節點的度
C.二叉樹的子樹沒有左右之分，左右子樹的次序可以交換
D.二叉樹中所有節點的度都小于或等于2
10.有一棵樹如圖所示，回答下面的問題：
答案　①A　②9　③2　④IJ　⑤A　⑥5　⑦4
解析　參照樹的概念和特性解答。
這棵樹的根節點是①________，葉子節點個數是②________；節點E的度是③________，節點E的孩子節點是④________；節點E的父節點是⑤________；這顆樹的度為⑥________；這棵樹的深度是⑦______。
11.根節點的深度為1，則深度為5的完全二叉樹中節點數最少為(　　)
C
解析　本題主要考查的是完全二叉樹的深度。它是由一個深度為4的滿二叉樹的基礎上得到的，要節點數最少，則第5層上只有一個節點，因此最少為16個節點，答案為C。
A.9 B.15 C.16 D.31
12.在一棵滿二叉樹中，若有N個葉節點，則該滿二叉樹的節點總數為(　　)
C
解析　滿二叉樹除了葉節點外，其他節點均有2個節點，在二叉樹中，葉子節點比度為2的節點多1個，因此，當葉節點個數為N時，它的節點總數為N＋N－1＝2N－1個，因此答案為C。
A.N個 B.2N個 C.2N－1個 D.2N＋1個
B
13.完全二叉樹共有2*n－1個節點，則它的葉節點數為(　　)
解析　完全二叉樹共有2*n－1個節點，該完全二叉樹可能就是一棵滿二叉樹，或者是將滿二叉樹的最下面一層中的偶數個葉節點刪除得到的，因此它的葉節點數為n，答案為B。
A.n－1 B.n C.2*n D.2*n－1
14.假設完全二叉樹的樹根為第1層，樹中第10層有5個葉子節點，則完全二叉樹最多節點個數是(　　)
A.2047 B.2048 C.2037 D.2038
C
解析　根據完全二叉樹的性質可知，葉子節點最多只出現在最下面2層，此題考查的是最多節點數，那么該二又樹應有11層。前10層節點：210－1＝1023第11層滿節點數為：20－1＝1024。因為第10層有S個葉子節點，所以第11層少10個節點，故總結點數為，1023＋1024－10＝2037。課時1　樹與二叉樹
課時目標
1.了解二叉樹的基本概念和特點，并能結合實例進行分析。2.了解滿二叉樹和完全二叉樹的特點，并能正確區分滿二叉樹和完全二叉樹。3.理解二叉樹的性質，并能利用二叉樹的性質解決實際問題。
1.樹(Tree)的幾個基本概念
樹是一種________的數據結構，用它能很好地描述有分支和層次特性的數據集合。
(1)樹可以描述為由n(n≥0)個節點構成的一個________________以及在該集合上定義的一種________關系。
(2)節點(Node)：集合中的元素稱為樹的節點，________的樹稱為空樹。
根節點：在樹形結構中，____________的節點稱為根節點(Root)，又稱為開始節點。
父節點、孩子節點：在樹形結構中，對于兩個以邊直接連接的節點，上端節點稱為下端節點的父節點(Parent)，下端節點為孩子節點(Child)，簡稱為子節點。
(3)子樹：樹中某個節點下面所有節點所構成的樹稱為該節點的子樹。
(4)邊：樹的兩個節點之間如果有一條邊連接，那么稱為這兩個節點之間存在一條邊。
對于一棵有n個節點的樹，它有________條邊。
(5)度(Degree)
節點的度：樹的一個節點所擁有的____________稱為該節點的度。
樹的度：____________________稱為樹的度。
節點的度和樹的度是指寬度。
(6)葉子：度為________的節點稱為葉子節點(Leaf)，又稱為終端節點。
(7)樹的深度(高度)：樹中節點的層數(Level)從根開始計算，根的層數為__________________，其余節點的層數等于父節點的層數加1。樹中節點的__________________稱為樹的高度或深度(Depth)。
2.二叉樹
(1)二叉樹的定義
二叉樹是指除根節點外的所有節點可分為兩個互不相交的有限集合，分別稱為左子樹和右子樹，左子樹和右子樹也是二叉樹。
二叉樹的子樹有左右之分，且左右子樹的次序不能顛倒。
(2)二叉樹的高度(深度)
二叉樹中節點的____________稱為二叉樹的深度或高度。
(3)二叉樹的五種形態
3.特殊的二叉樹
(1)滿二叉樹
符合滿二叉樹的兩個條件為：
①每個節點的度數均____________；
②所有葉子節點都在________。
(2)完全二叉樹
符合完全二叉樹的兩個條件為：
①只有____________中的節點度數小于2；
②最下一層的葉子節點都依次排列在該層________位置。
(3)哈夫曼樹
①哈夫曼樹又稱為最優二叉樹。
②樹的帶權路徑長度(WPL)的計算公式為：WPL＝Wi×Pi，其中，n為樹中葉子節點的個數，Wi和Pi分別是第i個葉子節點的權值和從根節點到該節點的路徑長度。
③最優二叉樹是指在具有n個帶權葉子結點的所有二叉樹中，帶權路徑長度(WPL)最小的二叉樹。
正確區分滿二叉樹和完全二叉樹的方法：
(1)滿二叉樹的判斷方法：指葉子節點都在最下面一層上，除葉節點外其他每個節點的度數為2。
(2)完全二叉樹的判斷方法：可將一棵二叉樹先變為滿二叉樹，然后從上到下，同層從左到右的次序從1開始連續編號，如果能按從大到小的順序連續刪除該滿二叉樹的若干節點后得到該二叉樹，則該二叉樹為完全二叉樹。
4.二叉樹的性質
(1)二叉樹的第k層上最多有______________(k≥1)個節點。
(2)深度為k的二叉樹最多有________(k≥1)個節點。
(3)在任意一棵二叉樹中，葉子節點數比度為2的節點數________。
例1 有一棵樹，如圖所示。則該樹中節點a的度和樹的度分別為(　　)
A.3，3 B.4，3 C.3，4 D.3，10
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有一棵樹，如圖所示。則該樹深度為(　　)
A.3 B.4 C.5 D.6
例2 若樹的根的高度為1，則二叉樹的第p層上的節點數最多為(　　)
A.2p－1個 B.2p－1 個
C.2p 個 D.2p－1個
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　若樹的根的高度為1，則高度為h的二叉樹中節點數最多為(　　)
A.2h－1個 B.2h－1 個 C.2h－1個 D.2h＋1個
例3 有一棵深度為h的滿二叉樹，共有n個節點，其中葉子節點為m個，則下列等式成立的是(　　)
A.n＝m＋h B.m＝2h－1＋1 C.2m＝n＋1 D.n＝2h＋1
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　將一棵有1000個節點的完全二叉樹從上到下，從左到右依次進行編號，根節點的編號為1，則編號為35的節點的右孩子的編號為(　　)
A.36 B.70 C.71 D.72
1.下列數據結構中屬于非線性結構的是(　　)
A.鏈表 B.隊列 C.棧 D.樹
2.在一棵樹中，沒有前驅節點的節點是(　　)
A.父節點 B.葉節點 C.根節點 D.空節點
3.如果節點A有3個兄弟節點，而且B是A的父節點，那么B的度是(　　)
A.3 B.4 C.5 D.6
4.按照二叉數的定義，具有3個節點的二叉樹形態有(　　)
A.3種 B.4種 C.5種 D.6種
5.若樹的根的高度為1，則具有120個節點的完全二叉樹的高度為(　　)
A.5 B.6 C.7 D.8
6.有如圖所示的二叉樹，圈中數字表示葉子節點的權。則該二叉樹的帶權路徑長度WPL為(　　)
A.26 B.41 C.62 D.88
課時1　樹與二叉樹
知識梳理
1.非線性　(1)有限集合　節點　(2)n＝0　沒有前驅　(4)n－1　(5)子樹個數　節點的度的最大值　(6)0　(7)1　最大層數
2.(2)最大層數　(3)②單點樹　④只有根和右子樹　⑤左右子樹均非空
3.(1)①為2或為0　②同一層　(2)①最下二層　②最左邊
4.(1)2k－1　(2)2k－1　(3)多1個
例題精析
例1　C　[本題主要考查的是節點的度和樹的度。節點a有三個子節點b、c、d，因此節點a的度為3；樹的度是指寬度，即樹中節點的度的最大值，樹中節點g的度最大，節點g的度為4，因此樹的度為4，答案為C。]
變式訓練　C　[本題主要考查的是樹的深度。樹中節點的最大層數稱為樹的高度或深度，根的層數為1，因此樹的深度為5，答案為C。]
例2　B　[本題主要考查的是二叉樹的性質。當二叉樹為滿二叉樹時，每一層上的節點數最多，第p層上的節點數為2p－1個，因此答案為B。]
變式訓練　C　[高度為h的滿二叉樹的節點數為2h－1個，因此答案為C。]
例3　C　[本題主要考查的是滿二叉樹的性質。深度為h的滿二叉樹的節點總數為2h－1，因此n＝2h－1；在滿二叉樹中，葉子節點數為2h－1，因此，m＝2h－1；在滿二叉樹中，只有度為2的節點和度為0的葉節點，且葉子節點比度為2的節點數多1個，度為2的節點數為n－m，可得到n－m＋1＝m，即2m＝n＋1，因此，答案為C。]
變式訓練　C　[本題主要考查的是完全二叉樹的特點。在一棵的完全二叉樹中，若父節點的編號為n，則它的左孩子的編號為2*n，右孩子的編號為2*n＋1，則編號為35的節點的右孩子的編號為71，因此答案為C。]
隨堂檢測
1.D　[樹是一種非線性的數據結構，用于描述有分支和層次的數據集合。]
2.C　[在樹中，沒有前驅節點的節點稱為根節點，也稱開始節點，因此答案為C。]
3.B　[節點B是節點A和三個兄弟節點的父節點，也就是節點B有4個孩子節點，即節點B的度數為4，因此選B。]
4.C　[具有3個節點的二叉樹有以下五種：
因此，答案為C。]
5.C　[高度為h的滿二叉樹的節點數為2h－1個，完全二叉樹是將滿二叉樹最后一層的葉子節點進行刪除得到的，高度為7的滿二叉樹的節點數為27－1個(127個節點)，可知該完全二叉樹的高度為7，因此答案為C。]
6.C　[本題主要考查的是二叉樹的帶權路徑長度WPL的計算。WPL＝5*1＋6*2＋(8＋7)*3＝62，因此答案為C。]

展開更多......

收起↑