第六章 树及二叉树
一、下面是有关二叉树的叙述，请判断正误 （√） 1. 若二叉树用二叉链表作存贮结构，则在 n 个结点的二叉树链表中只有 n—1 个非空 指针域。
（×）2. 二叉树中每个结点的两棵子树的高度差等于 1。 （√）3. 二叉树中每个结点的两棵子树是有序的。
（×）4. 二叉树中每个结点有两棵非空子树或有两棵空子树。
（×）5. 二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字 值，且小于其右非空子树 （若存在的话） 所有结点的关键字值。（应当是二叉排序树的特点） （×）6.二叉树中所有结点个数是 2k-1 -1 ，其中 k 是树的深度。（应 2i-1）
（×）7. 二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
（×）8. 对于一棵非空二叉树， 它的根结点作为第一层， 则它的第 i 层上最多能有 2i —1个结 点。（应 2i-1 ）
（√）9. 用二叉链表法（ link-rlink ）存储包含 n 个结点的二叉树，结点的 2n 个指针区域中 有 n+1 个
为空指针。
（正确。用二叉链表存储包含 n 个结点的二叉树，结点共有 2n 个链域。由于二叉树中，除根 结点外，每一个结点有且仅有一个双亲，所以只有 n-1 个结点的链域存放指向非空子女结点 的指针，还有 n+1 个空指针。）即有后继链接的指针仅 n-1 个。
（√） 10.具有 12个结点的完全二叉树有 5个度为 2的结点。 最快方法：用叶子数＝ [n/2] ＝6，再求
n2=n0-1=5
（ ） 11 、哈夫曼树中没有度为 1 的结点，所以必为满二叉树。 （ ） 12、在哈夫曼树中，权值最小
的结点离根结点最近。
（ ）13 、线索二叉树是一种逻辑结构。 （√ ）14、深度为 K的完全二叉树至少有 2K-1 个结点。 （ √ ）15 、具有 n个结点的满二叉树，其叶结点的个数为（ n+1）/2 。 （ √ ）16 、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。
（ ╳ ）17 、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。
二、填空
1． 由３个结点所构成的二叉树有
5 种形态。
2. 一棵深度为 6的满二叉树有 n1+n2=0+ n2= n 0-1=31 个分支结点和 26-1 =32 个叶子。 注：满二叉树没
有度为 1 的结点，所以分支结点数就是二度结点数。
3． 一棵具有２５７个结点的完全二叉树，它的深度为
9 。
（ 注：用 log 2（n） +1= 8.xx +1=9
4. 设一棵完全二叉树有 700 个结点，则共有 350 个叶子结点。 答：最快方法：用叶子数＝ [n/2] ＝
350
1
5. 设一棵完全二叉树具有 1000个结点，则此完全二叉树有 500 个叶子结点， 有 499 个 度为 2 的结
点，有 1 个结点只有非空左子树，有 0 个结点只有非空右子树。
2
答：最快方法：用叶子数＝ [n/2] ＝500 ，n2=n0-1=499。 另外，最后一结点为 2i 属于左叶子， 右叶子是空的，所以有 1 个非空左子树。完全二叉树的特点决定不可能有左空右不空的情况， 所以非空右子树数＝ 0.
6. 一棵含有 n 个结点的 k 叉树，可能达到的最大深度为
n ，最小深度为 2 。
答：当 k=1（单叉树 ） 时应该最深，深度＝ n（层）；当 k=n-1（n-1 叉树）时应该最浅，深度＝ 2 （层），但不包括 n=0或 1 时的特例情况。教材答案是“完全 k 叉树”，未定量。 ）
7. 二叉树的基本组成部分是：根（ N）、左子树（ L）和右子树（ R）。因而二叉树的遍历次序 有
六种。最常用的是三种：前序法（即按 N L R 次序），后序法（即按
L R N
次序）
和中序法（也称对称序法，即按 L N R 次序）。这三种方法相互之间有关联。若已知一棵二叉 树的前序序列是 BEFCGD，H中序序列是 FEBGCH，D则它的后序序 列必是 F
E G H D C B
。
解：法 1：先由已知条件画图，再后序遍历得到结果；
法 2 ：不画图也能快速得出后序序列，只要找到根的位置特 征。由前序先确定 root ，由中序先确定左子树。例如，前序遍 历 BEFCGD中H ，根结点在最前面，是 B；则后序遍历中 B 一定 在最后面。
法 3：递归计算。如 B 在前序序列中第一，中序中在中间（可知左右子树上有哪些元素） ， 则在后序中必为最后。如法对 B 的左右子树同样处理，则问题得解。
8. 中序遍历的递归算法平均空间复杂度为 O（n） 。 答：即递归最大嵌套层数，即栈的占用单元
数。精确值应为树的深度 递归了一次。
9. 用 5 个权值 {3, 2, 4, 5, 1}
k+1，包括叶子的空域也
构造的哈夫曼（ Huffman）树的带权路径长度是 33 。
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出 ×3=33
（15）
WPL＝（ 4＋5＋3）× 2＋（ 1＋2）
（9） （6） 注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）
4 5 3 （3） （注：合并值应排在叶子值之后）
1 2 （注：
原题为选择
题：
Ａ．32
Ｂ．33
n+1
Ｃ．34 Ｄ．15）
10、N 个结点的二叉树采用二叉链表存放，共有空链域个数为 11、深度为 6（根层次为 1）的二叉树至多有 26 – 1 个结点。
12、 已知一棵完全二叉树的第 5 层有 3 个结点，其叶子结点数是 9 。
3
数据结构第6章二叉树作业及答案汇总
