数据结构第6章树和二叉树：课后习题全解析（选择题+填空题+综合题+算法设计题）
第6章 树和二叉树 课后习题
一、单项选择题
1.一棵有n个结点，采用链式存储的二叉树中，共有（A）个指针域为空。
A.n+1
B.n
C.n−1
D.n−2
解析：
链式存储二叉树中，每个结点有2个指针域（左孩子、右孩子），总指针域数为2n。
除根结点外，每个结点有且仅有一个父结点指向它（即用掉一个非空指针），共用掉 n−1个非空指针。
因此空指针域数为 2n−(n−1)=n+1。
2.设一棵哈夫曼树共有n个非叶子结点，则该树有（B）个叶子结点。
A.n
B.n+1
C.n−1
D.2n
解析：
哈夫曼树是严格的二叉树（没有度为 1 的结点）,非叶子结点即是双分支节点，叶子结点比双分支节点多一个。
3.一棵完全二叉树共有5层，且第5层有6个结点，该树共有（C）个结点。
A. 30
B. 20
C. 21
D. 23
解析：
完全二叉树前 4 层为满二叉树，结点数 15。
加上第 5 层的 6 个结点，总结点数 =15+6=21。
4.在一棵二叉树中，若编号为i的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D）。
A.i/2
B.i/2+1
C.2i+1
D.⌊i/2⌋
解析：
在顺序存储（数组下标从 1 开始）的完全二叉树中，结点 i的双亲编号为 ⌊i/2⌋(向下取整)，无论它是左孩子还是右孩子。
5.一棵采用链式存储的二叉树中有n个指针域为空，该二叉树共有（C）个结点。
A.n+1
B.n
C.n−1
D.n−2
解析：
由第 1 题结论：空指针域数 = 结点数 + 1。
结点数=空指针域数-1。
6.一棵结点数31<n<40的完全二叉树，最后一层有4个结点，则该树有（B）个叶子结点。
A. 17
B. 18
C. 36
D. 35
7.设一棵哈夫曼树共有2n+1个结点，则该树有（A）个非叶子结点。
A.n
B.n+1
C.n−1
D.2n
解析：
哈夫曼树中叶子结点数 = 非叶子结点数 + 1。
设非叶子结点数为 x，则总结点数 =x+(x+1)=2x+1。
已知总结点数为 2n+1，所以 2x+1=2n+1，即 x=n。
8.在一棵具有35个结点的完全二叉树中，该树的深度为（B）。
A. 7
B. 6
C. 5
D. 8
9.在一棵二叉树中，若编号为i的结点存在左孩子，则左孩子结点的顺序编号为（A）。
A. 2i
B. 2i - 1
C. 2i + 1
D. 2i + 2
10.在一棵具有n个结点的二叉树的第i层上，最多具有（C）个结点。
A.2i
B.2i+1
C.2^(i−1)
D.2n
解析：
二叉树第 i 层（根为第 1 层）最多有2^(i−1)个结点（满二叉树的情况）。
二、填空题
1.设有一棵深度为4的完全二叉树，第4层有5个结点，该树共有12个结点（根所在结点为第1层）。
2.在二叉树的链式存储结构中，通常每个结点中设置3个域，它们是值域、左指针域、右指针域。
3.中序遍历二叉排序树可得到一个有序序列。
4.设有一棵有78个结点的完全二叉树，该树共有7层（根所在结点为第1层）。
5.一棵3度的树，其有3度结点1个，2度结点2个，1度结点2个，则该树共有5个叶子结点。
6.二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉树：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值；若它的右子树非空，则右子树的所有结点的值都大于（若允许结点有相同的值，则大于或等于）它的根结点的值。这种说法是正确的。（回答正确或错误）
7.一棵有7个叶子结点的二叉树，其1度结点数的个数为2，则该树共有15个结点。
8.一棵有20个结点的4度的树，其有3度结点1个，2度结点1个，1度结点2个，则该树共有14个叶子结点。
三、综合题
1.回答下列问题：
(1)以2, 3, 4, 7, 8, 9作为叶子结点的权，构造一棵哈夫曼树，给出相应权值叶子结点的哈夫曼编码。
(2)一棵哈夫曼树有n个叶子结点，它一共有多少个结点？简述理由。
答：（1）哈夫曼树如下：
叶子结点的哈夫曼编码如下：
2：0100
3：0101
4：011
7：10
8：11
9：00
(2)共有2n−1个结点。
理由：哈夫曼树是严格二叉树（无一度结点），有n0=n个叶子，则n2=n−1 个二度结点，总结点 n0+n2=2n−1。
2.回答下列问题：
(1)对给定权值2, 1, 3, 3, 4, 5，构造哈夫曼树。
(2)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权路径长度。
答案：
带权路径长度=1*3+2*3+3*3+3*3+4*2+5*2=3+6+9+9+8+10=45
带权路径长度=1*4+2*4+3*3+3*2+4*2+5*2=4+8+9+6++8+10=45
3.对于如图6-16所示的二叉树：
(1)给出中序遍历序列。
(2)给出先序遍历序列。
(3)给出后序遍历序列。
图6-16
答：
(1)中序遍历序列：dgbaechif
(2)先序遍历序列：abdgcefhi
(3)后序遍历序列：gdbeihfca
四、算法设计题
1.根据下面的函数声明编写求一棵二叉树中结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。
int BTreeNode(struct BTreeNode *BT);
答：
int BTreeNode(struct BTreeNode *BT) { if (BT == NULL) { return 0; } else { return 1 + BTreeNode(BT->left) + BTreeNode(BT->right); } }2.根据下面的函数声明编写求一棵二叉树中叶子结点总数的算法，该总数值由函数返回。假定参数BT初始指向二叉树的根结点。
int BTreeLeafCount(struct BTreeNode *BT);
答：
int BTreeLeafCount(struct BTreeNode *BT) { if (BT == NULL) { return 0; } if (BT->left == NULL && BT->right== NULL) { return 1; } return BTreeLeafCount(BT->left) + BTreeLeafCount(BT->right); }3.根据下面的函数声明编写从一棵二叉树BT中求出结点值大于x的结点个数的算法，并返回所求结果。
int BTreeCountBig(struct BTreeNode *BT, int x);
答：
int BTreeCountBig(struct BTreeNode *BT, int x) { if (BT == NULL) { return 0; } int count = (BT->data > x) ? 1 : 0; count += BTreeCountBig(BT->left, x); count += BTreeCountBig(BT->right, x); return count; }