数据结构与算法教程 习题答案作者 朱明方 吴及 第4章习题解答.doc

《数据结构与算法教程 习题答案作者 朱明方 吴及 第4章习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第4章习题解答4.1如图4-51所示的树中，找出树中度最大的结点，说明度的值？找出树中度最小的结点，其度是多少？该树的度是多少？它的深度是多少？[解答]该树中,度最大的结点分别是包含元素A和C的结点，它们的度都为3，它也就是该树的度。树中的叶子结点是图4-51度最小的结点，它们分别是包含元素E,F,G,H,I,J的结点，它们的度都为0。该树深度为3。4.2一棵共有n个结点的树，其所有分支结点的度都为k，请求出该树的叶子结点数。[解答]设树中的分支结点数为nk，叶子结点数n0，则有：n=nk+n0，①设分支数为B，因为除了根结点以外每个结点都有一个分支指向，因此有：B=n-1，②另

2、一方面，所有分支都由分支结点发出，则有：B=nk*k，③比较②、③式有：nk*k=n-1，即：nk=，④将④代入①，可得：n0=n-。所以该树的叶子结点数为：n-。4.3已知一棵度为m的树中，有n1个度为1的结点，有n2个度为2的结点，…，有nm个度为m的结点，请计算该树中的叶子结点数。[解答]设该树共有n个结点，叶子结点数为n0，则有：n=n0+n1+n2+…+nm①另一方面，树中除了根结点以外每个结点都有一个指针指向，也就是说总指针数与总结点数之间相差1；而树中的指针都是由非叶子结点发出的，由此可以得到：n=1+n1+2*n2+3*n3+…+m*nm②比较式①、②有：n0=1

3、+n2+2n3+(m-1)nm=1+4.4假设以孩子表示法用定长结点表示一棵有n个结点，度为k的树，请计算出树中的空指针数目。[解答]因为树的度为k，n个定长结点共有nk个指针域；除根结点外，每个结点有一个指针指向，即，树中共有n-1个指针。12所以，空指针域个数为：nk-(n-1)=n(k-1)+1(个)。4.5树与二叉树有何异同？度为2的有序树与二叉树有何区别？[解答]树与二叉树都具有明显的层次结构,都是表示一对多的联系。对于非空的情况，它们都有一个特殊的没有前件的根结点，其余结点有唯一的前件，而每个结点可以有多个后件。但是树中每个结点的后件个数没有限制，这些后件之间的次序可

4、以是不固定的；而二叉树中每个结点的后件个数不能大于2，后件的位置顺序是固定的，不能随便交换。根据有序树与二叉树的定义可以知道，度为2的有序树与二叉树有着相同之处，例如：它们都是分层的结构，它们的所有结点的度都不大于2，它们的子树的位置顺序是确定的，不能随意交换；但是它们又有不同之处，例如：在度为2的有序树，至少存在一个度为2的分支结点，而在二叉树中可以没有度为2的结点。因此，它们是两种不同的结构。4.6假设某完全二叉树共有500个结点，请问：(1)该二叉树有多少层？(2)它有多少个叶子结点？(3)它有多少个度为2的结点？[解答](1)设该二叉树的深度为k，则k=ëlog2500û

5、+1=9，即，该完全二叉树有9层。(2)因为二叉树共有500个结点，根据完全二叉树的特点可知，该二叉树的最后一个非叶子结点只有左孩子其度为1，其余结点是度为2的结点和叶子结点；因此有：n0+n2=499，又：n2=n0-1，所以有：2n0-1=499，n0=250，即，该完全二叉树有250个叶子结点。(3)根据n2=n0-1，有：n2=250-1=249，即，该完全二叉树有249个度为2的结点。4.7某二叉树为理想平衡树，它共有n个结点，求该二叉树的深度。[解答]根据求完全二叉树深度的推导过程可知，理想平衡树其深度的计算与完全二叉树是一样的，即其深度为：h=ëlog2nû+1。4

6、.8已知某二叉树的中序遍历结果为CBDAXYZ，后序遍历的结果为CDBZYXA。(1)请恢复该二叉树（画出其结构图）；(2)写出该二叉树的前序遍历序列。[解答](1)由二叉树中序遍历和后序遍历的规律可以知道，后序遍历序列中处于最后位置的元素是二叉树的根结点元素，在中序遍历序列中处于根结点元素左边的是该二叉树的左子树结点的元素，处于根结点元素右边的是该二叉树的右子树结点的元素。按照上述思路可以分别对左子树和右子树再划分出根结点元素、左子树结点元素和右子树结点元素三部分，并对其左、右子树继续进行上述过程，…12，直到某一层的左、右子树为空，即确定了所有元素在二叉树中的位置，也就恢复了

7、二叉树。其恢复过程如图4-1所示。图4-1恢复二叉树过程(2)该二叉树的前序遍历序列为：ABCDXYZ。4.9写出满足以下条件的二叉树深度h的可能值：(1)二叉树的前序序列与中序序列相同；(2)二叉树的前序序列与后序序列相同。[解答]由二叉树的前序遍历、中序遍历和后序遍历的规律可以知道(1)前序遍历序列与中序遍历序列相同的二叉树有可能是：空二叉树、只有根结点的二叉树和所有结点都只有右孩子的二叉树。因此，如果满足该条件的二叉树有n个结点，则其深度h可以由h=n求得。(2)前序遍历序