資源簡介

學習目標　1.通過描述現實世界中的樹形結構實例，了解樹的概念及性質，理解樹對有分支和層次的數據集合的描述方法；
2.在實際應用中，抽象二叉樹的數據結構形式，掌握二叉樹的概念及性質；
3.通過數組和鏈表實現樹的創建，理解樹形結構的數據節點存儲至數組和鏈表相應位置的方法；
4.按照一定的規則和次序訪問二叉樹中的所有節點，掌握前序遍歷、中序遍歷和后序遍歷等規則.
判定樹的依據：除根節點外，每個節點只有一個前驅，但可以有0個或多個后繼。樹體現的是一種層次和分支的關系，前驅表示他只能隸屬于一個層次，但他可能有0個或多個分支結構。節點數量：樹的度決定每層中最多的節點個數，決定了一棵深度為k層的樹總節點的個數。邊數量：邊的數量比總節點數量少一個。二叉樹的遍歷是將非線性結構轉換為線性結構，是按照一定的規則和次序(先訪問左節點，后訪問右節點)訪問二叉樹中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。
　　　　　　　　　　　　　　　　
(2023年6月浙江省選考)某二叉樹的樹形結構如圖所示，其前序遍歷結果為BDEFCA，則中序遍歷結果為(　　)
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
重難點1　節點和邊的數量關系
n個節點的樹有n－1條邊，邊的計算方法：從每節點到下一層孩子節點的邊數之和，葉子節點下方沒有邊。各種度數的節點個數與度數和乘積之和為n－1，是解決這類問題的關鍵。深度為k層的完全二叉樹從根節點到第k－1層是滿二叉樹，第k層的葉子節點從左向右依次排列。把握3個等量關系是解決該問題的關鍵：一是前k－1層總節點數為2k－2－1；二是葉子節點數為度為2的節點數加1，即n2＝n0＋1；三是度為1的節點數量為0或1。
例1 已知一棵完全二叉樹有8個葉子節點，下列說法正確的是(　　)
A.該完全二叉樹的高度可能為3
B.該完全二叉樹的形態只有一種
C.該完全二叉樹可能有1個度為1的節點
D.該完全二叉樹有9個度為2的節點
變式1 有一棵8個節點的二叉樹，下列說法正確的是(　　)
A.葉子節點可能為4個 B.第3層最多6個節點
C.度為1的節點最多4個 D.該樹的層數可能為3層
例2 假設完全二叉樹的樹根為第1層，樹中第10層有5個葉子節點，則完全二叉樹最多節點個數是(　　)
A.2047 B.2048 C.2037 D.2038
變式2 某完全二叉樹共有300個節點，該二叉樹的高度是(　　)
A.8 B.9 C.10 D.1l
例1 下列二叉樹中，中序遍歷結果為 BAEDFC的是(　　)
變式1 某完全二叉樹的后序遍歷為 EBAGDC，則下列說法正確的是(　　)
A.該樹的深度為4
B.該樹有2個葉子節點
C.該樹的節點B、G是兄弟節點
D.刪除節點E后，該樹的前序遍歷為CABDG
例2 用一維數組表示二叉樹，如表所示：
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.該二叉樹的結構圖為(如圖所示)
變式2 一個數學表達式可以用一棵表達式樹來表示，而一棵二叉樹可以用一維數組表示。有一棵表達式樹用一維數組表示如下。下列有關該表達式樹的說法正確的是(　　)
0 1 2 3 4 5 6 7 8
'/' ' '－ '4' '*' '8' '4' '6'
A.該表達式樹是一棵完全二叉樹
B.該表達式樹的左右子樹深度相差為1
C.該表達式樹的葉子結點有4個
D.該表達式樹中序遍歷的結果為4*6/8－4
重難點3　根據兩種遍歷序列確定一棵二叉樹
前序遍歷序列均為ABC的3個節點二叉樹可能形態如圖所示，
前3棵樹的后序遍歷均為CBA，前序遍歷為根左右，后序遍歷為左右根，當缺失一個孩子節點時，很難確定另外一個節點是左節點還是右節點，因此根據前后兩種遍歷序列，不能確定一棵二叉樹。前后序遍歷可以確定根節點，中序遍歷根據根節點劃分左右子樹。先將一棵樹分解成左右子樹，再對子樹再按上述方法來劃分，直到分解為最小的樹。
例題 某二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為ACBFEGD，下列說法正確的是(　　)
A.前序遍歷序列為DBACGFE
B.節點G為節點E的父節點
C.該二叉樹有兩個葉子節點
D.節點A與節點F為同一層
變式 二叉樹的中序遍歷為 BAEDFC，后序遍歷為 BEFDCA，其前序遍歷為(　　)
A.ABDEFC B.ABDCEF
C.ABCDEF D.ABCDFE
重難點1　節點和邊的數量關系
1.有樹結構的示意圖如圖所示，下列關于該樹的描述正確的是(　　)
A.該樹的度為6
B.該樹的葉子節點數量是7
C.節點I、J互為兄弟節點
D.該樹的深度為5
2.有一棵樹，節點的高度和個數如表所示。則葉子節點x的個數為(　　)
度 0 1 2 3 4
節點個數 x 4 3 2 1
A.8 B.9 C.10 D.11
3.已知一棵完全二叉樹的節點總數為12，則有關該二叉樹的說法正確的是(　　)
A.樹的度為12
B.樹的層數為3
C.葉子節點數為5
D.最后一層有5個節點
4.下列關于二叉樹的說法，不正確的是(　　)
A.二叉樹的數據元素之間呈非線性關系
B.二叉樹的第k層上最多有2k－1(k≥1)個節點
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹
D.具有100個節點的完全二叉樹有50個度為2的節點
5.某完全二叉樹的中序遍歷序列為abcdefgh，下列兩個選項屬于兄弟節點的是(　　)
A.節點a和節點b B.節點b和節點c
C.節點c和節點g D.節點d和節點f
6.已知一棵二叉樹有13個節點，樹中度為1的節點數為2，則該樹度為2的節點數為(　　)
A.4 B.5 C.6 D.11
重難點2　二叉樹的遍歷和數組表示
1.某二叉樹前序遍歷為ABDFGCEH，后序遍歷為FGDBHECA，則下列選項不可能是此二叉樹的是(　　)
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為“物技化數英語”，則中序遍歷結果為(　　)
A.語數英物化技 B.物數技化語英
C.語數物化技英 D.化物技英數語
3.某完全二叉樹，中序遍歷結果為“甲乙丙丁”，則后序遍歷結果是(　　)
A.甲乙丁丙 B.丙乙甲丁
C.甲丁丙乙 D.乙丁丙甲
4.某二叉樹的前序遍歷結果為ABC，若該二叉樹不是滿二叉樹，則其后序遍歷結果為(　　)
A.ABC B.BCA C.CBA D.CAB
5.用數組表示二叉樹的示意圖如表所示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
B D A E F C
下列說法正確的是(　　)
A.該二叉樹的深度為3
B.該二叉樹是完全二叉樹
C.該二叉樹有4個葉子節點
D.該二叉樹后序遍歷的結果為DCEFAB
6.某二叉樹的樹形結構如圖所示，其中序遍歷結果為FDGBAEC。若補全為完全二叉樹后，按從上到下、自左往右的順序用一維數組a存儲，其中根節點存儲于元素a[0]中，則元素a[6]的值為(　　)
A.D B.F C.G D.C
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.某二叉樹的前序遍歷結果為ABCEDF，在該二叉樹基礎上添加一個節點后的中序遍歷為BGCADEF，則添加節點后的后序遍歷結果為(　　)
A.CGBDFEA B.GCBADFE
C.CGBEFDA D.GCBDFEA
2.某二叉樹的前序遍歷結果為ABCDEF，后序遍歷結果為CDBFEA，下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結果可能為CBDAEF
C.該二叉樹可能的形態有3種
D.該二叉樹度為2的節點可能有3個
3.已知某二叉樹的前序遍歷是CABDEGF，中序遍歷為ABCGEDF，則其后序遍歷為(　　)
A.ABGEFDC B.BAFGEDC
C.ABFGECD D.BAGEFDC
4.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
5.已知某二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBDAEF，則下列說法正確的是(　　)
A.其后序遍歷結果為DCBFEA
B.該二叉樹為完全二叉樹
C.該二叉樹深度為3，葉子節點數為3
D.該二叉樹用一維數組實現需要6個節點的存儲空間才能表示
重難點1　節點和邊的數量關系
1.某樹的結構如圖，下列說法正確的是(　　)
A.該樹的度為4
B.該樹的高度為4
C.該樹的葉子節點為3個
D.節點F和G是兄弟節點
2.已知完全二叉樹T共有78個節點，則其葉子節點數量為(　　)
A.15 B.32 C.39 D.40
3.一棵有n(n>0)個節點的二叉樹，其節點為0度或2度，則此樹的最大高度是(　　)
A.(n＋1)∥2 B.n∥2
C.(n－1)∥2 D.int(log2n＋1)
4.現有一棵二叉樹，度為2的節點有10個，度為1的節點有5個，則這棵二叉樹共有節點數為(　　)
A.25 B.26
C.27 D.不確定
5.某二叉樹如圖所示，下列說法正確的是(　　)
A.節點D 、F都是節點B的孩子節點
B.該樹的高度和深度分別為2和3
C.該二叉樹中序遍歷的結果為DBEAGCF
D.若補全成高度為4的完全二叉樹則需增加4個節點
6.如圖所示，將二叉樹A的根節點與二叉樹B的根節點連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是(　　)
A.二叉樹C的高度為3
B.二叉樹C的葉子節點數量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結果是一個有序序列
7.下列Python表達式用于表示“一棵n個節點的二叉樹的葉子節點最大可能數量”，正確的是(　　)
A.n－1 B.n∥2 C.n∥2＋1 D.n/2
8.如圖所示的二叉樹，根節點為0，每個節點的左子節點為0，右子節點為1，每一條從根到葉子的路徑都組成一個二進制數。例如：從根到葉子a的路徑組成二進制數011，轉換為十進制數是3。若某完全二叉樹共有13個節點，則它能表示的最大十進制數是(　　)
A.3 B.4 C.5 D.6
9.有一棵二叉樹如圖所示，下列說法正確的是(　　)
A.該二叉樹是一棵完全二叉樹，樹的高度為3
B.該二叉樹的前序遍歷為A，B，D，C，E
C.該二叉樹的葉子節點有4個
D.該二叉樹的建立只能使用數組來實現
10.某二叉樹的結構如圖所示，下列說法不正確的是(　　)
A.該二叉樹是一棵完全二叉樹
B.該二叉樹的葉子節點數是3個
C.該二叉樹的中序遍歷結果是DCBEAF
D.該二叉樹的度為2
重難點2　二叉樹的遍歷和數組表示
1.某二叉樹中序遍歷為ABCDEF，則下列不可能是此二叉樹的是(　　)
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為BDEFCA，則前序遍歷結果為(　　)
A.ACFEDB B.ADBCFE
C.ADBFEC D.ADBEFC
3.有一棵完全二叉樹，已知其中序遍歷結果是CADGBEIHJ，則其前序遍歷結果應該為(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
4.有二叉樹形態如圖所示，后序遍歷結果為abcdefg，則樹中與c同層的節點是(　　)
A.f B.e C.d D.b
5.使用數組存儲某二叉樹的形式如圖所示，下列描述正確的是(　　)
0 1 2 3 4 5 6
A B C D
A.該二叉樹的深度為2
B.該二叉樹葉子節點個數為3
C.該二叉樹是一棵完全二叉樹
D.該二叉樹后序遍歷為BDCA
6.如圖所示用一維數組表示的二叉樹，其后序遍歷是(　　)
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
節點值 A B C D E F
A.FEDCBA B.ABDFCE
C.FDBECA D.BFDAEC
7.某二叉樹的樹形結構如圖所示，其后序遍歷結果為DBGEFCA，前序遍歷的結果為(　　)
A.ABCDEFG B.ABDCEGF
C.DBEGCFA D.ABDCGFE
8.某二叉樹前序遍歷的結果為“大好河山”，則中序遍歷的結果不可能是(　　)
A.大好河山 B.河山好大
C.好山大河 D.山河好大
9.某二叉樹前序遍歷的結果為“ABCD”，則中序遍歷的結果不可能是(　　)
A.ABCD B.CDBA
C.BDAC D.DCBA
10.某二叉樹的數組表示示意圖如圖所示，該二叉樹的后序遍歷序列為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
11.數學表達式3/(5*2)可用二叉樹表示，如圖所示。下列關于該二叉樹的說法，正確的是(　　)
A.是完全二叉樹
B.葉子節點數為2
C.前序遍歷結果為352*/
D.用數組表示為
/ 3 * 5 2
12.用一維數組來表示某二叉樹如表所示，則下列說法不正確的是(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.該二叉樹的深度為4
B.節點B有兩個孩子節點，分別為E和F
C.該二叉樹的中序遍歷結果為DBGEAFHC
D.葉子節點的數量比度為2的節點數量多1
13.某表達式樹如圖所示，下列說法錯誤的是(　　)
A.該表達式樹是一棵二叉樹，樹的度是2，高度是5
B.該樹的葉子節點數比度為2的節點數多1個
C.若采用完全二叉樹數組從0號位開始存儲，則節點b存儲在6號位
D.該表達式樹的前序遍歷序列是×d＋/fc－ab
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.有二叉樹的前序遍歷序列為A－B－C－E－F－G－D，中序遍歷序列為A－E－C－F－G－B－D，則關于該二叉樹的說法正確的是(　　)
A.該二叉樹根節點的度為1
B.該二叉樹的高度為4
C.該二叉樹中節點G是節點C的左孩子
D.該二叉樹中葉子節點的個數為4
2.某二叉樹的中序遍歷順序為DHBEAFCG，后序遍歷為HDEBFGCA，則節點E是(　　)
A.A節點的孩子節點 B.葉子節點
C.H節點的父親節點 D.F節點的兄弟節點
3.二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(　　)
A.abcde B.abdec C.debac D.adbce
4.已知一棵二叉樹的前序遍歷序列為abdgecfh，中序遍歷序列為dgbeachf，則該二叉樹的后序遍歷序列為(　　)
A.hfcegdba B.gdbehfca
C.gdbehfca D.gdebhfca
5.現有一棵二叉樹的中序遍歷序列為B－A－C－D－F－E，后序遍歷序列為A－B－F－E－D－C，則該二叉樹的前序遍歷序列是(　　)
A.C－B－A－D－F－E B.C－B－A－F－E－D
C.C－B－A－D－E－F D.C－B－A－E－F－D
6.某二叉樹的前序遍歷為A－B－D－E－C－F－G，中序遍歷為B－D－E－A－F－C－G，則下列說法正確的是(　　)
A.該二叉樹的葉子節點有4個
B.該二叉樹的后序遍歷為E－D－B－F－G－C－A
C.該二叉樹的高度為4，是一棵完全二叉樹
D.用數組來表示該樹，若A的下標為0，則E的下標為5
7.已知一棵二叉樹的前序遍歷序列為：A－B－D－C－E，后序遍歷序列為：D－B－E－C－A。則有關該二叉樹的中序遍歷序列說法正確的是(　　)
A.能唯一確定，中序遍歷序列為： B－D－A－E－C
B.不能唯一確定，中序遍歷序列可能為： B－D－A－E－C
C.能唯一確定，中序遍歷序列為： D－C－B－A－E
D.不能唯一確定，中序遍歷序列可能為： D－C－B－A－E
學習目標　1.通過描述現實世界中的樹形結構實例，了解樹的概念及性質，理解樹對有分支和層次的數據集合的描述方法；
2.在實際應用中，抽象二叉樹的數據結構形式，掌握二叉樹的概念及性質；
3.通過數組和鏈表實現樹的創建，理解樹形結構的數據節點存儲至數組和鏈表相應位置的方法；
4.按照一定的規則和次序訪問二叉樹中的所有節點，掌握前序遍歷、中序遍歷和后序遍歷等規則.
判定樹的依據：除根節點外，每個節點只有一個前驅，但可以有0個或多個后繼。樹體現的是一種層次和分支的關系，前驅表示他只能隸屬于一個層次，但他可能有0個或多個分支結構。節點數量：樹的度決定每層中最多的節點個數，決定了一棵深度為k層的樹總節點的個數。邊數量：邊的數量比總節點數量少一個。二叉樹的遍歷是將非線性結構轉換為線性結構，是按照一定的規則和次序(先訪問左節點，后訪問右節點)訪問二叉樹中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。
　　　　　　　　　　　　　　　　
(2023年6月浙江省選考)某二叉樹的樹形結構如圖所示，其前序遍歷結果為BDEFCA，則中序遍歷結果為(　　)
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
答案　A
解析　本題考查二叉樹的遍歷。 前序遍歷可知B為二叉樹根節點，D和左子樹根節點，E和F為左子樹的左右孩子。C為F的左孩子，A為樹的右子樹。該樹結構如圖所示。因此中序遍歷為EDCFBA。
重難點1　節點和邊的數量關系
n個節點的樹有n－1條邊，邊的計算方法：從每節點到下一層孩子節點的邊數之和，葉子節點下方沒有邊。各種度數的節點個數與度數和乘積之和為n－1，是解決這類問題的關鍵。深度為k層的完全二叉樹從根節點到第k－1層是滿二叉樹，第k層的葉子節點從左向右依次排列。把握3個等量關系是解決該問題的關鍵：一是前k－1層總節點數為2k－2－1；二是葉子節點數為度為2的節點數加1，即n2＝n0＋1；三是度為1的節點數量為0或1。
例1 已知一棵完全二叉樹有8個葉子節點，下列說法正確的是(　　)
A.該完全二叉樹的高度可能為3
B.該完全二叉樹的形態只有一種
C.該完全二叉樹可能有1個度為1的節點
D.該完全二叉樹有9個度為2的節點
思維點撥
明考向 本題考查樹的性質。根據樹的性質，2度節點個數為葉子節點個數減1，因此2度節點有7個。由于是完全二叉樹，1度節點的個數為0或1，因此總共節點數為15或16個
精　點　撥 A 根據總共節點數，可知該樹可能是3層，也可以是4層
B 當總節點是3層時，是一棵滿二叉樹，當節點為16時，在4層下有一個節點
C 當總節點為16時，有一個1度節點
D 2度節點個數為7個
答案　C
變式1 有一棵8個節點的二叉樹，下列說法正確的是(　　)
A.葉子節點可能為4個 B.第3層最多6個節點
C.度為1的節點最多4個 D.該樹的層數可能為3層
答案　A
解析　本題考查樹的性質。設n0、n1、n2分別為葉子節點數、1度節點數和2度節點數，2度節點數為葉子節點數加1，將n0＝n2＋1代入表達式n0＋n1＋n2＝8，2*n0－1＋n1＝8，當n1為1時，n0的值4，A選項成立。葉子節點數至少1個，代入后n1的值為7，即每一層上都只有一個節點，C選項錯誤。若該樹為滿二叉樹，樹的高度最小，因此至少4層，第3層最多只有3個葉子節點。
例2 假設完全二叉樹的樹根為第1層，樹中第10層有5個葉子節點，則完全二叉樹最多節點個數是(　　)
A.2047 B.2048 C.2037 D.2038
思維點撥
明考向 本題考查樹的性質
精點撥 根據完全二又樹的性質可知，葉子節點最多只出現在最下面2層，此題考查的是最多節點數，那么該二又樹應有11層。前10層節點：210－1＝1023第11層滿節點數為：20－1＝1024。因為第10層有S個葉子節點，所以第11層少10個節點，故總結點數為，1023＋1024－10＝2037
答案　C
變式2 某完全二叉樹共有300個節點，該二叉樹的高度是(　　)
A.8 B.9 C.10 D.1l
答案　B
解析　本題考查樹的性質。完全二叉樹倒數第2層是滿二叉樹，n層滿二叉樹總共節點數為2n－1，因此8層滿二叉樹節點數為255，該樹的高度為9。
重難點2　二叉樹的遍歷和數組表示
二叉樹的遍歷實現用線性結構來描述層次化、分支化的非線性結構。二叉樹的遍歷是按照一定的規則和次序(先訪問左節點，后訪問右節點)訪問二叉樹中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。一棵二叉樹必定先訪問左節點，再訪問右節點，將根節點所有位置分為前、中、后序三種遍歷方式。
二叉樹的建立可以用數組或者鏈表數據結構來實現。用數組實現時，需把二叉樹補全為一棵完全二叉樹，優點是能快速地檢索到某個節點的值，如果根節點編號為1，則第i個節點的左孩子編號為2*i，右孩子編號為2*i ＋1。缺點是當這棵二叉樹不是完全二叉樹時，會造成存儲空間的浪費。
例1 下列二叉樹中，中序遍歷結果為 BAEDFC的是(　　)
思維點撥
明考向 本題考查二叉樹遍歷。中序遍歷的方法：左子樹－根－右子樹，每個子樹，都遵循以上規定
精　點　撥 A 序遍歷結果為EDFBAC
B 序遍歷結果為BEDFAC
C 序遍歷結果為 BAEDFC
D 序遍歷結果為BACEDF
答案　C
變式1 某完全二叉樹的后序遍歷為 EBAGDC，則下列說法正確的是(　　)
A.該樹的深度為4
B.該樹有2個葉子節點
C.該樹的節點B、G是兄弟節點
D.刪除節點E后，該樹的前序遍歷為CABDG
答案　D
解析　本題考查二叉樹遍歷。由于是完全二叉樹，該樹的模型已經確定，畫出樹的形態如圖所示。A選項該樹的高度為3。B選項該樹有3個葉子節點。C選項B和G屬于不同的父節點，因此不是兄弟節點。D選項刪除節點E后，根據前序遍歷可知該二叉樹為CABDG。
例2 用一維數組表示二叉樹，如表所示：
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.該二叉樹的結構圖為(如圖所示)
思維點撥
明考向 本題考查二叉樹的基本知識。根據數組存儲情況，畫出對應的二叉樹如圖所示
精　點　撥 A 只有EFG共3個葉子節點
B 節點B和節點C沒有左子樹，因此不是完全二叉樹
C 根據左根右的原則遍歷該樹，得到中序遍歷為 B－F－D－G－A－C－E
D 該樹的形態與圖中所示有差別
答案　C
變式2 一個數學表達式可以用一棵表達式樹來表示，而一棵二叉樹可以用一維數組表示。有一棵表達式樹用一維數組表示如下。下列有關該表達式樹的說法正確的是(　　)
0 1 2 3 4 5 6 7 8
'/' ' '－ '4' '*' '8' '4' '6'
A.該表達式樹是一棵完全二叉樹
B.該表達式樹的左右子樹深度相差為1
C.該表達式樹的葉子結點有4個
D.該表達式樹中序遍歷的結果為4*6/8－4
答案　C
解析　畫出二叉樹如圖所示。A選項該表達式樹非完全二叉樹。B選項左子樹深度為3，右子樹深度1，相差2。C選項共有4個葉子節點。D選項該表達式中序遍歷的結果為(4*6－8)/4。
重難點3　根據兩種遍歷序列確定一棵二叉樹
前序遍歷序列均為ABC的3個節點二叉樹可能形態如圖所示，
前3棵樹的后序遍歷均為CBA，前序遍歷為根左右，后序遍歷為左右根，當缺失一個孩子節點時，很難確定另外一個節點是左節點還是右節點，因此根據前后兩種遍歷序列，不能確定一棵二叉樹。前后序遍歷可以確定根節點，中序遍歷根據根節點劃分左右子樹。先將一棵樹分解成左右子樹，再對子樹再按上述方法來劃分，直到分解為最小的樹。
例題 某二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為ACBFEGD，下列說法正確的是(　　)
A.前序遍歷序列為DBACGFE
B.節點G為節點E的父節點
C.該二叉樹有兩個葉子節點
D.節點A與節點F為同一層
思維點撥
明考向 根據前后序遍歷確定根節點，中序遍歷區分左右孩子。D為整棵樹的根節點，ABC為樹的左子樹，EFG為樹的右子樹。B為樹ABC根節點，A和C分別為左右孩子。G為樹EFG根節點，EF為左子樹，F為E的右孩子。畫出如圖所示的二叉樹
精　點　撥 A 前序遍歷序列為DBACGEF
B 節點E是節點G的左孩子
C 有ACF共3個葉子節點
D A處在第3層，F處在第4層
答案　B
變式 二叉樹的中序遍歷為 BAEDFC，后序遍歷為 BEFDCA，其前序遍歷為(　　)
A.ABDEFC B.ABDCEF
C.ABCDEF D.ABCDFE
答案　C
解析　本題考查二叉樹的遍歷。后序遍歷確定根節點，中序遍歷區分左右子樹。根據二叉樹的中序遍歷和后序遍歷可知，該二叉樹的形狀如圖所示，前序遍歷為：ABCDEF。
重難點1　節點和邊的數量關系
1.有樹結構的示意圖如圖所示，下列關于該樹的描述正確的是(　　)
A.該樹的度為6
B.該樹的葉子節點數量是7
C.節點I、J互為兄弟節點
D.該樹的深度為5
答案　B
解析　本題考查樹的基本概念。A選項度是指節點擁有的子樹個數，其中最大的節點的度就是樹的度。B選項共有H、I、J、C、K、L、M，7個葉子。C選項父節點是同一個的，才是兄弟節點。D選項該樹共4層，所以深度是4。
2.有一棵樹，節點的高度和個數如表所示。則葉子節點x的個數為(　　)
度 0 1 2 3 4
節點個數 x 4 3 2 1
A.8 B.9 C.10 D.11
答案　D
解析　本題考查樹的基本概念。樹中所有節點的度之和加1為節點總數，因此1*4＋2*3＋3*2＋4*1＋1＝21。節點數為x＋4＋3＋2＋1＝x＋10，因此可以得到葉子節點數為11個。
3.已知一棵完全二叉樹的節點總數為12，則有關該二叉樹的說法正確的是(　　)
A.樹的度為12
B.樹的層數為3
C.葉子節點數為5
D.最后一層有5個節點
答案　D
解析　本題考查二叉樹的基本性質。符合完全二叉樹的兩個條件為：①只有最下二層中的節點度數小于2；②最下一層的葉子節點都依次排列在該層最左邊位置。A選項度指樹的最大節點數。B選項若為滿二叉樹，第3層及前面所有節點數和為7，因此至少4層。C選項最后一層上有5個節點，即有葉子節點數為5，但第3層上還有一個葉子節點。
4.下列關于二叉樹的說法，不正確的是(　　)
A.二叉樹的數據元素之間呈非線性關系
B.二叉樹的第k層上最多有2k－1(k≥1)個節點
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹
D.具有100個節點的完全二叉樹有50個度為2的節點
答案　 D
解析　本題考查樹的性質。A選項樹表現一種層次性的非線性關系。D選項設二叉樹0度、1度和2度的節點個數分別為t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉樹1度節點個數為0或1，因此t2值為49。
5.某完全二叉樹的中序遍歷序列為abcdefgh，下列兩個選項屬于兄弟節點的是(　　)
A.節點a和節點b B.節點b和節點c
C.節點c和節點g D.節點d和節點f
答案　C
解析　本題考查樹的性質和遍歷。構建完全二叉樹如圖所示。A和B選項兩個節點不在同一層中。C選項節點c和節點g分別為節點e的左右孩子，屬于兄弟節點。D選項節點d和節點f的父親節點依次為c和g，因此不屬于兄弟節點。
6.已知一棵二叉樹有13個節點，樹中度為1的節點數為2，則該樹度為2的節點數為(　　)
A.4 B.5 C.6 D.11
答案　B
解析　本題考查二叉樹性質。根據二叉樹的性質，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。
重難點2　二叉樹的遍歷和數組表示
1.某二叉樹前序遍歷為ABDFGCEH，后序遍歷為FGDBHECA，則下列選項不可能是此二叉樹的是(　　)
答案　B
解析　B選項的后序遍歷為GFDBEHCA。
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為“物技化數英語”，則中序遍歷結果為(　　)
A.語數英物化技 B.物數技化語英
C.語數物化技英 D.化物技英數語
答案　B
解析　本題考查二叉樹遍歷。后序遍歷是“物技化數英語”可知，根節點為語，數英分別是語節點的左右孩子。物為數的左孩子，技為最高層的左孩子，化為數的右孩子。
3.某完全二叉樹，中序遍歷結果為“甲乙丙丁”，則后序遍歷結果是(　　)
A.甲乙丁丙 B.丙乙甲丁
C.甲丁丙乙 D.乙丁丙甲
答案　A
解析　畫出樹的形態如圖所示，可得后序遍歷為甲乙丁丙。
4.某二叉樹的前序遍歷結果為ABC，若該二叉樹不是滿二叉樹，則其后序遍歷結果為(　　)
A.ABC B.BCA C.CBA D.CAB
答案　C
解析　該二叉樹可能形態，滿足前序遍歷為ABC有4種形態，如圖所示，后序遍歷均為CBA。
5.用數組表示二叉樹的示意圖如表所示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
B D A E F C
下列說法正確的是(　　)
A.該二叉樹的深度為3
B.該二叉樹是完全二叉樹
C.該二叉樹有4個葉子節點
D.該二叉樹后序遍歷的結果為DCEFAB
答案　D
解析　畫出該樹的形態如圖所示。A選項該樹深度為4。C選項該樹有3個葉子節點。
6.某二叉樹的樹形結構如圖所示，其中序遍歷結果為FDGBAEC。若補全為完全二叉樹后，按從上到下、自左往右的順序用一維數組a存儲，其中根節點存儲于元素a[0]中，則元素a[6]的值為(　　)
A.D B.F C.G D.C
答案　D
解析　元素a[6]位于二叉樹從上至下，從左到右第7個位置，即第3層最后一個。根據中序遍歷畫出圖示如圖所示。
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.某二叉樹的前序遍歷結果為ABCEDF，在該二叉樹基礎上添加一個節點后的中序遍歷為BGCADEF，則添加節點后的后序遍歷結果為(　　)
A.CGBDFEA B.GCBADFE
C.CGBEFDA D.GCBDFEA
答案　D
解析　根據前序遍歷確定根節點為A，左子樹為BC，左子樹根為B，右子樹為EDF，右子樹根為E，新增節點G為節點C的左孩子，最終后續遍結果為GCBDFEA。
2.某二叉樹的前序遍歷結果為ABCDEF，后序遍歷結果為CDBFEA，下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結果可能為CBDAEF
C.該二叉樹可能的形態有3種
D.該二叉樹度為2的節點可能有3個
答案　B
解析　A為樹的根節點，在后序遍歷中，B沒有緊跟在A的前面，因此B是A的左孩子，CD是B的子樹，FE是A的右子樹。因此樹的形態可能有如圖所示的兩種情況。
3.已知某二叉樹的前序遍歷是CABDEGF，中序遍歷為ABCGEDF，則其后序遍歷為(　　)
A.ABGEFDC B.BAFGEDC
C.ABFGECD D.BAGEFDC
答案　D
解析　節點C為整棵樹的節節點，左子樹為AB，節點B為節點A的左子樹。節點D為右子樹的根節點，節點F為節點D的右子樹。
4.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
答案　B
解析　本題考查二叉樹的相關知識。前序遍歷找出根A，中序遍歷根據根的位置，區別左右子樹。A選項左子樹為C，但C在前序遍歷中后于B訪問，不正確。C選項同A選項。D選項該樹沒有左子樹，在右子樹中，B為根，D為B的左孩子，但在前序中D后于C訪問，不正確。B選項前序遍歷為根
左右，中序遍歷為左根右，當樹缺失左孩子時，前中序遍歷是一樣的。
5.已知某二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBDAEF，則下列說法正確的是(　　)
A.其后序遍歷結果為DCBFEA
B.該二叉樹為完全二叉樹
C.該二叉樹深度為3，葉子節點數為3
D.該二叉樹用一維數組實現需要6個節點的存儲空間才能表示
答案　C
解析　本題考查樹的性質和遍歷。根據前序遍歷確定根節點，中序遍歷區分左右子樹，畫出二叉樹。其后序遍歷結果為CDBFEA，該二叉樹最后一層葉子節點不是從左向右分布。該二叉樹深度為3，葉子節點數為3，該二叉樹補全為完全二叉樹，用一維數組實現需要7個節點的存儲空間才能表示。
重難點1　節點和邊的數量關系
1.某樹的結構如圖，下列說法正確的是(　　)
A.該樹的度為4
B.該樹的高度為4
C.該樹的葉子節點為3個
D.節點F和G是兄弟節點
答案　B
解析　本題考查樹的性質。A選項數的度取決于節點的最大度數，因此該樹的度為3。
2.已知完全二叉樹T共有78個節點，則其葉子節點數量為(　　)
A.15 B.32 C.39 D.40
答案　C
解析　設二叉樹0度、1度和2度的節點個數分別為t0，t1，t2，有等式t0＋t1＋t2＝78和t0＝t2＋1成立，代入可得t0＋t1＋t0－1＝78，且完全二叉樹1度節點個數為0或1，因此t1值為1。
3.一棵有n(n>0)個節點的二叉樹，其節點為0度或2度，則此樹的最大高度是(　　)
A.(n＋1)∥2 B.n∥2
C.(n－1)∥2 D.int(log2n＋1)
答案　A
解析　本題考查二叉樹基本性質。該二叉樹的節點的度都為0或2，即除根節點外，其每個節點都有一個兄弟節點。題目要求樹的最大高度，每層就只有2個節點(除了根節點)，若總節點數加上1，相當于令第1層也變成兩個節點，那么總層數就是(n＋1)∥2。
4.現有一棵二叉樹，度為2的節點有10個，度為1的節點有5個，則這棵二叉樹共有節點數為(　　)
A.25 B.26
C.27 D.不確定
答案　B
解析　本題考查二叉樹性質。根據二叉樹性質可知n0＝n2＋1，總的節點數量為10＋11＋5＝26。
5.某二叉樹如圖所示，下列說法正確的是(　　)
A.節點D 、F都是節點B的孩子節點
B.該樹的高度和深度分別為2和3
C.該二叉樹中序遍歷的結果為DBEAGCF
D.若補全成高度為4的完全二叉樹則需增加4個節點
答案　D
解析　A選項F不是B的子節點。B選項樹最高有4層，最大高度為2。C選項中序遍歷為DBEGACF。D選項完全二叉樹中，前3層為滿二叉樹，共有7個節點，少一個節點。第4層從左至右依次排列，還要補3個節點，因此共需補4個節點。
6.如圖所示，將二叉樹A的根節點與二叉樹B的根節點連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是(　　)
A.二叉樹C的高度為3
B.二叉樹C的葉子節點數量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結果是一個有序序列
答案　C
解析　本題考查二叉樹的性質和遍歷。新二叉樹高度為4；葉子節點數量為4，是一棵完全二叉樹；中序遍歷的結果為84251637，不是一個有序序列。
7.下列Python表達式用于表示“一棵n個節點的二叉樹的葉子節點最大可能數量”，正確的是(　　)
A.n－1 B.n∥2 C.n∥2＋1 D.n/2
答案　C
解析　本題考查二叉樹的性質。由n0＝n2＋1和n0＋n1＋n2＝n可得到n0＋n1＋n0－1＝n，二叉樹度為1的節點個數n1為0時，葉子節點個數n0達到最多，得到n0＝(n＋1)/2。總節點個數是奇數個，(n＋1)/2等價于n∥2＋1。
8.如圖所示的二叉樹，根節點為0，每個節點的左子節點為0，右子節點為1，每一條從根到葉子的路徑都組成一個二進制數。例如：從根到葉子a的路徑組成二進制數011，轉換為十進制數是3。若某完全二叉樹共有13個節點，則它能表示的最大十進制數是(　　)
A.3 B.4 C.5 D.6
答案　C
解析　本題考查二叉樹的性質。根據完全二叉樹的性質可知，該二叉樹共計13個節點。那么深度為4，前3層有7個節點，第4層有6個葉子節點，最大十進制數是0101B。
9.有一棵二叉樹如圖所示，下列說法正確的是(　　)
A.該二叉樹是一棵完全二叉樹，樹的高度為3
B.該二叉樹的前序遍歷為A，B，D，C，E
C.該二叉樹的葉子節點有4個
D.該二叉樹的建立只能使用數組來實現
答案　 B
解析　 本題考查樹的性質。A選項完全二叉樹第n－1層為滿二叉樹，不符合。C選項葉子節點有2個。D選項可以用數組或鏈表實現。
10.某二叉樹的結構如圖所示，下列說法不正確的是(　　)
A.該二叉樹是一棵完全二叉樹
B.該二叉樹的葉子節點數是3個
C.該二叉樹的中序遍歷結果是DCBEAF
D.該二叉樹的度為2
答案　A
解析　本題考查二叉樹的性質。該樹不是完全二叉樹。葉子節點有DEF，節點中最大的度為2。
重難點2　二叉樹的遍歷和數組表示
1.某二叉樹中序遍歷為ABCDEF，則下列不可能是此二叉樹的是(　　)
答案　C
解析　C選項中序遍歷為ACBDEF。
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為BDEFCA，則前序遍歷結果為(　　)
A.ACFEDB B.ADBCFE
C.ADBFEC D.ADBEFC
答案　B
解析　先根據樹的形態畫出前序遍歷的路徑，再將遍歷到的各個節點填上去，得到后序遍歷為BDEFCA。
3.有一棵完全二叉樹，已知其中序遍歷結果是CADGBEIHJ，則其前序遍歷結果應該為(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
答案　B
解析　該完全二叉樹有9個節點，因此共有4層，其中前3層是滿二叉樹(7個節點)，第4層有2個節點，畫出二叉樹的形態和中序遍歷路徑，可得前序遍歷序列。
4.有二叉樹形態如圖所示，后序遍歷結果為abcdefg，則樹中與c同層的節點是(　　)
A.f B.e C.d D.b
答案　A
解析　本題考查樹的遍歷和性質。從后序遍歷來看，g是根節點，左右子樹分別有個，左子樹先于右子樹，因此abc是左子樹，def是右子樹，c是g的左孩子，f是g的右孩子。
5.使用數組存儲某二叉樹的形式如圖所示，下列描述正確的是(　　)
0 1 2 3 4 5 6
A B C D
A.該二叉樹的深度為2
B.該二叉樹葉子節點個數為3
C.該二叉樹是一棵完全二叉樹
D.該二叉樹后序遍歷為BDCA
答案　D
解析　畫出樹的結構如圖所示：該樹深度為3，葉子節點有2個，不是完全二叉樹。
6.如圖所示用一維數組表示的二叉樹，其后序遍歷是(　　)
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
節點值 A B C D E F
A.FEDCBA B.ABDFCE
C.FDBECA D.BFDAEC
答案　C
解析　畫出樹的結構如圖所示：可以得到后序遍歷序列。
7.某二叉樹的樹形結構如圖所示，其后序遍歷結果為DBGEFCA，前序遍歷的結果為(　　)
A.ABCDEFG B.ABDCEGF
C.DBEGCFA D.ABDCGFE
答案　D
解析　先畫出該樹的后序遍歷路徑，再把各個節點填上去，最后寫出前序遍歷序列。
8.某二叉樹前序遍歷的結果為“大好河山”，則中序遍歷的結果不可能是(　　)
A.大好河山 B.河山好大
C.好山大河 D.山河好大
答案　C
解析　本題考查樹的遍歷。前序遍歷為根左右，A選項任一節點沒有左節點，則前中序均為根右。B選項河是第1個左節點，則好是大的左節點，是河的根，山為河的兄弟。D選項任一節點沒有右節點。C選項好是大的左節點，山是右節點，或山是大的左節點，是好的父節點，則前序遍歷不對了。
9.某二叉樹前序遍歷的結果為“ABCD”，則中序遍歷的結果不可能是(　　)
A.ABCD B.CDBA
C.BDAC D.DCBA
答案　C
解析　本題考查二叉樹相關概念。前序遍歷為根左右，中序遍歷為左根右。A選項當左子樹缺失時，遍歷序列相同。D選項當右子樹缺失時，遍歷序列正好相反。節點D可能是整棵樹的右子樹，也可能是左子樹中的一個右孩子，但節點C一定先于節點D訪問，因此C選項不可能。B選項當D是C的右孩子，C缺失左孩子，整棵樹沒有右子樹。
10.某二叉樹的數組表示示意圖如圖所示，該二叉樹的后序遍歷序列為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
答案　B
解析　本題考查二叉樹的遍歷。根據題意畫出二叉樹如圖所示
后序遍歷是：BFDGECA。
11.數學表達式3/(5*2)可用二叉樹表示，如圖所示。下列關于該二叉樹的說法，正確的是(　　)
A.是完全二叉樹
B.葉子節點數為2
C.前序遍歷結果為352*/
D.用數組表示為
/ 3 * 5 2
答案　D
解析　本題考查二叉樹的遍歷。A選項完全二叉樹是指一棵深度為k的有n節點的二叉樹，對樹中的節點按從上至下、從左到右的順序進行編號，編號為i(1≤i≤n)的結點與滿二叉樹中編號為i的節點在二叉樹中的位置相同。3所在節點缺少葉子節點，故該二叉樹不是完全二叉樹。B選項3、5、2所在節點為葉子節點，數量為3。C選項前序遍歷結果為/3*52。D選項將圖中二叉樹補全為完全二叉樹，依次把完全二叉樹中原二叉樹的節點用一維數組的各元素表示。
12.用一維數組來表示某二叉樹如表所示，則下列說法不正確的是(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.該二叉樹的深度為4
B.節點B有兩個孩子節點，分別為E和F
C.該二叉樹的中序遍歷結果為DBGEAFHC
D.葉子節點的數量比度為2的節點數量多1
答案　B
解析　構建的二叉樹如圖。
13.某表達式樹如圖所示，下列說法錯誤的是(　　)
A.該表達式樹是一棵二叉樹，樹的度是2，高度是5
B.該樹的葉子節點數比度為2的節點數多1個
C.若采用完全二叉樹數組從0號位開始存儲，則節點b存儲在6號位
D.該表達式樹的前序遍歷序列是×d＋/fc－ab
答案　D
解析　本題考查樹與二叉樹相關知識。樹的度是最大的節點的度，樹的高度是節點最大的層數，A選項在任意一棵二叉樹中都有n0＝n2＋1的性質，即葉子節點數等于度為2的節點數多一個；非完全二叉樹若用完全二叉樹保存時需將樹補成完全二叉樹，即第3層需補全d節點的兩個孩子節點，此時節點b存儲在第6號位置上。D選項該表達式樹的前序遍歷序列是×d＋/f－cab，對節點“－”而言先于其子節點c。
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.有二叉樹的前序遍歷序列為A－B－C－E－F－G－D，中序遍歷序列為A－E－C－F－G－B－D，則關于該二叉樹的說法正確的是(　　)
A.該二叉樹根節點的度為1
B.該二叉樹的高度為4
C.該二叉樹中節點G是節點C的左孩子
D.該二叉樹中葉子節點的個數為4
答案　A
解析　本題考查二叉樹的性質和遍歷。根據二叉樹的前序遍歷和中序遍歷畫出二叉樹。該二叉樹的根節點A的度為1，高度為5，節點G是節點F的右孩子。該二叉樹的葉子節點是E、G、D。
2.某二叉樹的中序遍歷順序為DHBEAFCG，后序遍歷為HDEBFGCA，則節點E是(　　)
A.A節點的孩子節點 B.葉子節點
C.H節點的父親節點 D.F節點的兄弟節點
答案　B
解析　本題考查樹的操作。由題意可知A為根節點，左子樹的中序遍歷為DHBE，觀察其后序遍歷，B為左子樹的根節點，E為左子樹的右子樹，因此節點E是葉子節點。
3.二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(　　)
A.abcde B.abdec C.debac D.adbce
答案　A
解析　本題考查樹的性質。從后序遍歷來看，a是根節點，b是左子樹，dce是右子樹；c是右子樹的根節點，d和e分別是左右子樹。因此前序遍歷為abcde。
4.已知一棵二叉樹的前序遍歷序列為abdgecfh，中序遍歷序列為dgbeachf，則該二叉樹的后序遍歷序列為(　　)
A.hfcegdba B.gdbehfca
C.gdbehfca D.gdebhfca
答案　D
解析　根據二叉樹的前序遍歷和中序遍歷確定唯一的二叉樹，再得出后序遍歷。
5.現有一棵二叉樹的中序遍歷序列為B－A－C－D－F－E，后序遍歷序列為A－B－F－E－D－C，則該二叉樹的前序遍歷序列是(　　)
A.C－B－A－D－F－E B.C－B－A－F－E－D
C.C－B－A－D－E－F D.C－B－A－E－F－D
答案　C
解析　本題考查樹的遍歷。由后序遍歷可知C為根節點，根據中序遍歷樹可分為(BA)C(DFE)，A為B的左子樹，FE為D的右子樹，F為E的左子樹。
6.某二叉樹的前序遍歷為A－B－D－E－C－F－G，中序遍歷為B－D－E－A－F－C－G，則下列說法正確的是(　　)
A.該二叉樹的葉子節點有4個
B.該二叉樹的后序遍歷為E－D－B－F－G－C－A
C.該二叉樹的高度為4，是一棵完全二叉樹
D.用數組來表示該樹，若A的下標為0，則E的下標為5
答案　B
解析　本題考查二叉樹的性質、存儲和遍歷。根據前序遍歷，可知A為根節點，中序序列可以劃分為(BDE)A(FCG)，則左子樹BDE中，B為根節點，DE為右子樹，DE子樹中，E為D的右節點。右子樹FCG中，C為根節點，F和G分別為左右子樹。根據上述描述，畫出樹，可知葉子節點有EFG 3個，后序遍歷為EDBFGCA，樹的高度為4，但不是完全二叉樹。
7.已知一棵二叉樹的前序遍歷序列為：A－B－D－C－E，后序遍歷序列為：D－B－E－C－A。則有關該二叉樹的中序遍歷序列說法正確的是(　　)
A.能唯一確定，中序遍歷序列為： B－D－A－E－C
B.不能唯一確定，中序遍歷序列可能為： B－D－A－E－C
C.能唯一確定，中序遍歷序列為： D－C－B－A－E
D.不能唯一確定，中序遍歷序列可能為： D－C－B－A－E
答案　B
解析　本題考查二叉樹遍歷相關知識點。只知道前序遍歷和后序遍歷不能得到唯一的二叉樹，故排除AC。假設B有可能，左子樹為BD，右子樹為EC。假設D有可能，得出左子樹為DCB，右子樹為E，后序遍歷不可能是D－B－E－C－A。(共74張PPT)
第三部分　數據的存儲與邏輯結構
專題14 樹
1.通過描述現實世界中的樹形結構實例，了解樹的概念及性質，理解樹對有分支和層次的數據集合的描述方法；
2.在實際應用中，抽象二叉樹的數據結構形式，掌握二叉樹的概念及性質；
3.通過數組和鏈表實現樹的創建，理解樹形結構的數據節點存儲至數組和鏈表相應位置的方法；
4.按照一定的規則和次序訪問二叉樹中的所有節點，掌握前序遍歷、中序遍歷和后序遍歷等規則.
目 錄
CONTENTS
體系構建
01
真題再現
02
考點精練
03
當堂檢測
04
課后練習
05
體系構建
1
判定樹的依據：除根節點外，每個節點只有一個前驅，但可以有0個或多個后繼。樹體現的是一種層次和分支的關系，前驅表示他只能隸屬于一個層次，但他可能有0個或多個分支結構。節點數量：樹的度決定每層中最多的節點個數，決定了一棵深度為k層的樹總節點的個數。邊數量：邊的數量比總節點數量少一個。二叉樹的遍歷是將非線性結構轉換為線性結構，是按照一定的規則和次序(先訪問左節點，后訪問右節點)訪問二叉樹中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。
真題再現
2
(2023年6月浙江省選考)某二叉樹的樹形結構如圖所示，其前序遍歷結果為BDEFCA，則中序遍歷結果為(　　)
解析　本題考查二叉樹的遍歷。 前序遍歷可知B為二叉樹根節點，D和左子樹根節點，E和F為左子樹的左右孩子。C為F的左孩子，A為樹的右子樹。該樹結構如圖所示。因此中序遍歷為EDCFBA。
A
A.EDCFBA B.ECFDAB
C.BFDEAC D.EDFCBA
考點精練
3
重難點1　節點和邊的數量關系
n個節點的樹有n－1條邊，邊的計算方法：從每節點到下一層孩子節點的邊數之和，葉子節點下方沒有邊。各種度數的節點個數與度數和乘積之和為n－1，是解決這類問題的關鍵。深度為k層的完全二叉樹從根節點到第k－1層是滿二叉樹，第k層的葉子節點從左向右依次排列。把握3個等量關系是解決該問題的關鍵：一是前k－1層總節點數為2k－2－1；二是葉子節點數為度為2的節點數加1，即n2＝n0＋1；三是度為1的節點數量為0或1。
例1 已知一棵完全二叉樹有8個葉子節點，下列說法正確的是(　　)
A.該完全二叉樹的高度可能為3
B.該完全二叉樹的形態只有一種
C.該完全二叉樹可能有1個度為1的節點
D.該完全二叉樹有9個度為2的節點
C
思維點撥
明考向 本題考查樹的性質。根據樹的性質，2度節點個數為葉子節點個數減1，因此2度節點有7個。由于是完全二叉樹，1度節點的個數為0或1，因此總共節點數為15或16個
精　點　撥 A 根據總共節點數，可知該樹可能是3層，也可以是4層
B 當總節點是3層時，是一棵滿二叉樹，當節點為16時，在4層下有一個節點
C 當總節點為16時，有一個1度節點
D 2度節點個數為7個
變式1 有一棵8個節點的二叉樹，下列說法正確的是(　　)
A.葉子節點可能為4個 B.第3層最多6個節點
C.度為1的節點最多4個 D.該樹的層數可能為3層
A
解析　本題考查樹的性質。設n0、n1、n2分別為葉子節點數、1度節點數和2度節點數，2度節點數為葉子節點數加1，將n0＝n2＋1代入表達式n0＋n1＋n2＝8，2*n0－1＋n1＝8，當n1為1時，n0的值4，A選項成立。葉子節點數至少1個，代入后n1的值為7，即每一層上都只有一個節點，C選項錯誤。若該樹為滿二叉樹，樹的高度最小，因此至少4層，第3層最多只有3個葉子節點。
例2 假設完全二叉樹的樹根為第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
變式2 某完全二叉樹共有300個節點，該二叉樹的高度是(　　)
A.8 B.9 C.10 D.1l
B
解析　本題考查樹的性質。完全二叉樹倒數第2層是滿二叉樹，n層滿二叉樹總共節點數為2n－1，因此8層滿二叉樹節點數為255，該樹的高度為9。
重難點2　二叉樹的遍歷和數組表示
二叉樹的遍歷實現用線性結構來描述層次化、分支化的非線性結構。二叉樹的遍歷是按照一定的規則和次序(先訪問左節點，后訪問右節點)訪問二叉樹中的所有節點，使得每個節點都被訪問一次且僅被訪問一次。一棵二叉樹必定先訪問左節點，再訪問右節點，將根節點所有位置分為前、中、后序三種遍歷方式。
二叉樹的建立可以用數組或者鏈表數據結構來實現。用數組實現時，需把二叉樹補全為一棵完全二叉樹，優點是能快速地檢索到某個節點的值，如果根節點編號為1，則第i個節點的左孩子編號為2*i，右孩子編號為2*i ＋1。缺點是當這棵二叉樹不是完全二叉樹時，會造成存儲空間的浪費。
例1 下列二叉樹中，中序遍歷結果為 BAEDFC的是(　　)
C
思維點撥
明考向 本題考查二叉樹遍歷。中序遍歷的方法：左子樹－根－右子樹，每個子樹，都遵循以上規定
精　點　撥 A 序遍歷結果為EDFBAC
B 序遍歷結果為BEDFAC
C 序遍歷結果為 BAEDFC
D 序遍歷結果為BACEDF
變式1 某完全二叉樹的后序遍歷為 EBAGDC，則下列說法正確的是(　　)
A.該樹的深度為4
B.該樹有2個葉子節點
C.該樹的節點B、G是兄弟節點
D.刪除節點E后，該樹的前序遍歷為CABDG
D
解析　本題考查二叉樹遍歷。由于是完全二叉樹，該樹的模型已經確定，畫出樹的形態如圖所示。A選項該樹的高度為3。B選項該樹有3個葉子節點。C選項B和G屬于不同的父節點，因此不是兄弟節點。D選項刪除節點E后，根據前序遍歷可知該二叉樹為CABDG。
例2 用一維數組表示二叉樹，如表所示：
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.該二叉樹的結構圖為(如圖所示)
思維點撥
明考向 本題考查二叉樹的基本知識。根據數組
存儲情況，畫出對應的二叉樹如圖所示
精 點 撥 A 只有EFG共3個葉子節點
B 節點B和節點C沒有左子樹，因此不是完全二叉樹
C 根據左根右的原則遍歷該樹，得到中序遍歷為 B－F－D－G－A－C－E
D 該樹的形態與圖中所示有差別
變式2 一個數學表達式可以用一棵表達式樹來表示，而一棵二叉樹可以用一維數組表示。有一棵表達式樹用一維數組表示如下。下列有關該表達式樹的說法正確的是(　　)
C
0 1 2 3 4 5 6 7 8
'/' ' '－ '4' '*' '8' '4' '6'
A.該表達式樹是一棵完全二叉樹
B.該表達式樹的左右子樹深度相差為1
C.該表達式樹的葉子結點有4個
D.該表達式樹中序遍歷的結果為4*6/8－4
解析　畫出二叉樹如圖所示。A選項該表達式樹非完全二叉樹。B選項左子樹深度為3，右子樹深度1，相差2。C選項共有4個葉子節點。D選項該表達式中序遍歷的結果為(4*6－8)/4。
重難點3　根據兩種遍歷序列確定一棵二叉樹
前序遍歷序列均為ABC的3個節點二叉樹可能形態如圖所示，
前3棵樹的后序遍歷均為CBA，前序遍歷為根左右，后序遍歷為左右根，當缺失一個孩子節點時，很難確定另外一個節點是左節點還是右節點，因此根據前后兩種遍歷序列，不能確定一棵二叉樹。前后序遍歷可以確定根節點，中序遍歷根據根節點劃分左右子樹。先將一棵樹分解成左右子樹，再對子樹再按上述方法來劃分，直到分解為最小的樹。
例題 某二叉樹的中序遍歷序列為ABCDEFG，后序遍歷序列為ACBFEGD，下列說法正確的是(　　)
A.前序遍歷序列為DBACGFE B.節點G為節點E的父節點
C.該二叉樹有兩個葉子節點 D.節點A與節點F為同一層
B
思維點撥
明考向 根據前后序遍歷確定根節點，中序遍歷區分左右孩子。
D為整棵樹的根節點，ABC為樹的左子樹，EFG為樹
的右子樹。B為樹ABC根節點，A和C分別為左右孩子。
G為樹EFG根節點，EF為左子樹，F為E的右孩子。畫
出如圖所示的二叉樹
精　點　撥 A 前序遍歷序列為DBACGEF
B 節點E是節點G的左孩子
C 有ACF共3個葉子節點
D A處在第3層，F處在第4層
變式 二叉樹的中序遍歷為 BAEDFC，后序遍歷為 BEFDCA，其前序遍歷為(　　)
A.ABDEFC B.ABDCEF
C.ABCDEF D.ABCDFE
C
解析　本題考查二叉樹的遍歷。后序遍歷確定根節點，中序遍歷區分左右子樹。根據二叉樹的中序遍歷和后序遍歷可知，該二叉樹的形狀如圖所示，前序遍歷為：ABCDEF。
當堂檢測
4
重難點1　節點和邊的數量關系
重難點2　二叉樹的遍歷和數組表示
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.有樹結構的示意圖如圖所示，下列關于該樹的描述正確的是(　　)
B
解析　本題考查樹的基本概念。A選項度是指節點擁有的子樹個數，其中最大的節點的度就是樹的度。B選項共有H、I、J、C、K、L、M，7個葉子。C選項父節點是同一個的，才是兄弟節點。D選項該樹共4層，所以深度是4。
A.該樹的度為6
B.該樹的葉子節點數量是7
C.節點I、J互為兄弟節點
D.該樹的深度為5
D
解析　本題考查樹的基本概念。樹中所有節點的度之和加1為節點總數，因此1*4＋2*3＋3*2＋4*1＋1＝21。節點數為x＋4＋3＋2＋1＝x＋10，因此可以得到葉子節點數為11個。
2.有一棵樹，節點的高度和個數如表所示。則葉子節點x的個數為(　　)
度 0 1 2 3 4
節點個數 x 4 3 2 1
A.8 B.9 C.10 D.11
D
解析　本題考查二叉樹的基本性質。符合完全二叉樹的兩個條件為：①只有最下二層中的節點度數小于2；②最下一層的葉子節點都依次排列在該層最左邊位置。A選項度指樹的最大節點數。B選項若為滿二叉樹，第3層及前面所有節點數和為7，因此至少4層。C選項最后一層上有5個節點，即有葉子節點數為5，但第3層上還有一個葉子節點。
3.已知一棵完全二叉樹的節點總數為12，則有關該二叉樹的說法正確的是(　　)
A.樹的度為12
B.樹的層數為3
C.葉子節點數為5
D.最后一層有5個節點
D
解析　本題考查樹的性質。A選項樹表現一種層次性的非線性關系。D選項設二叉樹0度、1度和2度的節點個數分別為t0，t1，t2，有等式t0＋t1＋t2＝100和t0＝t2＋1成立，代入可得t2＋1＋t1＋t2＝100，且完全二叉樹1度節點個數為0或1，因此t2值為49。
4.下列關于二叉樹的說法，
A.二叉樹的數據元素之間呈非線性關系
B.二叉樹的第k層上最多有2k－1(k≥1)個節點
C.由前序遍歷和中序遍歷序列能唯一確定一棵二叉樹
D.具有100個節點的完全二叉樹有50個度為2的節點
C
解析　本題考查樹的性質和遍歷。構建完全二叉樹如圖所示。A和B選項兩個節點不在同一層中。C選項節點c和節點g分別為節點e的左右孩子，屬于兄弟節點。D選項節點d和節點f的父親節點依次為c和g，因此不屬于兄弟節點。
5.某完全二叉樹的中序遍歷序列為abcdefgh，下列兩個選項屬于兄弟節點的是(　　)
A.節點a和節點b B.節點b和節點c
C.節點c和節點g D.節點d和節點f
B
解析　本題考查二叉樹性質。根據二叉樹的性質，n0＝n2＋1，n＝n0＋n1＋n2，可以推出n2＝5。
6.已知一棵二叉樹有13個節點，樹中度為1的節點數為2，則該樹度為2的節點數為(　　)
A.4 B.5 C.6 D.11
B
解析　B選項的后序遍歷為GFDBEHCA。
1.某二叉樹前序遍歷為ABDFGCEH，后序遍歷為FGDBHECA，則下列選項
是此二叉樹的是(　　)
B
解析　本題考查二叉樹遍歷。后序遍歷是“物技化數英語”可知，根節點為語，數英分別是語節點的左右孩子。物為數的左孩子，技為最高層的左孩子，化為數的右孩子。
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為“物技化數英語”，則中序遍歷結果為(　　)
A.語數英物化技 B.物數技化語英
C.語數物化技英 D.化物技英數語
A
解析　畫出樹的形態如圖所示，可得后序遍歷為甲乙丁丙。
3.某完全二叉樹，中序遍歷結果為“甲乙丙丁”，則后序遍歷結果是(　　)
A.甲乙丁丙 B.丙乙甲丁
C.甲丁丙乙 D.乙丁丙甲
C
解析　該二叉樹可能形態，滿足前序遍歷為ABC有4種形態，如圖所示，后序遍歷均為CBA。
4.某二叉樹的前序遍歷結果為ABC，若該二叉樹不是滿二叉樹，則其后序遍歷結果為(　　)
A.ABC B.BCA C.CBA D.CAB
D
解析　畫出該樹的形態如圖所示。A選項該樹深度為4。C選項該樹有3個葉子節點。
5.用數組表示二叉樹的示意圖如表所示：
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
B D A E F C
下列說法正確的是(　　)
A.該二叉樹的深度為3 B.該二叉樹是完全二叉樹
C.該二叉樹有4個葉子節點 D.該二叉樹后序遍歷的結果為DCEFAB
D
解析　元素a[6]位于二叉樹從上至下，從左到右第7個位置，即第3層最后一個。根據中序遍歷畫出圖示如圖所示。
6.某二叉樹的樹形結構如圖所示，其中序遍歷結果為FDGBAEC。若補全為完全二叉樹后，按從上到下、自左往右的順序用一維數組a存儲，其中根節點存儲于元素a[0]中，則元素a[6]的值為(　　)
A.D B.F
C.G D.C
D
1.某二叉樹的前序遍歷結果為ABCEDF，在該二叉樹基礎上添加一個節點后的中序遍歷為BGCADEF，則添加節點后的后序遍歷結果為(　　)
A.CGBDFEA B.GCBADFE
C.CGBEFDA D.GCBDFEA
解析　根據前序遍歷確定根節點為A，左子樹為BC，左子樹根為B，右子樹為EDF，右子樹根為E，新增節點G為節點C的左孩子，最終后續遍結果為GCBDFEA。
B
解析　A為樹的根節點，在后序遍歷中，B沒有緊跟在A的前面，因此B是A的左孩子，CD是B的子樹，FE是A的右子樹。因此樹的形態可能有如圖所示的兩種情況。
2.某二叉樹的前序遍歷結果為ABCDEF，后序遍歷結果為CDBFEA，下列關于該二叉樹的說法，正確的是(　　)
A.該二叉樹的深度可能為4
B.該二叉樹的中序遍歷結果可能為CBDAEF
C.該二叉樹可能的形態有3種
D.該二叉樹度為2的節點可能有3個
D
解析　節點C為整棵樹的節節點，左子樹為AB，節點B為節點A的左子樹。節點D為右子樹的根節點，節點F為節點D的右子樹。
3.已知某二叉樹的前序遍歷是CABDEGF，中序遍歷為ABCGEDF，則其后序遍歷為(　　)
A.ABGEFDC B.BAFGEDC
C.ABFGECD D.BAGEFDC
B
解析　本題考查二叉樹的相關知識。前序遍歷找出根A，中序遍歷根據根的位置，區別左右子樹。A選項左子樹為C，但C在前序遍歷中后于B訪問，不正確。C選項同A選項。D選項該樹沒有左子樹，在右子樹中，B為根，D為B的左孩子，但在前序中D后于C訪問，不正確。B選項前序遍歷為根左右，中序遍歷為左根右，當樹缺失左孩子時，前中序遍歷是一樣的。
4.已知一棵二叉樹的前序遍歷序列為ABCDEFG，則該二叉樹中序遍歷序列可能為(　　)
A.CABDEFG B.ABCDEFG
C.DACEFBG D.ADBCFEG
C
解析　本題考查樹的性質和遍歷。根據前序遍歷確定根節點，中序遍歷區分左右子樹，畫出二叉樹。其后序遍歷結果為CDBFEA，該二叉樹最后一層葉子節點不是從左向右分布。該二叉樹深度為3，葉子節點數為3，該二叉樹補全為完全二叉樹，用一維數組實現需要7個節點的存儲空間才能表示。
5.已知某二叉樹的前序遍歷結果為ABCDEF，中序遍歷結果為CBDAEF，則下列說法正確的是(　　)
A.其后序遍歷結果為DCBFEA
B.該二叉樹為完全二叉樹
C.該二叉樹深度為3，葉子節點數為3
D.該二叉樹用一維數組實現需要6個節點的存儲空間才能表示
課后練習
5
重難點1　節點和邊的數量關系
重難點2　二叉樹的遍歷和數組表示
重難點3　根據兩種遍歷序列確定一棵二叉樹
1.某樹的結構如圖，下列說法正確的是(　　)
B
解析　本題考查樹的性質。A選項數的度取決于節點的最大度數，因此該樹的度為3。
A.該樹的度為4
B.該樹的高度為4
C.該樹的葉子節點為3個
D.節點F和G是兄弟節點
2.已知完全二叉樹T共有78個節點，則其葉子節點數量為(　　)
A.15 B.32 C.39 D.40
C
解析　設二叉樹0度、1度和2度的節點個數分別為t0，t1，t2，有等式t0＋t1＋t2＝78和t0＝t2＋1成立，代入可得t0＋t1＋t0－1＝78，且完全二叉樹1度節點個數為0或1，因此t1值為1。
3.一棵有n(n>0)個節點的二叉樹，其節點為0度或2度，則此樹的最大高度是(　　)
A.(n＋1)∥2 B.n∥2
C.(n－1)∥2 D.int(log2n＋1)
A
解析　本題考查二叉樹基本性質。該二叉樹的節點的度都為0或2，即除根節點外，其每個節點都有一個兄弟節點。題目要求樹的最大高度，每層就只有2個節點(除了根節點)，若總節點數加上1，相當于令第1層也變成兩個節點，那么總層數就是(n＋1)∥2。
4.現有一棵二叉樹，度為2的節點有10個，度為1的節點有5個，則這棵二叉樹共有節點數為(　　)
A.25 B.26
C.27 D.不確定
B
解析　本題考查二叉樹性質。根據二叉樹性質可知n0＝n2＋1，總的節點數量為10＋11＋5＝26。
D
解析　A選項F不是B的子節點。B選項樹最高有4層，最大高度為2。C選項中序遍歷為DBEGACF。D選項完全二叉樹中，前3層為滿二叉樹，共有7個節點，少一個節點。第4層從左至右依次排列，還要補3個節點，因此共需補4個節點。
5.某二叉樹如圖所示，下列說法正確的是(　　)
A.節點D 、F都是節點B的孩子節點
B.該樹的高度和深度分別為2和3
C.該二叉樹中序遍歷的結果為DBEAGCF
D.若補全成高度為4的完全二叉樹則需增加4個節點
6.如圖所示，將二叉樹A的根節點與二叉樹B的根節點連接，使得二叉樹A成為二叉樹B的左子樹，合并為一棵新的二叉樹C。下列說法中正確的是(　　)
C
解析　本題考查二叉樹的性質和遍歷。新二叉樹高度為4；葉子節點數量為4，是一棵完全二叉樹；中序遍歷的結果為84251637，不是一個有序序列。
A.二叉樹C的高度為3
B.二叉樹C的葉子節點數量為3
C.二叉樹C是一棵完全二叉樹
D.二叉樹C中序遍歷的結果是一個有序序列
7.下列Python表達式用于表示“一棵n個節點的二叉樹的葉子節點最大可能數量”，正確的是(　　)
A.n－1 B.n∥2 C.n∥2＋1 D.n/2
C
解析　本題考查二叉樹的性質。由n0＝n2＋1和n0＋n1＋n2＝n可得到n0＋n1＋n0－1＝n，二叉樹度為1的節點個數n1為0時，葉子節點個數n0達到最多，得到n0＝(n＋1)/2。總節點個數是奇數個，(n＋1)/2等價于n∥2＋1。
C
解析　本題考查二叉樹的性質。根據完全二叉樹的性質可知，該二叉樹共計13個節點。那么深度為4，前3層有7個節點，第4層有6個葉子節點，最大十進制數是0101B。
8.如圖所示的二叉樹，根節點為0，每個節點的左子節點為0，右子節點為1，每一條從根到葉子的路徑都組成一個二進制數。例如：從根到葉子a的路徑組成二進制數011，轉換為十進制數是3。若某完全二叉樹共有13個節點，則它能表示的最大十進制數是(　　)
A.3 B.4 C.5 D.6
9.有一棵二叉樹如圖所示，下列說法正確的是(　　)
B
解析　 本題考查樹的性質。A選項完全二叉樹第n－1層為滿二叉樹，不符合。C選項葉子節點有2個。D選項可以用數組或鏈表實現。
A.該二叉樹是一棵完全二叉樹，樹的高度為3
B.該二叉樹的前序遍歷為A，B，D，C，E
C.該二叉樹的葉子節點有4個
D.該二叉樹的建立只能使用數組來實現
10.某二叉樹的結構如圖所示，下列說法
A
解析　本題考查二叉樹的性質。該樹不是完全二叉樹。葉子節點有DEF，節點中最大的度為2。
A.該二叉樹是一棵完全二叉樹
B.該二叉樹的葉子節點數是3個
C.該二叉樹的中序遍歷結果是DCBEAF
D.該二叉樹的度為2
1.某二叉樹中序遍歷為ABCDEF，則下列 是此二叉樹的是(　　)
C
解析　C選項中序遍歷為ACBDEF。
B
解析　先根據樹的形態畫出前序遍歷的路徑，再將遍歷到的各個節點填上去，得到后序遍歷為BDEFCA。
2.某二叉樹的樹形結構如圖所示，其后序遍歷結果為BDEFCA，則前序遍歷結果為(　　)
A.ACFEDB B.ADBCFE
C.ADBFEC D.ADBEFC
B
解析　該完全二叉樹有9個節點，因此共有4層，其中前3層是滿二叉樹(7個節點)，第4層有2個節點，畫出二叉樹的形態和中序遍歷路徑，可得前序遍歷序列。
3.有一棵完全二叉樹，已知其中序遍歷結果是CADGBEIHJ，則其前序遍歷結果應該為(　　)
A.ABCDEFGHI B.EGACDBHIJ
C.EACGBDIHJ D.EACDBHIJ
A
解析　本題考查樹的遍歷和性質。從后序遍歷來看，g是根節點，左右子樹分別有個，左子樹先于右子樹，因此abc是左子樹，def是右子樹，c是g的左孩子，f是g的右孩子。
4.有二叉樹形態如圖所示，后序遍歷結果為abcdefg，則樹中與c同層的節點是(　　)
A.f B.e
C.d D.b
D
解析　畫出樹的結構如圖所示：該樹深度為3，葉子節點有2個，不是完全二叉樹。
5.使用數組存儲某二叉樹的形式如圖所示，下列描述正確的是(　　)
0 1 2 3 4 5 6
A B C D
A.該二叉樹的深度為2 B.該二叉樹葉子節點個數為3
C.該二叉樹是一棵完全二叉樹 D.該二叉樹后序遍歷為BDCA
C
解析　畫出樹的結構如圖所示：可以得到后序遍歷序列。
6.如圖所示用一維數組表示的二叉樹，其后序遍歷是(　　)
索引 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
節點值 A B C D E F
A.FEDCBA B.ABDFCE
C.FDBECA D.BFDAEC
D
解析　先畫出該樹的后序遍歷路徑，再把各個節點填上去，最后寫出前序遍歷序列。
7.某二叉樹的樹形結構如圖所示，其后序遍歷結果為DBGEFCA，前序遍歷的結果為(　　)
A.ABCDEFG B.ABDCEGF
C.DBEGCFA D.ABDCGFE
C
解析　本題考查樹的遍歷。前序遍歷為根左右，A選項任一節點沒有左節點，則前中序均為根右。B選項河是第1個左節點，則好是大的左節點，是河的根，山為河的兄弟。D選項任一節點沒有右節點。C選項好是大的左節點，山是右節點，或山是大的左節點，是好的父節點，則前序遍歷不對了。
8.某二叉樹前序遍歷的結果為“大好河山”，則中序遍歷的結果
A.大好河山 B.河山好大
C.好山大河 D.山河好大
C
解析　本題考查二叉樹相關概念。前序遍歷為根左右，中序遍歷為左根右。A選項當左子樹缺失時，遍歷序列相同。D選項當右子樹缺失時，遍歷序列正好相反。節點D可能是整棵樹的右子樹，也可能是左子樹中的一個右孩子，但節點C一定先于節點D訪問，因此C選項不可能。B選項當D是C的右孩子，C缺失左孩子，整棵樹沒有右子樹。
9.某二叉樹前序遍歷的結果為“ABCD”，則中序遍歷的結果
A.ABCD B.CDBA
C.BDAC D.DCBA
B
解析　本題考查二叉樹的遍歷。根據題意畫出二叉樹如圖所示
10.某二叉樹的數組表示示意圖如圖所示，該二叉樹的后序遍歷序列為(　　)
0 1 2 3 4 5 6 7 8 9 10 11 12 13
A B C D E F G
A.BAFDCGE B.BFDGECA
C.BFGDECA D.DEBFGCA
后序遍歷是：BFDGECA。
D
解析　本題考查二叉樹的遍歷。A選項完全二叉樹是指一棵深度為k的有n節點的二叉樹，對樹中的節點按從上至下、從左到右的順序進行編號，編號為i(1≤i≤n)的結點與滿二叉樹中編號為i的節點在二叉樹中的位置相同。3所在節點缺少葉子節點，故該二叉樹不是完全二叉樹。B選項3、5、2所在節點為葉子節點，數量為3。C選項前序遍歷結果為/3*52。D選項將圖中二叉樹補全為完全二叉樹，依次把完全二叉樹中原二叉樹的節點用一維數組的各元素表示。
11.數學表達式3/(5*2)可用二叉樹表示，如圖所示。下列關于該二叉樹的說法，正確的是(　　)
A.是完全二叉樹
B.葉子節點數為2
C.前序遍歷結果為352*/
D.用數組表示為
B
12.用一維數組來表示某二叉樹如表所示，則下列說法
0 1 2 3 4 5 6 7 8 9 10 11 12
A B C D E F G H
A.該二叉樹的深度為4
B.節點B有兩個孩子節點，分別為E和F
C.該二叉樹的中序遍歷結果為DBGEAFHC
D.葉子節點的數量比度為2的節點數量多1
解析　構建的二叉樹如圖。
D
A.該表達式樹是一棵二叉樹，樹的度是2，高度是5
B.該樹的葉子節點數比度為2的節點數多1個
C.若采用完全二叉樹數組從0號位開始存儲，則節點b存儲在6號位
D.該表達式樹的前序遍歷序列是×d＋/fc－ab
解析　本題考查樹與二叉樹相關知識。樹的度是最大的節點的度，樹的高度是節點最大的層數，A選項在任意一棵二叉樹中都有n0＝n2＋1的性質，即葉子節點數等于度為2的節點數多一個；非完全二叉樹若用完全二叉樹保存時需將樹補成完全二叉樹，即第3層需補全d節點的兩個孩子節點，此時節點b存儲在第6號位置上。D選項該表達式樹的前序遍歷序列是×d＋/f－cab，對節點“－”而言先于其子節點c。
A
解析　本題考查二叉樹的性質和遍歷。根據二叉樹的前序遍歷和中序遍歷畫出二叉樹。該二叉樹的根節點A的度為1，高度為5，節點G是節點F的右孩子。該二叉樹的葉子節點是E、G、D。
1.有二叉樹的前序遍歷序列為A－B－C－E－F－G－D，中序遍歷序列為A－E－C－F－G－B－D，則關于該二叉樹的說法正確的是(　　)
A.該二叉樹根節點的度為1 B.該二叉樹的高度為4
C.該二叉樹中節點G是節點C的左孩子 D.該二叉樹中葉子節點的個數為4
B
解析　本題考查樹的操作。由題意可知A為根節點，左子樹的中序遍歷為DHBE，觀察其后序遍歷，B為左子樹的根節點，E為左子樹的右子樹，因此節點E是葉子節點。
2.某二叉樹的中序遍歷順序為DHBEAFCG，后序遍歷為HDEBFGCA，則節點E是(　　)
A.A節點的孩子節點 B.葉子節點
C.H節點的父親節點 D.F節點的兄弟節點
A
解析　本題考查樹的性質。從后序遍歷來看，a是根節點，b是左子樹，dce是右子樹；c是右子樹的根節點，d和e分別是左右子樹。因此前序遍歷為abcde。
3.二叉樹的中序遍歷序列：badce，后序遍歷序列：bdeca，則二叉樹前序遍歷序列為(　　)
A.abcde B.abdec C.debac D.adbce
D
解析　根據二叉樹的前序遍歷和中序遍歷確定唯一的二叉樹，再得出后序遍歷。
4.已知一棵二叉樹的前序遍歷序列為abdgecfh，中序遍歷序列為dgbeachf，則該二叉樹的后序遍歷序列為(　　)
A.hfcegdba B.gdbehfca
C.gdbehfca D.gdebhfca
C
解析　本題考查樹的遍歷。由后序遍歷可知C為根節點，根據中序遍歷樹可分為(BA)C(DFE)，A為B的左子樹，FE為D的右子樹，F為E的左子樹。
5.現有一棵二叉樹的中序遍歷序列為B－A－C－D－F－E，后序遍歷序列為A－B－F－E－D－C，則該二叉樹的前序遍歷序列是(　　)
A.C－B－A－D－F－E B.C－B－A－F－E－D
C.C－B－A－D－E－F D.C－B－A－E－F－D
B
解析　本題考查二叉樹的性質、存儲和遍歷。根據前序遍歷，可知A為根節點，中序序列可以劃分為(BDE)A(FCG)，則左子樹BDE中，B為根節點，DE為右子樹，DE子樹中，E為D的右節點。右子樹FCG中，C為根節點，F和G分別為左右子樹。根據上述描述，畫出樹，可知葉子節點有EFG 3個，后序遍歷為EDBFGCA，樹的高度為4，但不是完全二叉樹。
6.某二叉樹的前序遍歷為A－B－D－E－C－F－G，中序遍歷為B－D－E－A－F－C－G，則下列說法正確的是(　　)
A.該二叉樹的葉子節點有4個
B.該二叉樹的后序遍歷為E－D－B－F－G－C－A
C.該二叉樹的高度為4，是一棵完全二叉樹
D.用數組來表示該樹，若A的下標為0，則E的下標為5
B
解析　本題考查二叉樹遍歷相關知識點。只知道前序遍歷和后序遍歷不能得到唯一的二叉樹，故排除AC。假設B有可能，左子樹為BD，右子樹為EC。假設D有可能，得出左子樹為DCB，右子樹為E，后序遍歷不可能是D－B－E－C－A。
7.已知一棵二叉樹的前序遍歷序列為：A－B－D－C－E，后序遍歷序列為：D－B－E－C－A。則有關該二叉樹的中序遍歷序列說法正確的是(　　)
A.能唯一確定，中序遍歷序列為： B－D－A－E－C
B.不能唯一確定，中序遍歷序列可能為： B－D－A－E－C
C.能唯一確定，中序遍歷序列為： D－C－B－A－E
D.不能唯一確定，中序遍歷序列可能為： D－C－B－A－E

展開更多......

收起↑