《数据结构与算法教程 习题答案作者 朱明方 吴及 第4章习题解答》由会员分享，可在线阅读，更多相关《数据结构与算法教程 习题答案作者 朱明方 吴及 第4章习题解答（12页珍藏版）》请在金锄头文库上搜索。
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 比
3、较式、有：n0 = 1 + n2 + 2n3 + (m-1)nm = 1+ 4.4 假设以孩子表示法用定长结点表示一棵有n个结点，度为k的树，请计算出树中的空指针数目。解答 因为树的度为k，n个定长结点共有nk个指针域；除根结点外，每个结点有一个指针指向，即，树中共有n-1个指针。所以，空指针域个数为：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) 设该二叉树的深
5、度为k，则 k= log2500 +1= 9，即，该完全二叉树有9层。(2) 因为二叉树共有500个结点，根据完全二叉树的特点可知，该二叉树的最后一个非叶子结点只有左孩子其度为1，其余结点是度为2的结点和叶子结点；因此有：n0 + n2 = 499，又：n2=n0-1，所以有：2 n0 -1= 499，n0 = 250 ， 即，该完全二叉树有250个叶子结点。(3) 根据n2=n0-1，有：n2 = 250-1 = 249 ，即，该完全二叉树有249个度为2的结点。4.7 某二叉树为理想平衡树，它共有n个结点，求该二叉树的深度。解答 根据求完全二叉树深度的推导过程可知，理想平衡树其深度的计算与
6、完全二叉树是一样的，即其深度为： h=log2n +1 。 4.8 已知某二叉树的中序遍历结果为CBDAXYZ，后序遍历的结果为CDBZYXA。(1) 请恢复该二叉树（画出其结构图）；(2) 写出该二叉树的前序遍历序列。解答(1) 由二叉树中序遍历和后序遍历的规律可以知道，后序遍历序列中处于最后位置的元素是二叉树的根结点元素，在中序遍历序列中处于根结点元素左边的是该二叉树的左子树结点的元素，处于根结点元素右边的是该二叉树的右子树结点的元素。按照上述思路可以分别对左子树和右子树再划分出根结点元素、左子树结点元素和右子树结点元素三部分，并对其左、右子树继续进行上述过程，直到某一层的左、右子树为空，
7、即确定了所有元素在二叉树中的位置，也就恢复了二叉树。其恢复过程如图4-1所示。图4-1 恢复二叉树过程 (2) 该二叉树的前序遍历序列为：ABCDXYZ 。4.9 写出满足以下条件的二叉树深度h的可能值：(1) 二叉树的前序序列与中序序列相同；(2) 二叉树的前序序列与后序序列相同。解答由二叉树的前序遍历、中序遍历和后序遍历的规律可以知道(1) 前序遍历序列与中序遍历序列相同的二叉树有可能是：空二叉树、只有根结点的二叉树和所有结点都只有右孩子的二叉树。因此，如果满足该条件的二叉树有n个结点，则其深度h可以由h =n 求得。 (2) 前序遍历序列与后序遍历序列相同的二叉树有可能是：空二叉树和只有
8、根结点的二叉树。因此，满足该条件的二叉树其深度h可能是0或1 。4.10 写出中序遍历二叉树的非递归算法。解答中序遍历二叉树的非递归算法描述如下： void InOrderBT1 ( BTreeNode *BT, int h ) / BT 指向二叉树根结点的指针, h二叉树的深度 BTreeNode *p = BT ； / p 指向当前要处理的结点，初始指向根结点SeqStack (S)； / 建立栈S，栈中元素类型为二叉树结点指针类型InitStack (S, h ) ； / 初始化结点指针栈Swhile ( p | ! EmptyStack (S ) ) / 当前结点p为空且栈中无结点，结
9、束遍历 if ( p!= NULL ) / 当前结点不空，将其入栈，遍历左子树 Push (S, p ) ； p= p-Lchild ； else p= Pop (S ) ； / 当前结点为空，栈不空，退出栈顶结点成为当前结点printf (%d n, p-data ) ； / 访问当前结点p= p-Rchild ； / 进入右子树遍历4.11 假设二叉树的结点值均为正整数，如果约定以二叉树的前序序列作为输入序列，且以“0”表示空结点值，则可以运用二叉树前序遍历的思路来建立二叉树，请写出该思路下建立二叉树的递归算法。解答按照题中约定，假设该二叉树中的分支结点都有左、右孩子，空孩子结点值以0表示
10、，例如，图4-2所示的二叉树其输入的前序序列为：66，44，26，0，88，30，0，0，10，54，70，0，0。它实际上具有8个结点值，结点值为0的结点是 空结点。 图 4-2 以前序序列建立二叉树示例 读入以上的前序序列建立二叉树的算法思路是：读入一个结点值，为其建立一个结点，并且 通过根结点的指针引用使其成为根结点，然后递 归建立左、右子树，以读入0作为递归返回。假设以-1表示二叉树前序序列的结束标志，上述思路建立二叉树算法描述如下： BTreeNode *Create_BTree (BTreeNode *BT) / 以读入的二叉树前序序列，建立以BT为根结点的二叉树 int item
11、 ；scanf (%d, &item ) ； / 读入一个结点值 if (item != -1 ) / 当读入值为-1时结束读入 if (item != 0)/ 为刚读入的元素分配一个新结点，置其为根结点 BT=( BTreeNode*) malloc(sizeof( BTreeNode) ； if (!BT ) / 检查结点分配是否成功 printf ( Memory allocation failure! n) ； exit (1) ； BT-data= item ； / 置根结点的元素值BT-Lchild= NULL ； / 置根结点的左右指针BT-Rchild= NULL ； Crea
12、te_BTree ( BT-Lchild ) ； / 递归建立左子树中结点 Create_BTree ( BT-Rchild ) ； / 递归建立左子树中结点 elseBT= NULL ； / 若读入值为0，返回空树 return BT ;4.12 假设以二叉链表表示二叉树，请写出以下算法：(1) 统计出二叉树的结点数。(2) 输出二叉树的所有叶子结点。解答(1) 统计二叉树结点数的算法描述如下：int Count_Node ( BTreeNode *BT ) / BT指向二叉树根结点的指针，返回结点数 if (!BT ) return 0 ； / 二叉树为空返回0int c1= Count_Node ( BT-Lchild ) ； / 递归，统计出左子树的结点数int c1= Count_Node ( BT-Rchild ) ； / 递归，统计出右子树的结点数int count= c1+ c2 + 1 ； / 求出二叉树的全部结点数return count ； / 返回二叉树的结点数
