数据结构习题课4

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

2、在先根次序、中根次序和后根次序下的排列都按相序、中根次序和后根次序下的排列都按相同的相对位置出现。同的相对位置出现。GFEDCBALKJIH先根： 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数学归纳法数学归纳法令n等于二叉树的高度；ln=0时 命题成立l假设 n = k 时命题成立，往证n=k+1时命题也成立。当 n = k+1 时，对任意两个叶结点l1,l2，有三种情况ll1，l2 都在根的左子树中。ll1，l2 都在根的右子树当中。ll1，l2 不在根的同一个子树当中。作业作业4

3、-5l编写一算法，判别给定二叉树是否为完全二叉编写一算法，判别给定二叉树是否为完全二叉树。树。 分析分析l完全二叉树的叶子结点只能在层数最大两层出现，并且连续出现l在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。l层次遍历时，空指针可以入队。出队遇到第一个空指针时，此后队列里的都是空指针。l对所有结点按完全二叉树编号，记录编号的最大值和结点数n。相等，则是完全二叉树。l设有一个指针数组，下标代表编号，数组元素代表结点。出现空缺编号或编号大于n，则不是完全二叉树。l建立编号函数，递归记录结点数和编号最

4、大值参考算法如下参考算法如下l为此，在层次遍历二叉树时，增加一个标为此，在层次遍历二叉树时，增加一个标志志B B，B=1B=1表示所有已扫描过的结点均有左表示所有已扫描过的结点均有左、右孩子，、右孩子，B=0B=0，表示遇到无左或右孩子的，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。结点，此后的所有结点均应为叶结点。l时间复杂性为时间复杂性为 T(nT(n)=2n )=2n 或或 O(nO(n) )bool completetree(BintreeNode * t) Bool B=1; Queue Q ; if (t!=NULL) Q.Insert(t); while (!Q.Qu

5、eueEmpty() & B) p=Q.Delete(); 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); while (!Q.QueueEmpty() /处理剩余叶节点处理剩余叶节点 p=Q.Delete(); if ( p-left ! = NULL) | ( p-right ! = NULL) return false; return true;4-6l编写算法求任意二

6、叉树中一条最长的路径，并输出此路径上各结点的值。 分析分析l教材中，树上的路径定义：若树T中存在结点序列Vm - Vm+1 - Vm+k ，1= k =T的最大层数， Vi+1 是 Vi 的子结点。l相当于求根结点开始的最长路径。可以根据左右子树的高度确定下一步的结点。参考答案参考答案int height(BinTreeNode* t)if(t=NULL) return -1;return 1+max(height(t-left),height(t-right);void path(BinTreeNode* t)while(t)coutdataleft)height(t-right) t=t-

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

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

9、出口 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)4-8l对于下图所示的树l（a）对其进行先根和后根遍历。l（b）给出其在自然对应下的二叉树。AFGIHJKGCDBE参考答案参考答案l（a）对其进行先根和后根遍历。 先根遍历：ABEKGJFCGDHI 后根遍历：KGJEFBGCHIDAl（b）给出其在自然对应下

10、的二叉树。作业作业4-10l对以左儿子对以左儿子右兄弟链接表示的树，编写计算右兄弟链接表示的树，编写计算树的深度的算法。树的深度的算法。分析分析l解题思路1 对树做层次遍历，每遍历一层树的深度+1.关键：将队列中的结点结构变为(结点，该结点的层数i) 。 ACBGDFEACBGDFE算法Depth(t. d)/解题思路1 对树做层次遍历，每遍历一层树的深度+1.D1 判断t是否为NULLIF t=NULL THEN ( d -1 . RETURN )D2 创建辅助队列, 根结点入队CREATE(Q). Q ( t,0) . D3 利用队列Q遍历第d层结点WHILE NOT (IsEmpty(Q

11、) DO ( (p,d) Q . WHILE pNULL DO ( IF FirstChild(p)NULL THEN QFirstChild(p),d+1) pNextBrother(p) .) ) ACBGDFE分析分析l解题思路2 树的深度dept(t)=max(t的各子树的深度)+1ACBGDFEACBGDFE算法算法 Depth(t. d)/解题思路解题思路2 树的深度树的深度dept(t)=max(t的各子树的深度的各子树的深度)+1D1递归出口递归出口 IF t=NULL THEN ( d -1 . RETURN ) IF (GFC(t)=NULL) THEN ( d 0 . R

12、ETURN ) D2递归调用递归调用 p=GFC(t). Max -1. / Max存储各子树的最大深度存储各子树的最大深度 WHILE (pNULL) ( Depth(p. dp). IF (dpMax) THEN Maxdp. pGNB(p). )d Max+1 . RETURN. 分析分析l解题思路3 基于对应的二叉树直接求树的深度。 dept(t)=max(左子树的深度+1，右子树的深度) ACBGDFEACBGDFE算法算法 Depth(t. d)/解题思路3 基于对应的二叉树直接求树的深度D1递归出口递归出口 IF t=NULL THEN ( d -1 . RETURN )D2递归

13、调用递归调用 Depth(GFC(t). d1) Depth(GNB(t). d2) d Max(d1+1, d2).) 作业作业4-12l题目描述 构造权值为 5,13,21, 7,18,30,41的哈夫曼树。l首先，在森林中取权值最小的两个根结点s和n，合成一棵二叉树，新生成的结点T1，作为这两个结点的父结点，T1的权值是两个子结点的权值之和；l对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。 5，13，21，7，18，30，41 25805513512395713301821414-13l编写算法计算二叉树中边的个数。分析分析l边数=结点数-1；各种遍历计算结点数l直接计算边数。l时间复杂度都是O(n)算法E(t.n)/*计算二叉树t的边数，结果放在n中*/L1递归出口递归出口 n 0. IF t=NULL THEN RETURN.L2递归调用递归调用 IF (left(t