資源簡介

(共50張PPT)
課時2　二叉樹的基本操作
第四章　樹
1.掌握使用數組和鏈表等數據結構建立二叉樹的方法。2.掌握二叉樹遍歷的基本操作方法。
目 錄
CONTENTS
知識梳理
01
例題精析
02
隨堂檢測
03
鞏固與提升
04
知識梳理
1
1.建立二叉樹的方法
建立二叉樹的操作方法為：按照二叉樹層的順序進行，先由第___層開始，依次到下一層，在每一層中按照從_________的順序創建節點。
1
左到右
2.用數組實現二叉樹的創建
(1)完全二叉樹
①從二叉樹的_________開始，按____________、自左向右的順序對n個節點進行編號，根節點的編號為0，最后一個節點的編號為_________。
②然后依次將二叉樹的節點用一組連續的數組元素來表示，節點編號與_______________一一對應。
(2)非完全二叉樹
①對于非完全二叉樹，先將它補全為一棵______二叉樹，補上的節點及分支用虛線表示。
②然后按照完全二叉樹的方法，將節點存儲在數組中。
根節點
從上到下
n－1　
數組的下標
完全
(3)使用數組(列表)建立二叉樹
空樹用None表示，非空二叉樹用包含三個元素的列表[d，l，r]表示，分別存儲著根節點的元素和左右子樹，因此二叉樹的list實現采用嵌套括號([])的形式。
用數組(列表)構建二叉樹的代碼如下：
def create_tree(tree，data)：
for i in range(len(data))：
depth＝0 #程序的第0層相當于樹的第1層
if i＝＝0: #根節點
　　　　 tree[depth]＝data[i]
else：
　　　　 #while循環結束表示找到存放數據的節點(索引)位置
　　　while tree[depth] ！＝0：
　　　 　　　if data[i]>tree[depth]：　#往右尋找
　　　　　　　　depth＝depth*2＋2　#父節點的右孩子位置
　　　　　　else：　　　　#往左尋找
　　　　　　　　depth＝depth*2＋1　#父節點的左孩子位置
tree[depth]＝data[i]　#找到數據應存放的節點位置，并存儲該節點
3.用鏈表實現二叉樹的創建
二叉樹用鏈表實現時，二叉樹的節點至少需要三個域：一個_________和兩個_________。如下圖所示：
lchild data rchild
其中lchild和rchild是指針域，存放指向節點的左孩子節點和右孩子節點的指針，data是數據域。
使用鏈表建立搜索二叉樹如下：
def insert(self，data)：
if self.data：　　　#如果根節點不存在
if data數據域
指針域
　　　if self.left：
　　　 　　　self.left.insert(data) #遞歸調用往下一層
　　　　else：
　　　　　 self.left＝Node(data) #建立新節點存放數據
else: #插入值大于當前節點值
　　if self.right：
　　　self.right.insert(data)
　　　else：
　　　　　self.right＝Node(data)
else: #如果根節點不存在
self.data＝data #建立根節點
4.二叉樹的遍歷
(1)二叉樹的遍歷是指按照一定的_______________訪問二叉樹中的所有節點，使得每個節點都被訪問一次且__________________。
(2)根據訪問根節點的先后順序可以分為：前序遍歷、____________和____________。
①前序遍歷
前序遍歷，也稱為先序遍歷，前序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問_________，再訪問_________，最后訪問_________。
規則和次序
僅被訪問一次　
中序遍歷
后序遍歷
根節點
左子樹
右子樹
②中序遍歷
中序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問_________，再訪問根節點，最后訪問_________。
③后序遍歷
后序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問左子樹，再訪問右子樹，最后訪問_________。
左子樹
右子樹
根節點
二叉樹的三種遍歷是根據訪問根節點的先后次序來命名的，前序遍歷的訪問順序為根左右(BLR)，中序遍歷的訪問順序為左根右(LBR)，后序遍歷的訪問順序為左右根(LRB)。
例題精析
2
例1 下列二叉樹中，中序遍歷結果為 BAEDFC的是(　　)
C
解析　本題考查二叉樹遍歷。中序遍歷的方法：左子樹－根－右子樹，每棵子樹，都遵循以上規定。A選項中序遍歷為EDFBAC。B選項中序遍歷為BEDFAC。D選項中序遍歷為BACEDF。
解析　B選項的后序遍歷為GFDBEHCA。
B
例2 某二叉樹的樹形結構如圖所示，其前序遍歷結果為BDEFCA，則中序遍歷結果為(　　)
解析　本題考查二叉樹的遍歷。 前序遍歷可知B為二叉樹根節點，D和左子樹根節點，E和F為左子樹的左右孩子。C為F的左孩子，A為樹的右子樹。該樹結構如圖所示。因此中序遍歷為EDCFBA。
A
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
變式訓練　有一棵完全二叉樹，已知其中序遍歷結果是CADGBEIHJ，則其前序遍歷結果應該為(　　)
解析　該完全二叉樹有9個節點，因此共有4層，其中前3層是滿二叉樹(7個節點)，第4層有2個節點，畫出二叉樹的形態和中序遍歷路徑，可得前序遍歷序列。
B
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
例3 某二叉樹對應的一維數組表示如圖所示：
解析　根據存儲情況畫出樹如圖所示。
D
下列關于該二叉樹的說法正確的是(　　)
A.這是一棵完全二叉樹
B.節點F是節點D的孩子節點
C.該二叉樹有1個葉子結點
D.該二叉樹中序遍歷的結果是DBEACF
A選項最后一層節點沒有從左向右依次排列。B選項節點F是節點C的孩子節點。C選項該二叉樹有3個葉子結點。
變式訓練　某二叉樹用一維數組存儲結構如下表所示：
解析　本題考查二叉樹的相關知識。根據數組畫出樹如圖所示，可以得到正確的前序遍歷序列。
B
下列有關該二叉樹的說法正確的是(　　)
A.該樹度為 2 的節點有 4 個
B.該樹的前序遍歷為 A－B－D－E－G－H－C－F－I
C.該樹是完全二叉樹，其深度為 4
D.該樹中共有 3 個葉子節點，分別是 G、H、I
例4 某二叉樹的前序遍歷結果為ABCDEF，后序遍歷結果為CDBFEA，下列關于該二叉樹的說法，正確的是(　　)
解析　A為樹的根節點，在后序遍歷中，B沒有緊跟在A的前面，因此B是A的左孩子，CD是B的子樹，FE是A的右子樹。因此樹的形態可能有如圖所示的兩種情況。
B
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結果可能為CBDAEF
C.該二叉樹可能的形態有3種
D.該二叉樹度為2的節點可能有3個
A.該二叉樹不是完全二叉樹
B.該二叉樹的深度為4
C.該二叉樹的前序遍歷結果為ACBDEGF
D.該二叉樹所對應的一維數組表示為：
D
0 1 2 3 4 5 6 7 8 9 10 11
A C D B E F G
解析　本題考查二叉樹的性質和遍歷。后序遍歷確定根節點，中序遍歷由根節點位置劃分左右子樹。根節點A的左右子樹分別為CB和EGDF，C為子樹根，B為右節點。同理可以得到整棵樹的結構 。該樹深度為4但不是完
全二叉樹，前序遍歷結果為ACBDEGF，對應的一維數組為
0 1 2 3 4 5 6 7 8 9 10 11 12
A C D B E F G
隨堂檢測
3
C
解析　C選項中序遍歷為ACBDEF。
2.有一棵二叉樹如圖所示，下列說法正確的是(　　)
B
解析　本題考查樹的性質。A選項完全二叉樹第n－1層為滿二叉樹，不符合。C選項葉子節點有2個。D選項可以用數組或鏈表實現。
A.該二叉樹是一棵完全二叉樹，樹的高度為 3
B.該二叉樹的前序遍歷為 A，B，D，C，E
C.該二叉樹的葉子節點有4個
D.該二叉樹的建立只能使用數組來實現
3.下列二叉樹中，前序和中序遍歷結果一樣的選項是(　　)
D
解析　前序遍歷是根左右，中序遍歷是左根右，當左子樹不存在時，兩者相同。
4.有二叉樹形態如圖所示，后序遍歷結果為abcdefg，則樹中與c同層的節點是(　　)
A
解析　本題考查樹的遍歷和性質。從后序遍歷來看，g是根節點，左右子樹分別有3個，左子樹先于右子樹，因此abc是左子樹，def是右子樹，c是g的左孩子，f是g的右孩子。
A.f B.e
C.d D.b
5.某二叉樹從根節點開始，按從上到下、自左往右的順序用 A－G 字母表示，若補全為完全二叉樹后，用一維數組表示如圖所示。
C
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度為 3
B.節點 E 的父節點是 B
C.該二叉樹的中序遍歷結果為 BFDGACE
D.該二叉樹的葉子節點為 D、E、F、G
解析　本題考查二叉樹性質和遍歷。根據題意畫出二叉樹如圖所示：
該二叉樹的深度為 4，E 的父節點是 C，中序遍歷是 B－F－D－G－A－C－E，該二叉樹的葉子節點是F，G，E。
6.用一維數組表示二叉樹，如下表所示：
C
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有關該二叉樹的說法正確的是(　　)
A.該樹中共有 4 個葉子節點
B.該樹是完全二叉樹，其深度為 4
C.該樹的中序遍歷為 B－F－D－G－A－C－E
D.該二叉樹的結構圖為(如圖所示)
解析　本題考查二叉樹的基本知識。第3層節點的索引號為3，4，5，可見B沒有左子樹，但有右子樹，因此不可能是滿二叉樹，B也不是葉子節點。二叉樹形態如圖所示：
7.某二叉樹的前序遍歷結果為 GFDECAB，中序遍歷結果為 DFGCAEB。關于該二叉樹，以下說法，正確的是(　　)
B
解析　本題考查二叉樹的性質和遍歷。
根據前序遍歷和中序遍歷可畫出二叉樹。
A.該二叉樹的后序遍歷為 ADFCBEG
B.該二叉樹的深度為 4，節點 C 在第 3 層
C.該二叉樹的葉子節點數比非葉子節點數多一個
D.該二叉樹可以通過添加 3 個節點后變為完全二叉樹
8.某二叉樹的中序遍歷順序為DHBEAFCG，后序遍歷為HDEBFGCA，則節點E是(　　)
A.A節點的孩子節點 B.葉子節點
C.H節點的父親節點 D.F節點的兄弟節點
B
解析　本題考查樹的操作。由題意可知A為根節點，左子樹的中序遍歷為DHBE，觀察其后序遍歷，B為左子樹的根節點，E為左子樹的右子樹，因此節點 E是葉子節點。
4
鞏固與提升
基礎鞏固
能力提升
1.如圖所示的二叉樹，若要得到一個遞增序列，可以采用的遍歷方式是(　　)
B
解析　中序遍歷的結果為3，5，7，8，10，12，17。
A.前序遍歷 B.中序遍歷
C.后序遍歷 D.逐層遍歷
2.某二叉樹如圖所示，下列說法正確的是(　　)
D
解析　A選項共有6個葉子節點。B選項該樹倒數第2層不是滿二叉樹，因此不是完全二叉樹。C選項中序遍歷的結果為7*3＋1－4/2＋6，計算結果為26。
A.該二叉樹共有5個葉子節點
B.該二叉樹是一棵完全二叉樹
C.對該二叉樹進行中序遍歷后的計算結果是32
D.該二叉樹的后序遍歷序列為731＋*426＋/－
A.該二叉樹是一棵完全二叉樹
B.該二叉樹的葉子節點數是3個
C.該二叉樹的中序遍歷結果是DCBEAF
D.該二叉樹的度為2
A
解析　本題考查二叉樹的性質。該樹不是完全二叉樹。葉子節點有DEF，節點中最大的度為2。
4.數學表達式3/(5*2)可用二叉樹表示，如圖所示。
D
解析　本題考查二叉樹的遍歷。A選項完全二叉樹是指一棵深度為k的有n個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號，編號為i(1≤i≤n)的結點與滿二叉樹中編號為i的結點在二叉樹中的位置相同。3所在節點缺少葉子節點，故該二叉樹不是完全二叉樹。B選項3、5、2所在節點為葉子節點，數量為3。C選項前序遍歷結果為/3*52。
下列關于該二叉樹的說法，正確的是(　　)
A.是完全二叉樹
B.葉子節點數為2
C.前序遍歷結果為352*/
5.某二叉樹的樹形結構如圖所示，其后序遍歷結果為FBCEAD，則前序遍歷結果為(　　)
C
解析　根據樹的形態，畫出后序遍歷的路徑 ，
從而確定每個節點的值。
A.ABCDEF B.FEDCBA
C.DFACBE D.FDBCAE
6.已知某二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBDAEF，則下列說法正確的是 (　　)
A.其后序遍歷結果為DCBFEA
B.該二叉樹為完全二叉樹
C.該二叉樹深度為3，葉子節點數為3
D.該二叉樹用一維數組實現需要6個節點的存儲空間才能表示
C
解析　本題考查樹的性質和遍歷。根據前序遍歷確定根節點，中序遍歷區分左右子樹，畫出二叉樹。其后序遍歷結果為CDBFEA，該二叉樹最后一層葉子節點不是從左向右分布。該二叉樹深度為 3，葉子節點數為 3，該二叉樹補全為完全二叉樹，用一維數組實現需要 7 個節點的存儲空間才能表示。
7.有一棵二叉樹，如圖所示，下列說法正確的是(　　)
C
解析　本題考查二叉樹的相關知識。A選項節點 C 缺少左子樹，不是完全二叉樹。B選項該二叉樹的深度是 4。D選項節點C前沒有空節點。
A.此二叉樹是完全二叉樹
B.此二叉樹的深度是 3
C.此二叉樹的中序遍歷為 H－D－B－E－A－C－F
D.此二叉樹用一維數組表示為['A'，'B'，″，'C'，'D'，'E'，″，'F'，″，'H']
8.對于右圖所示的二叉樹，下列說法正確的是(　　)
D
解析　本題考查樹與二叉樹相關知識。A 選項樹的高度是4，但不是完全二叉樹。完全二叉樹是除最后一層外節點都滿節點，且最后一層節點都集中左邊位置上，而該二叉樹倒數第二層也沒有滿節點(c 沒有子節點)。B選項度為2的節點有2個，而葉子節點有3個。實際上，任意二叉樹的都滿足葉子節點數比度為2的節點數多一個。C選項若有數組存儲二叉樹時，c節點雖然沒有子節點，但是也要在數組中占據額外的兩個空元素位置，因此總容量應該是8個存儲空間。D選項后序遍歷為fdebca。
A.樹的高度是4，是一棵完全二叉樹
B.度為2的節點數比葉子節點數多1
C.若采用數組存儲法，需要6個存儲空間
D.該二叉樹的后序遍歷序列是fdebca
9.用一維數組表示二叉樹，如下表所示：
B
解析　本題考查樹的性質。根據存儲結構畫出的二叉樹如圖所示 。A選項3個葉子節點。
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有關該二叉樹的說法正確的是(　　)
A.該樹中共有4個葉子節點，度為2的節點有2個
B.該樹的中序遍歷為B－F－D－G－A－C－E
C.該樹是完全二叉樹，其深度為 4
D.該樹有7條邊
10.某二叉樹用一維數組實現的示意圖如下所示。
C
解析　本題考查二叉樹的知識。根據題意畫出二叉樹如圖所示：
0 1 2 3 4 5 6 7 8
A B C D E F
下列關于該二叉樹的說法，正確的是(　　)
A.是完全二叉樹 B.葉子節點數為3
C.前序遍歷結果為ABDFCE D.深度為3
該樹不是一顆完全二叉樹，葉子節點個數2，深度為4。前序遍歷時A－B－D－F－C－E。
11.二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(　　)
A.abcde B.abdec C.debac D.adbce
A
解析　本題考查樹的性質。從后序遍歷來看，a是根節點，b是左子樹，dce是右子樹；c是右子樹的根節點，d和e分別是左右子樹。因此前序遍歷為abcde。
12.有二叉樹的前序遍歷序列為A－B－C－E－F－G－D，中序遍歷序列為A－E－C－F－G－B－D，則關于該二叉樹的說法正確的是(　　)
A
解析　本題考查二叉樹的性質和遍歷。根據二叉樹的前序遍歷和中序遍歷畫出二叉樹。該二叉樹的根節點A的度為1，高度為5，節點G是節點F的右孩子。該二叉樹的葉子節點是E、G、D。
A.該二叉樹根節點的度為1 B.該二叉樹的高度為4
C.該二叉樹中節點G是節點C的左孩子 D.該二叉樹中葉子節點的個數為4
C
13.某二叉樹前序遍歷為ABDCE，后序遍歷為DBECA，則該二叉樹可能情況數量是(　　)
A.1 B.2 C.4 D.6
解析　本題考查二叉樹遍歷的相關知識。左右子樹的根節點都只有一個子節點，以下四種情況的前序和后序遍歷都符合題目要求：
14.如圖所示的二叉樹，根節點為0，每個節點的左子節點為0，右子節點為1，每一條從根到葉子的路徑都組成一個二進制數。例如：從根到葉子 a 的路徑組成二進制數 011，轉換為十進制數是 3。若某完全二叉樹共有 13 個節點，則它能表示的最大十進制數是(　　)
C
A.3 B.4 C.5 D.6
解析　本題考查二叉樹的性質。根據完全二叉樹的性質可知，該二叉樹共計13個節點。那么深度為4，前3層有7個節點，第4層有6個葉子節點，最大十進制數是0101B。
A.大好河山 B.河好山大 C.好山大河 D.山河好大
C
解析　本題考查樹的遍歷。前序遍歷為根左右，A選項任一節點沒有左節點，則前中序均為根右。B選項好是第1個左節點，則好是大的左節點，是河的根，山為河的兄弟。D選項任一節點沒有右節點。C選項好是大的左節點，山是右節點，或山是大的左節點，是好的父節點，則前序遍歷不對了。課時2　二叉樹的基本操作
課時目標
1.掌握使用數組和鏈表等數據結構建立二叉樹的方法。2.掌握二叉樹遍歷的基本操作方法。
1.建立二叉樹的方法
建立二叉樹的操作方法為：按照二叉樹層的順序進行，先由第________層開始，依次到下一層，在每一層中按照從__________的順序創建節點。
2.用數組實現二叉樹的創建
(1)完全二叉樹
①從二叉樹的__________開始，按__________、自左向右的順序對n個節點進行編號，根節點的編號為0，最后一個節點的編號為________。
②然后依次將二叉樹的節點用一組連續的數組元素來表示，節點編號與__________一一對應。
(2)非完全二叉樹
①對于非完全二叉樹，先將它補全為一棵________二叉樹，補上的節點及分支用虛線表示。
②然后按照完全二叉樹的方法，將節點存儲在數組中。
(3)使用數組(列表)建立二叉樹
空樹用None表示，非空二叉樹用包含三個元素的列表[d，l，r]表示，分別存儲著根節點的元素和左右子樹，因此二叉樹的list實現采用嵌套括號([])的形式。
用數組(列表)構建二叉樹的代碼如下：
def create_tree(tree，data)：
for i in range(len(data))：
depth＝0 #程序的第0層相當于樹的第1層
if i＝＝0: #根節點
　　　　 tree[depth]＝data[i]
else：
　　　　 #while循環結束表示找到存放數據的節點(索引)位置
　　　while tree[depth] ！＝0：
　　　 　　　if data[i]>tree[depth]：　#往右尋找
　　　　　　　　depth＝depth*2＋2　#父節點的右孩子位置
　　　　　　else：　　　　#往左尋找
　　　　　　　　depth＝depth*2＋1　#父節點的左孩子位置
tree[depth]＝data[i]　#找到數據應存放的節點位置，并存儲該節點
3.用鏈表實現二叉樹的創建
二叉樹用鏈表實現時，二叉樹的節點至少需要三個域：一個__________和兩個__________。如下圖所示：
Lchild data rchild
其中lchild和rchild是指針域，存放指向節點的左孩子節點和右孩子節點的指針，data是數據域。
使用鏈表建立搜索二叉樹如下：
def insert(self，data)：
if self.data：　　　#如果根節點不存在
if data　　　if self.left：
　　　 　　　self.left.insert(data) #遞歸調用往下一層
　　　　else：
　　　　　 self.left＝Node(data) #建立新節點存放數據
else: #插入值大于當前節點值
　　if self.right：
　　　self.right.insert(data)
　　　else：
　　　　　self.right＝Node(data)
else: #如果根節點不存在
self.data＝data #建立根節點
4.二叉樹的遍歷
(1)二叉樹的遍歷是指按照一定的____________訪問二叉樹中的所有節點，使得每個節點都被訪問一次且________________。
(2)根據訪問根節點的先后順序可以分為：前序遍歷、____________和____________。
①前序遍歷
前序遍歷，也稱為先序遍歷，前序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問________，再訪問________，最后訪問________。
②中序遍歷
中序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問________，再訪問根節點，最后訪問________。
③后序遍歷
后序遍歷的規則為：若二叉樹為空，則空操作返回；否則，先訪問左子樹，再訪問右子樹，最后訪問________。
二叉樹的三種遍歷是根據訪問根節點的先后次序來命名的，前序遍歷的訪問順序為根左右(BLR)，中序遍歷的訪問順序為左根右(LBR)，后序遍歷的訪問順序為左右根(LRB)。
例1 下列二叉樹中，中序遍歷結果為 BAEDFC的是(　　)
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　某二叉樹前序遍歷為ABDFGCEH，后序遍歷為FGDBHECA，則下列選項不可能是此二叉樹的是(　　)
例2 某二叉樹的樹形結構如圖所示，其前序遍歷結果為BDEFCA，則中序遍歷結果為(　　)
A.EDCFBA B.ECFDAB C.BFDEAC D.EDFCBA
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　有一棵完全二叉樹，已知其中序遍歷結果是CADGBEIHJ，則其前序遍歷結果應該為(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
例3 某二叉樹對應的一維數組表示如圖所示：
下列關于該二叉樹的說法正確的是(　　)
A.這是一棵完全二叉樹
B.節點F是節點D的孩子節點
C.該二叉樹有1個葉子結點
D.該二叉樹中序遍歷的結果是DBEACF
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　某二叉樹用一維數組存儲結構如下表所示：
下列有關該二叉樹的說法正確的是(　　)
A.該樹度為 2 的節點有 4 個
B.該樹的前序遍歷為 A－B－D－E－G－H－C－F－I
C.該樹是完全二叉樹，其深度為 4
D.該樹中共有 3 個葉子節點，分別是 G、H、I
例4 某二叉樹的前序遍歷結果為ABCDEF，后序遍歷結果為CDBFEA，下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結果可能為CBDAEF
C.該二叉樹可能的形態有3種
D.該二叉樹度為2的節點可能有3個
聽課筆記：　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　
變式訓練　已知某二叉樹的后序遍歷結果為BCGEFDA，中序遍歷結果為CBAEGDF，下列說法不正確的是(　　)
A.該二叉樹不是完全二叉樹
B.該二叉樹的深度為4
C.該二叉樹的前序遍歷結果為ACBDEGF
D.該二叉樹所對應的一維數組表示為：
0 1 2 3 4 5 6 7 8 9 10 11
A C D B E F G
1.某二叉樹中序遍歷為ABCDEF，則下列不可能是此二叉樹的是(　　)
2.有一棵二叉樹如圖所示，下列說法正確的是(　　)
A.該二叉樹是一棵完全二叉樹，樹的高度為 3
B.該二叉樹的前序遍歷為 A，B，D，C，E
C.該二叉樹的葉子節點有4個
D.該二叉樹的建立只能使用數組來實現
3.下列二叉樹中，前序和中序遍歷結果一樣的選項是(　　)
4.有二叉樹形態如圖所示，后序遍歷結果為abcdefg，則樹中與c同層的節點是(　　)
A.f B.e C.d D.b
5.某二叉樹從根節點開始，按從上到下、自左往右的順序用 A－G 字母表示，若補全為完全二叉樹后，用一維數組表示如圖所示。
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
A B C D E F G
下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度為 3
B.節點 E 的父節點是 B
C.該二叉樹的中序遍歷結果為 BFDGACE
D.該二叉樹的葉子節點為 D、E、F、G
6.用一維數組表示二叉樹，如下表所示：
0 1 2 3 4 5 6 7 8 9 10
A B C D E F G
下列有關該二叉樹的說法正確的是(　　)
A.該樹中共有 4 個葉子節點
B.該樹是完全二叉樹，其深度為 4
C.該樹的中序遍歷為 B－F－D－G－A－C－E
D.該二叉樹的結構圖為(如圖所示)
7.某二叉樹的前序遍歷結果為 GFDECAB，中序遍歷結果為 DFGCAEB。關于該二叉樹，以下說法，正確的是(　　)
A.該二叉樹的后序遍歷為 ADFCBEG
B.該二叉樹的深度為 4，節點 C 在第 3 層
C.該二叉樹的葉子節點數比非葉子節點數多一個
D.該二叉樹可以通過添加 3 個節點后變為完全二叉樹
8.某二叉樹的中序遍歷順序為DHBEAFCG，后序遍歷為HDEBFGCA，則節點E是(　　)
A.A節點的孩子節點 　B.葉子節點
C.H節點的父親節點 　 D.F節點的兄弟節點
課時2　二叉樹的基本操作
知識梳理
1.1　左到右
2.(1)①根節點　從上到下　n－1　②數組的下標　(2)①完全
3.數據域　指針域
4.(1)規則和次序　僅被訪問一次　(2)中序遍歷　后序遍歷
①根節點　左子樹　右子樹　②左子樹　右子樹　③根節點
例題精析
例1　C　[本題考查二叉樹遍歷。中序遍歷的方法：左子樹－根－右子樹，每棵子樹，都遵循以上規定。A選項中序遍歷為EDFBAC。B選項中序遍歷為BEDFAC。D選項中序遍歷為BACEDF。]
變式訓練　B　[B選項的后序遍歷為GFDBEHCA。]
例2　A　[本題考查二叉樹的遍歷。 前序遍歷可知B為二叉樹根節點，D和左子樹根節點，E和F為左子樹的左右孩子。C為F的左孩子，A為樹的右子樹。該樹結構如圖所示。因此中序遍歷為EDCFBA。]
變式訓練　B　[該完全二叉樹有9個節點，因此共有4層，其中前3層是滿二叉樹(7個節點)，第4層有2個節點，畫出二叉樹的形態和中序遍歷路徑，可得前序遍歷序列。]
例3　D　[根據存儲情況畫出樹如圖所示。
A選項最后一層節點沒有從左向右依次排列。B選項節點F是節點C的孩子節點。C選項該二叉樹有3個葉子結點。]
變式訓練　B　[本題考查二叉樹的相關知識。根據數組畫出樹如圖所示，可以得到正確的前序遍歷序列。]
例4　B　[A為樹的根節點，在后序遍歷中，B沒有緊跟在A的前面，因此B是A的左孩子，CD是B的子樹，FE是A的右子樹。因此樹的形態可能有如圖所示的兩種情況。]
變式訓練　D　[本題考查二叉樹的性質和遍歷。后序遍歷確定根節點，中序遍歷由根節點位置劃分左右子樹。根節點A的左右子樹分別為CB和EGDF，C為子樹根，B為右節點。同理可以得到整棵樹的結構。該樹深度為4但不是完全二叉樹，前序遍歷結果為ACBDEGF，對應的一維數組為]
0 1 2 3 4 5 6 7 8 9 10 11 12
A C D B E F G
隨堂檢測
1.C　[C選項中序遍歷為ACBDEF。]
2.B　[本題考查樹的性質。A選項完全二叉樹第n－1層為滿二叉樹，不符合。C選項葉子節點有2個。D選項可以用數組或鏈表實現。]
3.D　[前序遍歷是根左右，中序遍歷是左根右，當左子樹不存在時，兩者相同。]
4.A　[本題考查樹的遍歷和性質。從后序遍歷來看，g是根節點，左右子樹分別有3個，左子樹先于右子樹，因此abc是左子樹，def是右子樹，c是g的左孩子，f是g的右孩子。]
5.C　[本題考查二叉樹性質和遍歷。根據題意畫出二叉樹如圖所示：
該二叉樹的深度為 4，E 的父節點是 C，中序遍歷是 B－F－D－G－A－C－E，該二叉樹的葉子節點是F，G，E。]
6.C　[本題考查二叉樹的基本知識。第3層節點的索引號為3，4，5，可見B沒有左子樹，但有右子樹，因此不可能是滿二叉樹，B也不是葉子節點。二叉樹形態如圖所示：]
7.B　[本題考查二叉樹的性質和遍歷。
根據前序遍歷和中序遍歷可畫出二叉樹。]
8.B　[本題考查樹的操作。由題意可知A為根節點，左子樹的中序遍歷為DHBE，觀察其后序遍歷，B為左子樹的根節點，E為左子樹的右子樹，因此節點 E是葉子節點。]

展開更多......

收起↑