第六章树及二叉树
一、 下面是有关二叉树的叙述，请判断正误
(V) 1.若二叉树用二叉链表作存贮结构，则在 n个结点的二叉树链表中只有n— 1个非空 指针域。 (X) 2.二叉树中每个结点的两棵子树的高度差等于 (V) 3.二叉树中每个结点的两棵子树是有序的。
(X) 4.二叉树中每个结点有两棵非空子树或有两棵空子树。
(X) 5.二叉树中每个结点的关键字值大于其左非空子树(若存在的话)所有结点的关键字 值，且小
1。
于其右非空子树(若存在的话)所有结点的关键字值。(应当是二叉排序树的特点)
(X) 6.二叉树中所有结点个数是2-1，其中k是树的深度。(应2-1 )
k-1
i
(X) 7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。
(X) 8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2 — 1个结 点。
i
(应 2 )
i-1
(V) 9.用二叉链表法(link-rlink )存储包含n个结点的二叉树，结点的2n个指针区域中
有n+1个为空指针。
(正确。用二叉链表存储包含n个结点的二叉树，结点共有2n个链域。由于二叉树中，除根 结点外，每一个结点有且仅有一个双亲，所以只有 n-1个结点的链域存放指向非空子女结点 的指针，还有n+1个空指针。)即有后继链接的指针仅n-1个。
(V) 10.具有12个结点的完全二叉树有5个度为2的结点。
最快方法：用叶子数=[n/2] = 6,再求n2=no-仁5
()11、哈夫曼树中没有度为1的结点，所以必为满二叉树。 ()12、在哈夫曼树中，权值最小的结点离根结点最近。 ()13、线索二叉树是一种逻辑结构。 (V ) 14、深度为K的完全二叉树至少有
2-1个结点。
K
(V )15、具有n个结点的满二叉树，其叶结点的个数为(n+1) /2。 (V )16、前序和中序遍历用线索树方式存储的二叉树，不必使用栈。
(X )17、哈夫曼树是带权路径长度最短的树，路径上权值较大的点离根较远。
二、 填空
1. 2.
由3个结点所构成的二叉树有 —5—种形态。
一棵深度为6的满二叉树有』+化=0+ n2= n。-1=31 —个分支结点和_2 =32—个叶子。
6-1
注：满二叉树没有度为1的结点，所以分支结点数就是二度结点数。
3. _____________________________________________________________ 一棵具有2 5 7个结点的完全
二叉树，它的深度为 —9 ____________________________________________ 。 (注：用 IL log 2(n)
4.
+1= IL 8.xx +仁9
设一棵完全二叉树有700个结点，则共有_ 350 —个叶子结点。 答：最快方法：用叶子数二[n/2] = 350
5.
设一棵完全二叉树具有1000个结点，则此完全二叉树有_50L个叶子结点，有_499_个
1
度为2的结点，有—1—个结点只有非空左子树，有—0 ___________ 个结点只有非空右子树。
答：最快方法：用叶子数二[n/2] = 500, n2=no-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 次序） 和中序法（也称对称序法，即按 LN R次序）。这三种方法相互之间有关联。若已知一棵二叉 树的前序序列是BEFCGDH中序序列是FEBGCHD则它的后序序
列必是 _______ F E G H D C B _______________ 。 解：法1:先由已知条件画图，再后序遍历得到结果；
法2:不画图也能快速得出后序序列，只要找到根的位置特 征。由前序先确定root，由中序先确定左子树。例如，前序遍 历BEFCGD中，根结点在最前面，是 B;则后序遍历中B 一定 在最后面。
法3:递归计算。如B在前序序列中第一，中序中在中间（可知左右子树上有哪些元素） ，
则在后序中必为最后。如法对 B的左右子树同样处理，则问题得解。
8. 中序遍历的递归算法平均空间复杂度为 —0（n） _。
答：即递归最大嵌套层数，即栈的占用单元数。精确值应为树的深度 递归了一次。
9.
k+1,包括叶子的空域也
用5个权值{3, 2, 4, 5, 1} 构造的哈夫曼（Huffman）树的带权路径长度是 —33 _。
WP』（4+ 5+ 3）X 2+（ 1+ 2）
解：先构造哈夫曼树，得到各叶子的路径长度之后便可求出
X 3=33
（15）
......
/（9）
妙、 注：两个合并值先后不同会导致编码不同，即哈夫曼编码不唯一）
（注：合并值应排在叶子值之后）
1 2
4 5 3 ' （3）
（注：原题为选择题：A. 32
10.
B. 33 C. 34
D. 15）
N个结点的二叉树采用二叉链表
n+1
6
存放，共有空链域个数为
11.
深度为6 （根层次为1、的二叉树至多有2 - 1 个结点。
12._______________________________________________________________________________ 已知一棵
完全二叉树的第5层有3个结点，其叶子结点数是__9_ _________________________________ 。 三、单项选择题
2
（C ） 1.不含任何结点的空树 _____________ 。
（A）是一棵树；
（C）是一棵树也是一棵二叉树；
（B）是一棵二叉树； （D）既不是树也不是二叉树
答：以前的标答是B,因为那时树的定义是n》1
3
数据结构第6章二叉树作业及答案汇总
