资源简介

学习目标　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

展开更多......

收起↑