树与二叉树
1．树的概念
树的逻辑结构特征
树的常用术语及含义
2．二叉树
二叉树的定义，二叉树与树的差别
完全二叉树和满二叉树的概念
二叉树的性质
二叉树的顺序存储结构和链式存储结构的定义和表示方法
3．二叉树的遍历
二叉树的先序、中序、后序、层序遍历算法
求给定二叉树的先序、中序、后序遍历对应的结点访问序列
由二叉树的先序和中序、中序和后序、中序和层序的序列确定二
叉树
以遍历算法为基础，设计有关算法解决简单的应用问题
4．线索二叉树
二叉树线索化的目的
线索二叉树存储结构的表示方法
在线索二叉树中查找给定结点的前趋和后继的方法
5．树和森林
树和森林与二叉树之间的转换方法和对应关系
树的各种存储结构的表示方法及其特点（能对利用二叉链表表示
的树进行程序设计）
树的先序和后序遍历方法
森林的先序和中序遍历方法
6．哈夫曼树及其应用
最优二叉树的概念及特点
求哈夫曼树的方法
设计哈夫曼编码的方法
1. 设树 T 的度为 4 ，其中度为 1，2，3 和 4 的结点个数分别为
4，2，1，1 则 T 中的叶子数为（ m-n ）
2. 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度
为 0 的结点个数是（ 11 ）
3. 设森林 F 中有三棵树，第一，第二，第三棵树的结点个数分别为
M1，M2 和 M3。与森林 F 对应的二叉树根结点的右子树上的结点个
数是（ M2+M3 ）。
4. 设给定权值总数有 n 个，其哈夫曼树的结点总数为( 2n+1 )
5. 若度为 m 的哈夫曼树中，其叶结点个数为 n，则非叶结点的个数
为（é(n-1)/(m-1)ù ）。
6. 一棵二叉树高度为 h,所有结点的度或为 0，或为 2，则这棵二叉
树最少有( 2h-1 )结点。
7. 一 棵 具 有 n 个 结 点 的 完 全 二 叉 树 的 树 高 度 （ 深 度 ） 是 （
ëlognû+1 ）
8. 深度为 h 的满 m 叉树的第 k 层有（ m
k-1
）个结点。
9. 对二叉树的结点从 1 开始进行连续编号，要求每个结点的编号大
于其左、右孩子的编号，同一结点的左右孩子中，其左孩子的编号
小于其右孩子的编号，可采用( 中序 )次序的遍历实现编号。
10．树的后根遍历序列等同于该树对应的二叉树的(中序序列 )。
11. 二叉树的先序遍历和中序遍历如下： 先序遍历：EFHIGJK；中
序遍历: HFIEJKG 。该二叉树根的右子树的根是（G）。
12. 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，
则该二叉树一定满足(只有一个叶子结点)。
13. 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个
数是：( 2 )。
14. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域
的个数是：( 1 )。
15. 若 X 是二叉中序线索树中一个有左孩子的结点，且 X 不为根，
则 X 的前驱为( X 的左子树中最右结点 )。
16. n 个结点的线索二叉树上含有的线索数为（ n+1 ）。
18. 如某二叉树有 20 个叶子结点，有 30 个结点仅有一个孩子，则
该二叉树的总结点数为（69）。
19. 8 层完全二叉树至少有（128）个结点，拥有 100 个结点的完
全二叉树的层数为（7）。
20. 给定 K(K>=1),对一棵含有 N 个结点的 K 叉树（N＞０）、请
讨论其可能的最大高度和最小高度。
答：N 个结点的 K 叉树，最大高度 N（只有一个叶结点的任意 k 叉
树 ） 。 设 最 小高 度 为 H ， 第 i(1<=i<=H) 层 的 结点 数 K
i-1
， 则
N=1+k+k
2
+…+ k
H-1
，由此得 H=ëlog
K
(N(K-1)+1)û
21. 求含有 n 个结点、采用顺序存储结构 A[1..n]的完全二叉树中的
序号最小的叶子结点的下标。
答：根据完全二叉树的性质，最后一个结点（编号为 n）的双亲结
点的编号是 ën/2û，这是最后一个分枝结点，在它之后是第一个终端
（叶子）结点，故序号最小的叶子结点的下标是 ën/2û+1。
22. 若一棵树中有度数为 1 至 m 的各种结点数为 n
1
,n
2
,…,n
m
(n
m
表
示度数为 m 的结点个数)请推导出该树中共有多少个叶子结点 n
0
的
公式。
答：设树的结点数为 n，分枝数为 B，则下面二式成立
n=n
0
+n
1
+n
2
+…+n
m
(1)
n=B+1= n
1
+2n
2
+…+mn
m
(2)
由(1)和(2)得叶子结点数 n
0
=1+
m
i
i
1
i
n)1(
23. 一棵二叉树的中序、后序、先序序列分别如下，其中有一部分未
显示出来，试求出空格处的内容，并画出该二叉树。
