首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一棵二叉树用二叉链表存储,t指向根节点,P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。 [C程序] #define MaxSize 1000 typedef struct node { TelemType d
已知一棵二叉树用二叉链表存储,t指向根节点,P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。 [C程序] #define MaxSize 1000 typedef struct node { TelemType d
admin
2012-12-10
88
问题
已知一棵二叉树用二叉链表存储,t指向根节点,P指向树中任一节点。下列算法为输出从t到P之问路径上的节点。
[C程序]
#define MaxSize 1000
typedef struct node {
TelemType data ;
struct node *ichiid,*rchiid;
}BiNode,*BiTree;
void Path(BiTree t,BiNode *P)
{BiTree *stack[Maxsize],*stackl[Maxsize],*q;
int tag[Maxsize],top=0,topl;
q=t;
/*通过先序遍历发现P*/
do{while(q!=NULL &&q!=p)
/*扫描左孩子,_日.相应的节点不为P*/
{ (1) ;
stack[top]=q;
tag[top]=0;
(2) ;
}
if(top>0)
{ if(stack[top]=P) break; /*找到P,栈底到栈顶为t到P*/
if(tag[top]==1)top--;
else { q=stack[top];
q=q->rchiid;
tag[top]=1;
}
}
} (3) ;
top--;topl=0;
while(top>0) {
q=stack[top]; /*反向打印准备*/
topl++;
(4) ;
top--;
}
while( (5) ){ /*打印栈的内容*/
q=stackl[topl]j
printf(q->data);
topl--;
}
}
选项
答案
(1)top++ (2) q=q->lchild (3) while(top>0) (4) stackl[topl]=q (5) topl>0
解析
本题本质上是对二叉树的先序遍历进行考核,但不是简单地进行先序遍历,而是仅遍历从根节点到给定的节点p为止。本题采用非递归算法来实现,其主要思想是:①初始化栈;②根节点进栈,栈不空则循环执行以下步骤直到发现节点p;③当前节点不为空且不为P进栈;④栈顶为p,则结束,否则转③;⑤若右子树访问过,则栈顶的右孩子为当前节点,转③。
扫描左孩子,.当相应的节点不为P时进栈,所以(1)填“top++”,(2)填“q=q->lchild”。在栈不为空时则一直在do while循环中查找,因此(3)填“while(top>0)”。在进行反向打印准备时,读取stack[top]的信息放到stackl[topl]中,即(4)填“stackl[top1]=q”。打印栈中所有内容,所以(5)填“topl>0”。
转载请注明原文地址:https://kaotiyun.com/show/1njZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
下列(28)不属于电子商务的应用模式。
某企业长期从事大量的数据处理工作,所建立的一系列规范中一般不包括________。
图文混排是Word的特色功能之一,下列叙述中,不正确的是(46)。
信息传递的三个基本环节中,信息接收者称为(9)________________。
在Excel中,函数“=AVERAGE(A1,.B4)”的含义是()。
Windows系统的快捷方式确切的含义是______。
在Excel中,A1,A2,B1,B2,C1,C2单元格的值分别为1、2、3、4、3、5,在D1单元格中输入函数“=SUM(A1:B2,B1:C2)”,按回车键后,D1单元格中显示的值为______。
用高级语言编写的程序称为______。
连接主机A与交换机的单根网线的最大长度为多少?为了控制局域网用户访问Internet时只能进行WWW浏览,网管应该在路由器上采取什么措施?
防火墙包过滤规则的默认策略为拒绝,下表给出防火墙的包过滤规则配置界面。若要求内部所有主机能使用IE浏览器访问外部IP地址为202.117.118.23的Web服务器,为图中(1)~(4)空缺处选择正确答案。(1)A.允许B.拒绝(2)A.192
随机试题
正常人触觉语颤的生理差异为()
下列对间歇热的叙述正确的是
冬季,某猪场引种1周后,部分引入母猪体温41~42℃,厌食。流产,腹部和后肢皮肤发紫,并迅速传播至全场,抗生素治疗无效,与疫情密切相关的因素是
肾盂肾炎最常见的感染途径是
A.全蝎B.牛黄C.海螵蛸D.蟾蜍E.羚羊角具有“乌金衣”特征的药材是()
债务人将合同义务全部或者部分转移给第三人的,的应当( )。
2015年高考结束后,小明和其同学去北方某城市避暑休闲了1个月,在此期间,主要活动包括:(1)向当地人张某租赁了一套住房,支付了1个月的房租4000元,同时向某汽车租赁公司租赁了一辆汽车,支付了1个月的租金5000元;(2)去当地知名影院观看暑期档上映
幼儿园的双重任务是指幼儿园对幼儿实施保育和教育以及()。
根据《专利法》的规定,下列关于专利强制许可的表述,错误的是()。
Inthepast,theParkServicefocusedonmakingthebigscenicparksmore【21】andcomfort-ablefortourists.Roadswerepavedto
最新回复
(
0
)