首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。 函数LevelTraVerse()的
admin
2017-08-31
81
问题
一般的树结构常采用孩子-兄弟表示法表示,即用二叉链表作为树的存储结构,链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。例如,如图15-1(a)所示的树的孩子.兄弟表示如图15一1(b)所示。
函数LevelTraVerse()的功能是对给定树进行层序遍历。例如,当对图15.1(a)中的树进行层序遍历时,结点的访问次序为DBAEFPC。
对树进行层序遍历时使用了队列结构,实现队列基本操作的函数原型如表15一1所示。
Bool、Status类型定义如下:
typedef enum{FALSE=0,TRUE=1)Bool;
typedef enum{OVERFLOW=一2,UNDERFLOW=一1,ERROR=0,OK=1}Status;
树的二叉链表结点定义如下:
typedef struct Node{
char data;
struct Node*firstchild,*nextbrother;
}Node,*TreeNode;
【函数代码】
Status LevelTraverse(TreeNode root)
{/*层序遍历树,树采用孩子一兄弟表示法,root是树根结点的指针*/
Queue temQ ;
TreeNode ptr, brOtherptr;
if(!root)
return ERROR;
InitQueue(&tempQ);
(1);
brotherptr=root一>nextbrother;
while( brotherptr ){
EnQueue( &tempQ, brotherptr);
(2),
}/*end-while*/
while( (3) ){
(4),
printf(”%c\t”,ptr一>data);
if( (5) )continue;
(6),
brotherptr=ptr一>firstchild一>nextbrother;
while(brotherptr){
EnQueue(&tempQ,brotherptr);
(7);
}/*end—while*/
}/*end-while*/
return OK;
}/*LevelTraverse*/
选项
答案
(1)EnQueue(&tempQ,root)。 (2)brotherptr=brotherptr->nextbrother。 (3)!IsEmpty(tempQ)。 (4)DeQueue(&tempQ,&ptr)。 (5)!ptr->firstchild。 (6)EnQueue(&tempQ,ptr->firstchild)。 (7)brotherptr=brotherptr->nextbrother。
解析
解答此题的关键在于理解用队列层序遍历树的过程。算法的流程是这样的:首先将树根结点入队,然后将其所有兄弟结点入队(当然,由于是根结点,故无兄弟结点);完成这一操作以后,便开始出队、打印;在打印完了之后,需要进行一个判断,判断当前结点有无孩子结点,若有孩子结点,则将孩子结点入队,同时将孩子结点的所有兄弟结点入队;完了以后继续进行出队操作,出队后再次判断当前结点是否有孩子结点,并重复上述过程,直至所有结点输出。
这一描述可能过于理论,难以理解,接下来以本题为例来说明此过程。首先将树根结点D入队,并同时检查是否有兄弟结点,对于兄弟结点应一并入队。这里的D没有兄弟结点,所以队列此时应是:
D
接下来执行出队操作。D出队,出队以后检查D是否有子结点,经检查,D有子结点B,所以将B入队,同时将B的兄弟结点:A和E按顺序入队。得到队列:
B
A
E
接下来再执行出队操作。B出队,同时检查B是否有子结点,B无子结点,所以继续执行出队操作。A出队,同时检查A是否有子结点,A有子结点F,所以将F入队,同时将F的兄弟结点P入队。得到队列:
E
F
P
接下来再次执行出队操作。E出队,E有子结点C,所以C入队。得:
F
P
C
接下来再次执行出队操作。F出队,F无子结点,继续出队操作,P出队,仍无子结点,最后C出队,整个过程结束。
通过对算法的详细分析,现在便可轻松得到答案。(1)应是对根结点root执行入队操作,即.EnQueue(&tempQ,root)。(2)在一个循环当中,循环变量是brotherptr,此变量无语句对其进行更新,所以(2)必定是更新brotherptr。结合前面的算法分析可知(2)应填:brotherptr=brotherptr->nextbrother。(3)、(4)加上后面的语句“printf(“%c\t”,ptr->data);”是控制数据的输出,这些数据应是从队列中得到,所以此处必有出队操作,同时在出队之前应判断队列是否为空,所以(3)、(4)填:!IsEmpty(tempQ)和DeQueue(&tempQ,&ptr)。(5)实际上是问“在什么情况下,要持续进行出队操作?”,前面的算法分析中已指出:若出队结点无子结点,则继续进行出队操作,所以(5)填!ptr->flrstchild。(6)和(7)所在的语句段的功能是将刚出队结点的子结点及其兄弟结点入队,所以(6)填:EnQueue(&tempQ,ptr->firstchild)。(7)和(2)相同,填brotherptr=brotherptr->nextbrother。
转载请注明原文地址:https://kaotiyun.com/show/eODZ777K
本试题收录于:
软件设计师下午应用技术考试题库软考中级分类
0
软件设计师下午应用技术考试
软考中级
相关试题推荐
网络负载平衡(NetworkLoadBalancing)的核心是位于网络适配器驱动和(1)之间的WLBS.SYS的筛选器驱动。它采用一种(2),根据传入客户端的(3),以统计方式将其映射到群集主机。当发现到达的数据包时,所有主机同时执行这种映射,以快速
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?VPN是在不安全的Internet中通信的,通信的内容可能涉及企业的机密数据,因此保证其安全性非常重要。VPN中的安全技术通常由加密、认证及密钥交换与管理组成,请简要解释其认证技
如果以前已经配置过这台服务器为VPN服务器,现在需要重新配置,该怎么操作?在Windows2000服务器上分配给客户端使用的IP地址时的注意事项是什么?
根据该单位防火墙与外部网络相关的网络连接参数,请将以下命令行中(1)~(4)空缺处的内容填写完整,以完成对防火墙相应的网络接口进行地址初始化的配置。FireWall(config)#ipaddressinside(1)(2)
阅读以下关于ADSL宽带接入Internet的技术说明,请结合网络拓扑结构图,根据要求回答问题1至问题5。【说明】某边远山区的行政机关需要与该地区的市委行政机关进行网络互连,提高行政办事效率,并要求与Internet网互连,从而打开该山区原信息
在交换机上可以配置虚拟局域网(VLAN),以下是部分配置清单。回答问题1、问题2、问题3、问题4和问题5,将解答填入对应栏内。>enablegconfigtEnterconfigurationcommands,oneperli
ISDN分哪几层?NT2(网络终端连接设备)提供哪两种交换功能?如果ISDN收费是按每分钟计算,假如0.5元/分钟,采用ISDN基本速率接口下载1024k的文件需要付费多少?
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。某商务公司在全国各城市共有15个分支机构,这些机构已经建设了基于大型关系数据库的信息管理系统,每天负责独立地处理本区域内的业务并实时存储业务数据。每个
对一个大型校园网工程进行网络备份系统设计时,应考虑解决哪些主要的问题?请用150字以内的文字简要说明。备份就是对数据文件的备份,备份网络文件就是将所需要的文刊:复制到光盘、磁带或磁盘等存储介质上。这种备份网络文件的思路是否正确?请用200字以内的文字简
请说出图9-1的拓扑结构名称与特点。根据IP地址与子网掩码,请判断它们是否属于同一个网段?如果不是,请说出他们分别属于哪个网段。
随机试题
首先应考虑下列哪项诊断根据以上情况应采取哪项措施
治疗霍乱首选为
盛夏,一黄牛在拉车过程中突然发病,站立不稳,张口呼吸,全身大汗,被毛湿润,体温升高达42.1℃,呼吸增快,每分钟达73次,呼吸时鼻孔开张,舌伸出于口外;很快倒地,四肢不停划动,口吐白沫,血管怒张,结膜发绀,心音微弱。该病最可能是
A、处三年以下有期徒刑或者拘役。并处或单处罚金B、处三年以上十年以下有期徒刑,并处罚金C、处十年以上有期徒刑、无期徒刑或者死刑并处罚金D、处二年以下有期徒刑或者拘役。并处或单处罚金E、处二年以上七年以下有期徒刑并处罚
列入国家基本药物目录药品的条件包括()。
要客观地看待杀人游戏,其名字耸人听闻,但游戏规则中透出的东西含有一定逻辑分析、交际演讲的成分,有一定的积极意义,属于心理游戏范畴。在国外,不少公司用这个游戏来测试职员的思辨、表达和判断能力。但既然是游戏,肯定也有负面的东西,正如电脑游戏和网络游戏让众多家长
严重饥饿时脑组织的能量主要来源于()。
共同犯罪人可分为()。
Althoughthefalsebanknotesfooledmanypeople,theydidnot______toacloseexamination.
Technically,anysubstanceotherthanfoodthataltersourbodilyormentalfunctioningisadrug.Manypeoplemistakenbelieve
最新回复
(
0
)