第6章 树和二叉树 课后习题一、单项选择题1.一棵有n个结点采用链式存储的二叉树中共有A个指针域为空。A.n1B.nC.n−1D.n−2解析链式存储二叉树中每个结点有2个指针域左孩子、右孩子总指针域数为2n。除根结点外每个结点有且仅有一个父结点指向它即用掉一个非空指针共用掉 n−1个非空指针。因此空指针域数为 2n−(n−1)n1。2.设一棵哈夫曼树共有n个非叶子结点则该树有B个叶子结点。A.nB.n1C.n−1D.2n解析哈夫曼树是严格的二叉树没有度为 1 的结点,非叶子结点即是双分支节点叶子结点比双分支节点多一个。3.一棵完全二叉树共有5层且第5层有6个结点该树共有C个结点。A. 30B. 20C. 21D. 23解析完全二叉树前 4 层为满二叉树结点数 15。加上第 5 层的 6 个结点总结点数 15621。4.在一棵二叉树中若编号为i的结点是其双亲结点的右孩子则双亲结点的顺序编号为D。A.i/2B.i/21C.2i1D.⌊i/2⌋解析在顺序存储数组下标从 1 开始的完全二叉树中结点 i的双亲编号为 ⌊i/2⌋(向下取整)无论它是左孩子还是右孩子。5.一棵采用链式存储的二叉树中有n个指针域为空该二叉树共有C个结点。A.n1B.nC.n−1D.n−2解析由第 1 题结论空指针域数 结点数 1。结点数空指针域数-1。6.一棵结点数31n40的完全二叉树最后一层有4个结点则该树有B个叶子结点。A. 17B. 18C. 36D. 357.设一棵哈夫曼树共有2n1个结点则该树有A个非叶子结点。A.nB.n1C.n−1D.2n解析哈夫曼树中叶子结点数 非叶子结点数 1。设非叶子结点数为 x则总结点数 x(x1)2x1。已知总结点数为 2n1所以 2x12n1即 xn。8.在一棵具有35个结点的完全二叉树中该树的深度为B。A. 7B. 6C. 5D. 89.在一棵二叉树中若编号为i的结点存在左孩子则左孩子结点的顺序编号为A。A. 2iB. 2i - 1C. 2i 1D. 2i 210.在一棵具有n个结点的二叉树的第i层上最多具有C个结点。A.2iB.2i1C.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哈夫曼树如下叶子结点的哈夫曼编码如下20100301014011710811900(2)共有2n−1个结点。理由哈夫曼树是严格二叉树无一度结点有n0n个叶子则n2n−1 个二度结点总结点 n0n22n−1。2.回答下列问题(1)对给定权值2, 1, 3, 3, 4, 5构造哈夫曼树。(2)同样用上述权值构造另一棵哈夫曼树使两棵哈夫曼树有不同的高度并分别求两棵树的带权路径长度。答案带权路径长度1*32*33*33*34*25*2369981045带权路径长度1*42*43*33*24*25*24896810453.对于如图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; }
