（推荐）数据结构习题课4.ppt
1,数据结构习题 第 4 章,吉林大学计算机科学与技术学院 谷方明,2,第4章作业,4-2，4-3， 4-5，4-6，4-7，4-8， 4-10， 4-12，4-13,3,作业4-2,题目描述 由三个结点A，B和C可以构成多少棵不同的树？可以构成多少棵不同的二叉树？,4,树有2种形态：6+3=9种 二叉树有5种形态：6*5=30种,5,作业4-3,判断以下命题是否为真？若真，请证明之；否则，举出反例。 一棵二叉树形的所有的叶结点，在先根次序、中根次序和后根次序下的排列都按相同的相对位置出现。,6,先根： 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等于二叉树的高度； n=0时 命题成立 假设 n = k 时命题成立，往证n=k+1时命题也成立。当 n = k+1 时，对任意两个叶结点l1,l2，有三种情况 l1，l2 都在根的左子树中。 l1，l2 都在根的右子树当中。 l1，l2 不在根的同一个子树当中。,8,作业4-5,编写一算法，判别给定二叉树是否为完全二叉树。,9,分析,完全二叉树的叶子结点只能在层数最大两层出现，并且连续出现 在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。 层次遍历时，空指针可以入队。出队遇到第一个空指针时，此后队列里的都是空指针。 对所有结点按完全二叉树编号，记录编号的最大值和结点数n。相等，则是完全二叉树。 设有一个指针数组，下标代表编号，数组元素代表结点。出现空缺编号或编号大于n，则不是完全二叉树。 建立编号函数，递归记录结点数和编号最大值,10,参考算法如下,为此，在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。 时间复杂性为 T(n)=2n 或 O(n),11,bool completetree(BintreeNode * t) Bool B=1; Queue Q ; if (t!=NULL) Q.Insert(t); while (!Q.QueueEmpty() ,12,while (!Q.QueueEmpty() /处理剩余叶节点 p=Q.Delete(); if ( p-left ! = NULL) | ( p-right ! = NULL) return false; return true; ,13,4-6,编写算法求任意二叉树中一条最长的路径，并输出此路径上各结点的值。,14,分析,教材中，树上的路径定义：若树T中存在结点序列Vm - Vm+1 - Vm+k ，1<= k <=T的最大层数， Vi+1 是 Vi 的子结点。 相当于求根结点开始的最长路径。可以根据左右子树的高度确定下一步的结点。,15,参考答案,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-left; else t=t-right; ,16,时间复杂度为O(n2)或O(n*h)。原因在于高度的重复计算。在每个结点中引入高度域，可以将时间复杂度为降为O(n)。 树上的路径也有另一种理解，即图论的理解。这时，最长路不一定是从根结点出发的，需要先确定路径最长的结点，然后按前面的方法处理。也可以按第五章的方法处理。,17,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)+height(t-right)+2maxl; lstp=t; Longest(t-left); Longest(t-right); ,18,其它方法,课后提示：非递归后根遍历，当i=2是，判断是否为叶子节点，若是就与当前记录的最长路径比较，大于就更新最大路径值及最大路径。 回溯法：引入一个数组记录路径上的结点。递归出口是叶子结点。非叶子结点继续尝试和修改,19,4-7,编写算法判断两棵二叉树T和T是否相似。两棵二叉树相似是指它们具有相同结构。,20,参考答案,算法Like(t1,t2) /*判断两棵二叉树是否相似,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-8,对于下图所示的树 （a）对其进行先根和后根遍历。 （b）给出其在自然对应下的二叉树。,22,参考答案,（a）对其进行先根和后根遍历。 先根遍历：ABEKGJFCGDHI 后根遍历：KGJEFBGCHIDA （b）给出其在自然对应下的二叉树。,23,作业4-10,对以左儿子右兄弟链接表示的树，编写计算树的深度的算法。,24,分析,解题思路1 对树做层次遍历，每遍历一层树的深度+1. 关键：将队列中的结点结构变为(结点，该结点的层数i) 。,25,算法Depth(t. d) /解题思路1 对树做层次遍历，每遍历一层树的深度+1. D1 判断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 Q(FirstChild(p),d+1) pNextBrother(p) .) ) ,26,分析,解题思路2 树的深度dept(t)=max(t的各子树的深度)+1,27,算法 Depth(t. d) /解题思路2 树的深度dept(t)=max(t的各子树的深度)+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 . RETURN. ,28,分析,解题思路3 基于对应的二叉树直接求树的深度。 dept(t)=max(左子树的深度+1，右子树的深度),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-12,题目描述 构造权值为 5,13,21, 7,18,30,41的哈夫曼树。,31,首先，在森林中取权值最小的两个根结点s和n，合成一棵二叉树，新生成的结点T1，作为这两个结点的父结点，T1的权值是两个子结点的权值之和； 对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。,32, 5，13，21，7，18，30，41 ,25,80,55,135,12,39,5,7,13,30,18,21,41,33,4-13,编写算法计算二叉树中边的个数。,34,分析,边数=结点数-1；各种遍历计算结点数 直接计算边数。 时间复杂度都是O(n),35,算法E(t.n) /*计算二叉树t的边数，结果放在n中*/ L1递归出口 n 0. IF t=NULL THEN RETURN. L2递归调用 IF (left(t)NULL) THEN(E(left(t),n1).n n+1+n1.). IF (right(t)NULL) THEN(E(right(t),n2).n n+1+n2.). ,36,小结,树的定义是递归的，导致树的题目多用递归。 先序遍历、中序遍历、后序遍历是三种经典的递归。树上的很多递归算法都可以认为是它们的变种。 递归书写是，最好把递归出口写在前面。 层次遍历是另一种常用的解题方法。树和二叉树的遍历是解题的核心算法,
