资源简介

二、 二叉树的基本操作
1. 某二叉树的中序遍历序列为ABCDEFG,后序遍历序列为ACBFEGD。下列说法中,正确的是(　B　)
A. 前序遍历序列为DBACGFE B. 节点G为节点E的父节点
C. 该二叉树有两个叶子节点 D. 节点A与节点F为同一层
【解析】 本题考查二叉树的应用。根据中序遍历及后序遍历可得树的结构如图所示。分析可得,B正确。
2. 某二叉树的树形结构如图所示,其中序遍历的结果为EDBCFA,则后序遍历的结果为(　C　)
A. EDFACB B. BEDCAF
C. DEFACB D. CAFBED
【解析】 本题考查二叉树的遍历。中序遍历规则为“左—根—右”,已知中序遍历结果为EDBCFA,可知完整二叉树如图所示。可得出后序遍历结果为DEFACB,C正确。
3. 如图所示的二叉树的中序遍历的结果是(　B　)
A. ABDEGCFH B. DBEGACHF
C. DGEBHFCA D. ABCDEFGH
【解析】 中序遍历先访问左子树,再访问根节点,最后访问右子树。故该二叉树的中序遍历结果是DBEGACHF,B正确。
4. 如图所示的二叉树的后序遍历的结果是(　C　)
A. ABDEGCFH B. DBEGACHF
C. DGEBHFCA D. ABCDEFGH
【解析】 后序遍历是先访问左子树,再访问右子树,最后访问根节点。因此该二叉树的后序遍历结果是DGEBHFCA,C正确。
5. 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点编号),中序遍历是DBFEAGC,则该二叉树的后序遍历是(　A　)
A. DFEBGCA B. DFEBACG
C. FBCGEDA D. DFECAGB
【解析】 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点的编号),判断出节点A是树根,B、D错误;又根据中序遍历是DBFEAGC,可判断出GC是树根的右子树,A正确,C错误。
6. 某二叉树的前序遍历序列和中序遍历序列相同,下列选项中,符合该二叉树结构的是(　C　)
A. B.
C. D.
【解析】 本题考查二叉树的遍历。前序遍历为根—左—右,中序遍历为左—根—右,若没有左子树,则两种遍历结果相同,C正确。
7. 如表所示为用数组表示二叉树。则该二叉树的中序遍历序列为(　A　)
0 1 2 3 4 5 6 7
A B C 　 D 　 　 　
8 9 10 11 12 13 14
　 E F 　 　 　 　
A. BEDFAC B. ABDEFC
C. DBEAFC D. BDAECF
【解析】 本题考查二叉树的创建与遍历。根据题意,创建如图所示的二叉树,然后进行中序遍历,分析可得A正确。
8. 某二叉树的树形结构如图所示,前序遍历为ABCDEF,则该二叉树的后序遍历的结果是(　A　)
A. CBFEDA B. BCADEF
C. ABDCEF D. FEDCBA
【解析】 本题考查二叉树的遍历。根据前序遍历根—左—右的规则和题图的二叉树结构,不难得出该二叉树如图所示。由此可知,后序遍历结果是CBFEDA,A正确。
9. 已知一棵二叉树的前序遍历序列为ABCDEFG,则该二叉树的中序遍历序列可能为(　B　)
A. CABDEFG B. ABCDEFG
C. DACEFBG D. ADBCFEG
【解析】 本题考查二叉树的相关知识。已知前序遍历和中序遍历,可以确定对应的二叉树。若某个中序遍历序列有错,则无法还原二叉树。利用这个特点,我们可以逐个选项尝试画出二叉树。当二叉树所有分支节点都没有左子树时,该二叉树的中序遍历序列是ABCDEFG,B正确。
10. 某二叉树的后序遍历序列为ABCDE,其中节点A和节点B分别是节点C的左右孩子,则该树的前序遍历可能是(　D　)
A. CABED B. DCABE
C. EACBD D. EDCAB
【解析】 本题考查二叉树的遍历。根据后序遍历序列为ABCDE可知,节点E是根节点,前序遍历根节点在最前面,A、B错误。另外,由于节点A和节点B分别是节点C的左右孩子,因此前序遍历(根—左—右)A和B节点不可能分居在节点C的两边,C错误。
11. 某二叉树的前序遍历序列和后序遍历序列正好相反,则该二叉树一定是(　B　)
A. 空或只有一个节点 B. 高度等于其节点数
C. 任一节点无左孩子 D. 任一节点无右孩子
【解析】 前序遍历顺序是“M－L－R”,后序遍历的顺序是“L－R－M”,其中L－R的相对位置不发生变化,变化的是M的位置。题目指出二叉树的先序和后序结果正好相反,分析以下几种情况:①当二叉树只有一个节点时,只有M、L和R为空,满足条件;②当二叉树为空时,M、L和R均为空,满足条件;③当二叉树任一节点无左孩子时,L为空,前序遍历为M－R,后序遍历为R－M,结果正好相反,满足条件;④当二叉树任一节点无右孩子时,R为空,前序遍历的结果为M－L,后序遍历的结果为L－M,满足条件;综上,上述分析的四种条件都满足二叉树的高度等于其节点数。B正确。
12. 已知某二叉树的前序遍历是cdaefh,中序遍历是adechf。下列说法中,正确的是(　A　)
A. 该二叉树是完全二叉树
B. 该二叉树的数组实现示意图如下
0 1 2 3 4 5
a c d e f h
C. 该二叉树的高度为4
D. 该二叉树的后序遍历是aedfhc
【解析】 由前序遍历和中序遍历可以绘制出如图所示的对应的二叉树及数组实现示意图,B错误。
0 1 2 3 4 5
c d f a e h
综上可知,其高度为3,C错误。后序遍历为aedhfc,D错误。
13. 某二叉树的中序遍历为BACEDF,前序遍历为ABCDEF。下列关于该二叉树的说法,正确的是(　D　)
A. 该二叉树是完全二叉树 B. 该二叉树的高度为3
C. 该二叉树有4个叶子节点 D. 该二叉树的总边数为5
【解析】 根据题干描述,该二叉树如图所示。
由图可知,该二叉树不是完全二叉树,A错误。该二叉树的高度为4,B错误。该二叉树有3个叶子节点,C错误。该二叉树的总边数为5,D正确。
14. 某完全二叉树的总节点数为 10,用数字[1~10]逐层依次标示各个节点。下列关于该二叉树的说法,错误的是(　B　)
A. 叶子节点数比度为 2 的节点数多1
B. 中序遍历的顺序为8－9－4－10－5－2－1－6－3－7
C. 若某节点无左孩子节点,则此节点亦无右孩子节点
D. 用一维数组存储该树,所有节点对应的数组元素一定是连续的
【解析】 本题考查二叉树的遍历。具体二叉树的形态如图所示。因此其中序遍历数序为8－4－9－2－10－5－1－6－3－7,B符合题意。
15. 某二叉树的中序遍历的结果是DGBAECF,后序遍历的结果是GDBEFCA。下列关于该二叉树的说法,错误的是(　B　)
A. 该二叉树前序遍历结果是ABDGCEF
B. 该二叉树是满二叉树
C. 该二叉树有3个叶子节点
D. 节点D是节点G的父节点
【解析】 本题考查二叉树的遍历。根据中序遍历结果是 DGBAECF,后序遍历结果是GDBEFCA,可得具体二叉树的形态如图所示。
因此该二叉树不是满二叉树,B符合题意。(共21张PPT)
二、 二叉树的基本操作
第四章　树
信息技术 选择性必修1 数据与数据结构
必备知识练
1. 某二叉树的中序遍历序列为ABCDEFG,后序遍历序列为ACBFEGD。下列说法中,正确的是(　　)
A. 前序遍历序列为DBACGFE B. 节点G为节点E的父节点
C. 该二叉树有两个叶子节点 D. 节点A与节点F为同一层
【解析】 本题考查二叉树的应用。根据中序遍历及后序遍历可得树的结构如图所示。分析可得,B正确。
B
2. 某二叉树的树形结构如图所示,其中序遍历的结果为EDBCFA,则后序遍历的结果为
(　　)
A. EDFACB B. BEDCAF
C. DEFACB D. CAFBED
C
【解析】 本题考查二叉树的遍历。中序遍历规则为“左—根—右”,已知中序遍历结果为EDBCFA,可知完整二叉树如图所示。可得出后序遍历结果为DEFACB,C正确。
3. 如图所示的二叉树的中序遍历的结果是(　　)
A. ABDEGCFH B. DBEGACHF
C. DGEBHFCA D. ABCDEFGH
【解析】 中序遍历先访问左子树,再访问根节点,最后访问右子树。故该二叉树的中序遍历结果是DBEGACHF,B正确。
B
4. 如图所示的二叉树的后序遍历的结果是(　　)
A. ABDEGCFH B. DBEGACHF
C. DGEBHFCA D. ABCDEFGH
【解析】 后序遍历是先访问左子树,再访问右子树,最后访问根节点。因此该二叉树的后序遍历结果是DGEBHFCA,C正确。
C
5. 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点编号),中序遍历是
DBFEAGC,则该二叉树的后序遍历是(　　)
A. DFEBGCA B. DFEBACG
C. FBCGEDA D. DFECAGB
【解析】 已知7个节点的二叉树的前序遍历是ABDEFCG(字母为节点的编号),判断出节点A是树根,B、D错误;又根据中序遍历是DBFEAGC,可判断出GC是树根的右子树,A正确,C错误。
A
6. 某二叉树的前序遍历序列和中序遍历序列相同,下列选项中,符合该二叉树结构的是
(　　)
C
A. B. C. D.
【解析】 本题考查二叉树的遍历。前序遍历为根—左—右,中序遍历为左—根—右,若没有左子树,则两种遍历结果相同,C正确。
7. 如表所示为用数组表示二叉树。则该二叉树的中序遍历序列为(　　)
0 1 2 3 4 5 6 7
A B C 　 D 　 　 　
8 9 10 11 12 13 14
　 E F 　 　 　 　
A. BEDFAC B. ABDEFC
C. DBEAFC D. BDAECF
【解析】 本题考查二叉树的创建与遍历。根据题意,创建如图所示的二叉树,然后进行中序遍历,分析可得A正确。
A
8. 某二叉树的树形结构如图所示,前序遍历为ABCDEF,则该二叉树的后序遍历的结果是
(　　)
A. CBFEDA B. BCADEF
C. ABDCEF D. FEDCBA
A
【解析】 本题考查二叉树的遍历。根据前序遍历根—左—右的规则和题图的二叉树结构,不难得出该二叉树如图所示。由此可知,后序遍历结果是CBFEDA,A正确。
9. 已知一棵二叉树的前序遍历序列为ABCDEFG,则该二叉树的中序遍历序列可能为
(　　)
A. CABDEFG B. ABCDEFG
C. DACEFBG D. ADBCFEG
【解析】 本题考查二叉树的相关知识。已知前序遍历和中序遍历,可以确定对应的二叉树。若某个中序遍历序列有错,则无法还原二叉树。利用这个特点,我们可以逐个选项尝试画出二叉树。当二叉树所有分支节点都没有左子树时,该二叉树的中序遍历序列是ABCDEFG,B正确。
B
关键能力练
10. 某二叉树的后序遍历序列为ABCDE,其中节点A和节点B分别是节点C的左右孩子,则该树的前序遍历可能是(　　)
A. CABED B. DCABE
C. EACBD D. EDCAB
【解析】 本题考查二叉树的遍历。根据后序遍历序列为ABCDE可知,节点E是根节点,前序遍历根节点在最前面,A、B错误。另外,由于节点A和节点B分别是节点C的左右孩子,因此前序遍历(根—左—右)A和B节点不可能分居在节点C的两边,C错误。
D
11. 某二叉树的前序遍历序列和后序遍历序列正好相反,则该二叉树一定是(　　)
A. 空或只有一个节点 B. 高度等于其节点数
C. 任一节点无左孩子 D. 任一节点无右孩子
【解析】 前序遍历顺序是“M－L－R”,后序遍历的顺序是“L－R－M”,其中L－R的相对位置不发生变化,变化的是M的位置。题目指出二叉树的先序和后序结果正好相反,分析以下几种情况:①当二叉树只有一个节点时,只有M、L和R为空,满足条件;②当二叉树为空时,M、L和R均为空,满足条件;③当二叉树任一节点无左孩子时,L为空,前序遍历为M－R,后序遍历为R－M,结果正好相反,满足条件;④当二叉树任一节点无右孩子时,R为空,前序遍历的结果为M－L,后序遍历的结果为L－M,满足条件;综上,上述分析的四种条件都满足二叉树的高度等于其节点数。B正确。
B
12. 已知某二叉树的前序遍历是cdaefh,中序遍历是adechf。下列说法中,正确的是(　　)
A. 该二叉树是完全二叉树
B. 该二叉树的数组实现示意图如下
0 1 2 3 4 5
a c d e f h
C. 该二叉树的高度为4
D. 该二叉树的后序遍历是aedfhc
A
【解析】 由前序遍历和中序遍历可以绘制出如图所示的对应的二叉树及数组实现示意图,B错误。
0 1 2 3 4 5
c d f a e h
综上可知,其高度为3,C错误。后序遍历为aedhfc,D错误。
13. 某二叉树的中序遍历为BACEDF,前序遍历为ABCDEF。下列关于该二叉树的说法,
正确的是(　　)
该二叉树是完全二叉树
B. 该二叉树的高度为3
C. 该二叉树有4个叶子节点
D. 该二叉树的总边数为5
【解析】 根据题干描述,该二叉树如图所示。
由图可知,该二叉树不是完全二叉树,A错误。该二叉树的高度为4,
B错误。该二叉树有3个叶子节点,C错误。该二叉树的总边数为5,
D正确。
D
14. 某完全二叉树的总节点数为 10,用数字[1~10]逐层依次标示各个节点。下列关于该二叉树的说法,错. 误. 的是(　　)
A. 叶子节点数比度为 2 的节点数多1
B. 中序遍历的顺序为8－9－4－10－5－2－1－6－3－7
C. 若某节点无左孩子节点,则此节点亦无右孩子节点
D. 用一维数组存储该树,所有节点对应的数组元素一定是连续的
【解析】 本题考查二叉树的遍历。具体二叉树的形态如图所示。
因此其中序遍历数序为8－4－9－2－10－5－1－6－3－7,
B符合题意。
B
15. 某二叉树的中序遍历的结果是DGBAECF,后序遍历的结果是GDBEFCA。下列关于该二叉树的说法,错. 误. 的是(　　)
A. 该二叉树前序遍历结果是ABDGCEF
B. 该二叉树是满二叉树
C. 该二叉树有3个叶子节点
D. 节点D是节点G的父节点
【解析】 本题考查二叉树的遍历。根据中序遍历结果是
DGBAECF,后序遍历结果是GDBEFCA,可得具体二叉树
的形态如图所示。
因此该二叉树不是满二叉树,B符合题意。
B

展开更多......

收起↑