问题：
① 二叉树的先序序列和中序序列相同的条件是 任何结点至多只有右子树，没有左子树或
是空树 。
② 二叉树的中序序列和后序序列相同的条件是 任何结点至多只有左子树，没有右子
树或是空树 。
③ 二叉树的先序序列和后序序列相同的条件是 只有根结点 。
4.3 树和二叉树课堂练习
【noip2019普及组】8.一棵二叉树如右图所示,若采用顺序存储结构，即用一维数组元素存
储该二叉树中的结点（根结点的下标为 1,若某结点的下标为ⅰ,则其左孩子位于下标 2i 处、
右孩子位于下标 2i+1 处）,则该数组的最大下标至少为（ ）。
A.6 B.10 C.15 D.12
答案：C
解析：根据题目给定的规则可知,下标最大的结点为树中深度最大且最靠右的结点,其下标为
((1*2+1)*2+1)*2+1=15。
【noip2019 普及组】14.假设一棵二叉树的后序遍历序列为 DGJHEBIFCA，中序遍历序列为
DBGEHJACIF，则其前序遍历序列为（ ）
A. ABCDEFGHIJ B. ABDEGHJCFI C. ABDEGJHCFI D. ABDEGHJFIC
答案：B
解析：后序遍历的规则是“左右根”、中序遍历的规则是“左根右”,因此可知 A 是树根、
DBGEHJ 是 A 左子树的中序遍历（对应后续遍历 DGJHEB）、CIF 是 A 右子树的中序遍历（对应
后续遍历 IFC），递归画出对应的二叉树,再根据前序遍历规则“根左右”即可求出答案。
【noip2018 普及组】7.根节点深度为 0，一棵深度为 h 的满 k（k>1）叉树，即除最后一
层无任何子节点外，每一层上的所有结点都有 k 个子结点的树，共有（ ）个结点。
A.(k h+1 - 1) / (k - 1)
B.k
h-1
C.k
h
D.(k | h-1) / (k - 1) |
答案：A
解析：假设 h=2，k=2，画出完美二叉树，共 7 个节点，带入运算，得到选 A。
推导过程：
深度为 h 的树(根节点深度为 0),其总节点数为：
s=k0+k1+k2+…+kh （公式 1）
两边都乘以 k,得到：
sk=k h+kh+1 （公式 2）
1+k2…+k
公式 2 减公式 1,得到
(k-1)s=kh+1-k0=kh+1 - 1
于是 s=(kh+1-1)/(k-1)
【noip2018 提高组】4. 下列说法中，是树的性质的有（ ）。【不定项选择】
A. 无环
B. 任意两个结点之间有且只有一条简单路径
C. 有且只有一个简单环
D. 边的数目恰是顶点数目减 1
答案：ABD
【noip2015 普及组】16. 前序遍历序列与中序遍历序列相同的二叉树为（ ）
A.根结点无左子树的二叉树
B.根结点无右子树的二叉树
C.只有根结点的二叉树或非叶子结点只有左子树的二叉树
D.只有根结点的二叉树或非叶子结点只有右子树的二叉树
答案：D
【noip2015 普及组】17.如果根的高度为 1，具有 61 个结点的完全二叉树的高度为（ ）
A. 5 B. 6 C. 7 D. 8
答案：B
4.4 树和二叉树习题 1
一、单项选择题
1．下列说法中正确的是 ( )
A．任何一棵二叉树中至少有一个结点的度为 2
B．任何一棵二叉树中每个结点的度都为 2
C．任何一棵二叉树中的度肯定等于 2
D．任何一棵二叉树中的度可以小于 2
2．树最适合用来表示 ( )
A．有序数据元素 B．无序数据元素
C．元素之间具有分支层次关系的数据 D．元素之间无联系的数据
3．若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（ ）
A．9 B．11 C．15 D．不确定
4．一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是（ ）
A． 250 B． 500 C．254 D．505 E．以上答案都不对
5．二叉树的第 I 层上最多含有结点数为（ ）
A．2
I B． 2I-1-1 C． 2I-1 D．2I -1
6．一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉树最少有( )结点
A．2h B．2h-1 C．2h+1 D．h+1
7．已知一棵二叉树的前序遍历结果为 ABCDEF,中序遍历结果为 CBAEDF,则后序遍历的结果
为（ ）。
A．CBEFDA B． FEDCBA C． CBEDFA D．不定
8．已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac , 它的前序遍历是
（ ）。
A．acbed B．decab C．deabc D．cedba
9．在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序（ ）
A．都不相同 B．完全相同
C．先序和中序相同，而与后序不同 D．中序和后序相同，而与先序不同
10．在完全二叉树中，若一个结点是叶结点，则它没（ ）。
A．左子结点和兄弟结点 B．右子结点和兄弟结点
C．左子结点和右子结点 D．左子结点，右子结点和兄弟结点
11．n 个结点的线索二叉树上含有的线索数为（ ）
A．2n B．n－l C．n＋l D．n
12．由 3 个结点可以构造出多少种不同的二叉树？（ ）
A．2 B．3 C．4 D．5
13. 一棵有 n 个结点的二叉树，按层次从上到下，同一层从左到右顺序存储在一维数组
A[1..n]中，则二叉树中第 i 个结点（i 从 1 开始用上述方法编号）的右孩子在数组 A 中的
位置是（ ）
A．A[2i](2i<=n) B．A[2i+1](2i+1<=n)
C．A[i-2] D．条件不充分，无法确定
二、填空题
1．深度为 k 的完全二叉树至少有___ ____个结点，至多有___ ____个结点。
2．高度为 8 的完全二叉树至少有______个叶子结点。
3.具有 n 个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点
的左右孩子，其余的________个指针域为NULL。
4．树的主要遍历方法有________、________、________等三种。
5．一个深度为 k 的，具有最少结点数的完全二叉树按层次，（同层次从左到右）用自然数依
此对结点编号，则编号最小的叶子的序号是__ _；编号是 i 的结点所在的层次号
是_ __（根所在的层次号规定为 1 层）。
6．如果结点 A 有 3 个兄弟，而且 B 是 A 的双亲，则 B 的度是______。
7．二叉树的先序序列和中序序列相同的条件是__ ___。
二叉树的中序序列和后序序列相同的条件是__ ___。
二叉树的先序序列和后序序列相同的条件是___ ___。
8．若一个二叉树的叶子结点是某子树的中序遍历序列中的最后一个结点，则它必是该子树
的____ __序列中的最后一个结点。
参考答案：
一、选择题
1.D 2.C 3.B 4.E 5.C
6.B 7.A 8.D 9.B 10.C
11.C 12.D 13.D
二、填空题
1. 2k-1 2k-1
2. 26-1+1=64
3. 2n n-1 n+1
4. 先序遍历 后序遍历 中序遍历
5. 2k-2 - 1 + 1 + 1 = 2k-2 + 1
trunk(log2i)+1
6. 4
7. 任何结点至多只有右子树，没有左子树或是空树
任何结点至多只有左子树，没有右子树或是空树
只有根结点
8. 前序遍历
4.5 树和二叉树习题 2
一.选择题
1. 假定在一棵二叉树中，双分支结点数为 15，单分支结点数为 30 个，则叶子结点数为
（ ）个。
A．15 B．16 C．17 D．47
2. 深度为 5 的二叉树至多有（ ）个结点。
A. 16 B. 32 C. 31 D. 10
3. 设高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此类二叉树中所包含的结点数
至少为（ ）。
A. 2h B. 2h-1 C. 2h+1 D. h+1
4. 对一个满二叉树，m 个树叶，n 个结点，深度为 h，则（ ）。
A. n=h+m B. h+m=2n C. m=h-1 D. n=2
h-1
5. 任何一棵二叉树的叶结点在先序.中序和后序遍历序列中的相对次序（ ）。
A.不发生改变 B.发生改变 C.不能确定 D.以上都不对
6. 如果某二叉树的前根次序遍历结果为 stuwv，中序遍历为 uwtvs，那么该二叉树的后序
为（ ）。
A. uwvts B. vwuts C. wuvts D. wutsv
7. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是 dgbaechf，
则其后序遍历的结点访问顺序是（ ）。
A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca
8. 在一非空二叉树的中序遍历序列中，根结点的右边（ ）。
A. 只有右子树上的所有结点 B. 只有右子树上的部分结点
C. 只有左子树上的部分结点 D. 只有左子树上的所有结点
13. 某二叉树结点的中序序列为 A.B.C.D.E.F.G，后序序列为 B.D.C.A.F.G.E，则其左子树
中结点数目为（ ）。
A. 3 B. 2 C. 4 D. 5
14. 具有 n(n>0)个结点的完全二叉树的深度为（ ）。
A. log2(n) B. log2(n) -1
C. trunc(log2(n)) +1 D. 2n-1+1
15. 将一棵有 100 个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行
编号，根结点编号为 1，则编号为 49 的结点的左孩子的编号为（ ）。
A.98 B.99 C.50 D.48
16. 将一棵有 100 个结点的完全二叉树从根开始，每一层从左到右依次对结点进行编号，根
结点编号为 1，则编号最大的非叶结点的编号为（ ）。
A.48 B.49 C.50 D.51
17. 一棵树深度为 K 的完全二叉树至少有（ ）个结点
A．2k –1 B. 2k-1-1 C. 2k-1 D. 2
k
18. 一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。
A．CABDEFG B．ABCDEFG C．DACEFBG D．ADCFEG