首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一棵二叉树用二叉链表存储,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
146
问题
已知一棵二叉树用二叉链表存储,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
程序员下午应用技术考试
软考初级
相关试题推荐
数据收集的基本原则中不包括(7)。
人类传播信息的五大类媒体按其出现的先后顺序排列为________。
在Windows XP中,文件名中不允许出现的字符是(32)。
下列关于计算机病毒的说法中错误的是_______。
在用Word软件编辑文档时,若误删除了一个数据,随后可使用______命令进行恢复。
职工的“工资级别”与“职工”的联系是__________。
在WindowsXP中,删除某个应用程序在桌面上的快捷方式,则(42)。
某软件公司职工以下的行为中,除________外,都侵害了本单位的权益。
计算机在接通电源后,系统首先由(41)程序对内部每个设备进行测试。
某公司统计一季度考勤情况如下:根据公司规定,凡缺勤不超过2天的人,每人发200元考勤奖;凡缺勤天数超过5天的人,每人每天缺勤从工资中扣50元,用于发放其他人的考勤奖。根据上表,计算该公司还需要拿出(29)元作为一季度的考勤奖。
随机试题
Excel2010单元格中输入的内容,可通过______________进行确认。
以下影响发病的因素不属于外环境的是
某男,25岁,高热,咳吐脓血腥臭痰属()
国家康居示范工程的规划设计中,提倡城市住宅宜以哪种类型为主?
在焊接方法分类中,属于非熔化极的焊接方法有()。
Joyinlivingcomesfromhavingfineemotions,trustingthem,givingthemthe【E1】f______ofabirdintheopen.Joyinlivingcan
2008年年底,我国网民数从1997年的62万增加到2.98亿,居世界第2位。其中宽带网民数达到2.7亿,手机网民数达到1.2亿。互联网普及率达到22.6%,超过全球平均水平。2008年年底,我国互联网的国际出口带宽由1997年的25.4Mbps
以下叙述中正确的是
WhichmetalweretheCeltsusingatthebeginningofthefirstmillenniumB.C.?
Areyoualwayssureyouknowwhatpeoplemeanwhentheytrytodescribetheirfeelingstoyou?Weusebothwordsand【C1】______to
最新回复
(
0
)