（推荐）数据结构习题课4

1、1 数据结构习题数据结构习题 第第 4 章章 吉林大学计算机科学与技术学院 谷方明 2 第第4 4章作业章作业 l4-2，4-3， l4-5，4-6，4-7，4-8， l4-10， l4-12，4-13 3 作业作业4-24-2 l题目描述题目描述 由三个结点由三个结点A A，B B和和C C可以构成多少棵不同的树可以构成多少棵不同的树 ？可以构成多少棵不同的二叉树？可以构成多少棵不同的二叉树？ 4 l树有2种形态：6+3=9种 l二叉树有5种形态：6*5=30种 5 作业作业4-34-3 l判断以下命题是否为真？若真，请证明之判断以下命题是否为真？若真，请证明之 ；否则，举出反例。；否则，举

2、出反例。 一棵二叉树形的所有的叶结点，在先根次一棵二叉树形的所有的叶结点，在先根次 序、中根次序和后根次序下的排列都按相序、中根次序和后根次序下的排列都按相 同的相对位置出现。同的相对位置出现。 6 GFE DC B A LKJI H 先根： A B C E I F J D G H K L 中根： E I C F J B G D K H L A 后根： I E J F C G K L H D B A 7 数学归纳法数学归纳法 令n等于二叉树的高度； ln=0时 命题成立 l假设 n = k 时命题成立，往证n=k+1时命题也 成立。当 n = k+1 时，对任意两个叶结点 l1,l2，有三种情

3、况 ll1，l2 都在根的左子树中。 ll1，l2 都在根的右子树当中。 ll1，l2 不在根的同一个子树当中。 8 作业作业4-54-5 l编写一算法，判别给定二叉树是否为完全二叉编写一算法，判别给定二叉树是否为完全二叉 树。树。 9 分析分析 l完全二叉树的叶子结点只能在层数最大两层出现，并 且连续出现 l在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描 过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的 结点，此后的所有结点均应为叶结点。 l层次遍历时，空指针可以入队。出队遇到第一个空指针时， 此后队列里的都是空指针。 l对所有结点按完全二叉树编号，记录编号的最大值和 结点数

4、n。相等，则是完全二叉树。 l设有一个指针数组，下标代表编号，数组元素代表结点。出 现空缺编号或编号大于n，则不是完全二叉树。 l建立编号函数，递归记录结点数和编号最大值 10 参考算法如下参考算法如下 l为此，在层次遍历二叉树时，增加一个标为此，在层次遍历二叉树时，增加一个标 志志B B，B=1B=1表示所有已扫描过的结点均有左表示所有已扫描过的结点均有左 、右孩子，、右孩子，B=0B=0，表示遇到无左或右孩子的，表示遇到无左或右孩子的 结点，此后的所有结点均应为叶结点。结点，此后的所有结点均应为叶结点。 l时间复杂性为时间复杂性为 T(n)=2n T(n)=2n 或或 O(n)O(n) 1

5、1 bool completetree(BintreeNode * t) Bool B=1; Queue Q ; if (t!=NULL) Q.Insert(t); while (!Q.QueueEmpty() if (p-left = = NULL) B=0; if (p-right != NULL) return false; else Q.Insert(p-left); if (p-right = = NULL) B=0; else Q.Insert(p-right); 12 while (!Q.QueueEmpty() /处理剩余叶节点处理剩余叶节点 p=Q.Delete(); if

6、( p-left ! = NULL) | ( p-right ! = NULL) return false; return true; 13 4-64-6 l编写算法求任意二叉树中一条最长的路径，并 输出此路径上各结点的值。 14 分析分析 l教材中，树上的路径定义：若树T中存在结点 序列Vm - Vm+1 - Vm+k ，1= k =T的 最大层数， Vi+1 是 Vi 的子结点。 l相当于求根结点开始的最长路径。可以根据左 右子树的高度确定下一步的结点。 15 参考答案参考答案 int height(BinTreeNode* t) if(t=NULL) return -1; return

7、1+max(height(t-left),height(t-right); void path(BinTreeNode* t) while(t) coutdataleft)height(t-right) t=t- left; else t=t-right; 16 l时间复杂度为O(n2)或O(n*h)。原因在于高度 的重复计算。在每个结点中引入高度域，可以 将时间复杂度为降为O(n)。 l树上的路径也有另一种理解，即图论的理解。 这时，最长路不一定是从根结点出发的，需要 先确定路径最长的结点，然后按前面的方法处 理。也可以按第五章的方法处理。 17 TreeNodeTreeNode* * ls

8、tp=NULL; lstp=NULL; int maxl=-1;int maxl=-1; void Longest(TreeNodevoid Longest(TreeNode* * t) t) if(t=NULL) return NULL if(t=NULL) return NULL； if(height(t-left)+height(t-right)+2maxl)if(height(t-left)+height(t-right)+2maxl) maxl=height(t-left)+height(t-maxl=height(t-left)+height(t- right)+2maxl;rig

9、ht)+2maxl; lstp=t; lstp=t; Longest(t-left); Longest(t-left); Longest(t-right); Longest(t-right); 18 其它方法其它方法 l课后提示：非递归后根遍历，当i=2是，判断 是否为叶子节点，若是就与当前记录的最长路 径比较，大于就更新最大路径值及最大路径。 l回溯法：引入一个数组记录路径上的结点。递 归出口是叶子结点。非叶子结点继续尝试和修 改 19 4-74-7 l编写算法判断两棵二叉树T和T是否相似。 两棵二叉树相似是指它们具有相同结构。 20 参考答案参考答案 算法Like(t1,t2) /*判断两

10、棵二叉树是否相似,t1,t2表示两棵树的根节点 。若相似，返回值为true，否则为false*/ L1递归出口递归出口 IF t1=NULL AND t2=NULL THEN RETURN true. IF t1=NULL OR t2=NULL THEN RETURN false. L2递归调用递归调用 RETURN Like(left(t1),left(t2) AND Like(right(t1),right(t2). 时间复杂度为O(n1+n2) 21 4-84-8 l对于下图所示的树 l（a）对其进行先根和后根遍历。 l（b）给出其在自然对应下的二叉树。 A FGIH JKG CD B

11、E 22 参考答案参考答案 l（a）对其进行先根和后根遍历。 先根遍历：ABEKGJFCGDHI 后根遍历：KGJEFBGCHIDA l（b）给出其在自然对应下的二叉树。 23 作业作业4-104-10 l对以左儿子对以左儿子右兄弟链接表示的树，编写计算右兄弟链接表示的树，编写计算 树的深度的算法。树的深度的算法。 24 分析分析 l解题思路1 对树做层次遍历，每遍历一层树的深度+1. 关键：将队列中的结点结构变为(结点，该结点的层 数i) 。 A C B G D F E A CB G D FE 25 算法Depth(t. d) /解题思路1 对树做层次遍历，每遍历一层树的深度+1. D1 判

12、断t是否为NULL IF t=NULL THEN ( d -1 . RETURN ) D2 创建辅助队列, 根结点入队 CREATE(Q). Q ( t,0) . D3 利用队列Q遍历第d层结点 WHILE NOT (IsEmpty(Q) DO ( (p,d) Q . WHILE pNULL DO ( IF FirstChild(p)NULL THEN QFirstChild(p),d+1) pNextBrother(p) .) ) A C B G D F E 26 分析分析 l解题思路2 树的深度dept(t)=max(t的各子树的深度 )+1 A CB G D FE A C B G D F

13、 E 27 算法算法 Depth(t. d) /解题思路解题思路2 树的深度树的深度dept(t)=max(tdept(t)=max(t的各子树的深度的各子树的深度)+1)+1 D1递归出口递归出口 IF t=NULL THEN ( d -1 . RETURN ) IF (GFC(t)=NULL) THEN ( d 0 . RETURN ) D2递归调用递归调用 p=GFC(t). Max -1. / Max存储各子树的最大深度存储各子树的最大深度 WHILE (pNULL) ( Depth(p. dp). IF (dpMax) THEN Maxdp. pGNB(p). ) d Max+1 .

14、 RETURN. 28 分析分析 l解题思路3 基于对应的二叉树直接求树的深度。 dept(t)=max(左子树的深度+1，右子树的深度) A C B G D F E A CB G D FE 29 算法算法 Depth(t. d) /解题思路3 基于对应的二叉树直接求树的深度 D1递归出口递归出口 IF t=NULL THEN ( d -1 . RETURN ) D2递归调用递归调用 Depth(GFC(t). d1) Depth(GNB(t). d2) d Max(d1+1, d2). ) 30 作业作业4-124-12 l题目描述 构造权值为 5,13,21, 7,18,30,41的哈夫曼

15、树 。 31 l首先，在森林中取权值最小的两个根结点s和n ，合成一棵二叉树，新生成的结点T1，作为这 两个结点的父结点，T1的权值是两个子结点的 权值之和； l对新的森林重复上一步操作，直至森林中只有 唯一的根结点时，终止操作。 32 5，13，21，7，18，30，41 25 8055 135 12 39 5 7 13 30 18 21 41 33 4-134-13 l编写算法计算二叉树中边的个数。 34 分析分析 l边数=结点数-1；各种遍历计算结点数 l直接计算边数。 l时间复杂度都是O(n) 35 算法E(t.n) /*计算二叉树t的边数，结果放在n中*/ L1递归出口递归出口 n 0. IF t=NULL THEN RETURN. L2递