收藏 分销(赏)

数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc

上传人:w****g 文档编号:1362661 上传时间:2024-04-24 格式:DOC 页数:9 大小:303KB
下载 相关 举报
数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc_第1页
第1页 / 共9页
数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc_第2页
第2页 / 共9页
数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc_第3页
第3页 / 共9页
数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc_第4页
第4页 / 共9页
数据结构-C语言版-第二版(严蔚敏)-第5章--树和二叉树-答案.doc_第5页
第5页 / 共9页
点击查看更多>>
资源描述

1、第5章 树和二叉树1选择题(1)把一棵树转换为二叉树后,这棵二叉树的形态是( )。 A唯一的 有多种C有多种,但根结点都没有左孩子 有多种,但根结点都没有右孩子答案:A 解释:因为二叉树有左孩子、右孩子之分,故一棵树转换为二叉树后,这棵二叉树的形态是唯一的。(2)由3个结点可以构造出多少种不同的二叉树?( )A2 B3 C4 D5 答案:D解释:五种情况如下: (3)一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。A250 B 500 C254 D501 答案:D解释:设度为0结点(叶子结点)个数为A,度为1的结点个数为B,度为2的结点个数为C,有A=C+1,A+B+C=1001

2、,可得2C+B=1000,由完全二叉树的性质可得B=0或1,又因为C为整数,所以B=0,C=500,A=501,即有501个叶子结点。(4)一个具有1025个结点的二叉树的高h为( )。A11 B10 C11至1025之间 D10至1024之间答案:C解释:若每层仅有一个结点,则树高h为1025;且其最小树高为log21025+1=11,即h在11至1025之间。(5)深度为h的满m叉树的第k层有( )个结点。(1=k=lchild=NULL&T-rchild=NULL)return 1; /判断结点是否是叶子结点(左孩子右孩子都为空),若是则返回1elsereturn LeafNodeCou

3、nt(T-lchild)+LeafNodeCount(T-rchild);(2)判别两棵树是否相等。题目分析先判断当前节点是否相等(需要处理为空、是否都为空、是否相等),如果当前节点不相等,直接返回两棵树不相等;如果当前节点相等,那么就递归的判断他们的左右孩子是否相等。算法描述int pareTree(TreeNode* tree1, TreeNode* tree2)/用分治的方法做,比较当前根,然后比较左子树和右子树bool tree1IsNull = (tree1=NULL);bool tree2IsNull = (tree2=NULL);if(tree1IsNull != tree2Is

4、Null)return 1;if(tree1IsNull & tree2IsNull)/如果两个都是NULL,则相等return 0;/如果根节点不相等,直接返回不相等,否则的话,看看他们孩子相等不相等if(tree1-c != tree2-c)return 1;return (pareTree(tree1-left,tree2-left)&pareTree(tree1-right,tree2-right) (pareTree(tree1-left,tree2-right)&pareTree(tree1-right,tree2-left);/算法结束(3)交换二叉树每个结点的左孩子和右孩子。题

5、目分析如果某结点左右子树为空,返回,否则交换该结点左右孩子,然后递归交换左右子树。算法描述void ChangeLR(BiTree &T)BiTree temp;if(T-lchild=NULL&T-rchild=NULL)return;elsetemp = T-lchild;T-lchild = T-rchild;T-rchild = temp;/交换左右孩子ChangeLR(T-lchild); /递归交换左子树ChangeLR(T-rchild); /递归交换右子树(4)设计二叉树的双序遍历算法(双序遍历是指对于二叉树的每一个结点来说,先访问这个结点,再按双序遍历它的左子树,然后再一次访

6、问这个结点,接下来按双序遍历它的右子树)。题目分析若树为空,返回;若某结点为叶子结点,则仅输出该结点;否则先输出该结点,递归遍历其左子树,再输出该结点,递归遍历其右子树。算法描述void DoubleTraverse(BiTree T)if(T = NULL)return;else if(T-lchild=NULL&T-rchild=NULL)coutdata; /叶子结点输出elsecoutdata;DoubleTraverse(T-lchild); /递归遍历左子树coutdata; DoubleTraverse(T-rchild); /递归遍历右子树(5)计算二叉树最大的宽度(二叉树的最

7、大宽度是指二叉树所有层中结点个数的最大值)。题目分析 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法,记下各层结点数,每层遍历完毕,若结点数大于原先最大宽度,则修改最大宽度。算法描述int Width(BiTree bt)/求二叉树bt的最大宽度if (bt=null) return (0); /空二叉树宽度为0else BiTree Q;/Q是队列,元素为二叉树结点指针,容量足够大front=1;rear=1;last=1;/front队头指针,rear队尾指针,last同层最右结点在队列中的位置temp=0; maxw=0; /temp记局部宽度, maxw记最大宽度Qrear=

8、bt; /根结点入队列while(frontlchild!=null) Q+rear=p-lchild; /左子女入队if (p-rchild!=null) Q+rear=p-rchild; /右子女入队if (frontlast) /一层结束, last=rear;if(tempmaxw) maxw=temp;/last指向下层最右元素, 更新当前最大宽度 temp=0; /if /whilereturn (maxw);/结束width(6)用按层次顺序遍历二叉树的方法,统计树中具有度为1的结点数目。题目分析若某个结点左子树空右子树非空或者右子树空左子树非空,则该结点为度为1的结点算法描述i

9、nt Level(BiTree bt) /层次遍历二叉树,并统计度为1的结点的个数int num=0; /num统计度为1的结点的个数 if(bt)QueueInit(Q); QueueIn(Q,bt);/Q是以二叉树结点指针为元素的队列while(!QueueEmpty(Q)p=QueueOut(Q); coutdata; /出队,访问结点if(p-lchild & !p-rchild |!p-lchild & p-rchild)num+;/度为1的结点if(p-lchild) QueueIn(Q,p-lchild); /非空左子女入队if(p-rchild) QueueIn(Q,p-rch

10、ild); /非空右子女入队 / while(!QueueEmpty(Q)/if(bt) return(num); /返回度为1的结点的个数 (7)求任意二叉树中第一条最长的路径长度,并输出此路径上各结点的值。题目分析因为后序遍历栈中保留当前结点的祖先的信息,用一变量保存栈的最高栈顶指针,每当退栈时,栈顶指针高于保存最高栈顶指针的值时,则将该栈倒入辅助栈中,辅助栈始终保存最长路径长度上的结点,直至后序遍历完毕,则辅助栈中内容即为所求。算法描述void LongestPath(BiTree bt)/求二叉树中的第一条最长路径长度BiTree p=bt,l,s; /l, s是栈,元素是二叉树结点指

11、针,l中保留当前最长路径中的结点int i,top=0,tag,longest=0;while(p | top0)while(p) s+top=p;tagtop=0; p=p-Lc; /沿左分枝向下if(tagtop=1) /当前结点的右分枝已遍历if(!stop-Lc & !stop-Rc) /只有到叶子结点时,才查看路径长度if(toplongest) for(i=1;i0) tagtop=1; p=stop.Rc; /沿右子分枝向下/while(p!=null|top0)/结束LongestPath(8)输出二叉树中从每个叶子结点到根结点的路径。题目分析采用先序遍历的递归方法,当找到叶子

12、结点*b时,由于*b叶子结点尚未添加到path中,因此在输出路径时还需输出b-data值。算法描述void AllPath(BTNode *b,ElemType path,int pathlen)int i; if (b!=NULL)if (b-lchild=NULL & b-rchild=NULL) /*b为叶子结点cout data 到根结点路径: data; for (i=pathlen-1;i=0;i-) cout data; /将当前结点放入路径中 pathlen+; /路径长度增1 AllPath(b-lchild,path,pathlen); /递归扫描左子树 AllPath(b-rchild,path,pathlen); /递归扫描右子树 pathlen-; /恢复环境 / if (b!=NULL)/算法结束

展开阅读全文
部分上传会员的收益排行 01、路***(¥15400+),02、曲****(¥15300+),
03、wei****016(¥13200+),04、大***流(¥12600+),
05、Fis****915(¥4200+),06、h****i(¥4100+),
07、Q**(¥3400+),08、自******点(¥2400+),
09、h*****x(¥1400+),10、c****e(¥1100+),
11、be*****ha(¥800+),12、13********8(¥800+)。
相似文档                                   自信AI助手自信AI助手
搜索标签

当前位置:首页 > 通信科技 > 开发语言

移动网页_全站_页脚广告1

关于我们      便捷服务       自信AI       AI导航        获赠5币

©2010-2024 宁波自信网络信息技术有限公司  版权所有

客服电话:4008-655-100  投诉/维权电话:4009-655-100

gongan.png浙公网安备33021202000488号   

icp.png浙ICP备2021020529号-1  |  浙B2-20240490  

关注我们 :gzh.png    weibo.png    LOFTER.png 

客服