首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
已知一棵二叉树用二叉链表存储,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
92
问题
已知一棵二叉树用二叉链表存储,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
程序员下午应用技术考试
软考初级
相关试题推荐
下列快捷功能按钮中,可以在画好的图形内填充颜色的是(49)。
数据收集的基本原则中不包括(7)。
在Word2007编辑过程中,为防止突然断电或电脑死机等突发情况,最大程度减少损失,下列做法较好的是__________。
在Excel2007中,(43)________________不是计算从A1到A6单元格中数据之和的公式。
在Excel的A2单元格中输入:“=1=2”,则显示的结果是______。
在Excel中,在单元格C1中输入函数“=ROUND(653.54897,2)”,按回车键后,C1单元格中的值为()。
数据处理过程中经常会发生数据出错,因此,数据校验工作非常重要。实际工作中一般都需要采取某些有效的数据校验措施,但有些做法是很少采用的。例如,在每个处理阶段结束后,要求(26)。
连接主机A与交换机的单根网线的最大长度为多少?为了控制局域网用户访问Internet时只能进行WWW浏览,网管应该在路由器上采取什么措施?
综合布线系统由6个子系统组成,将图1-1中(1)~(6)处空缺子系统的名称填写在答题纸对应的解答栏内。为满足公司要求,通常选用什么类型的信息插座?
随机试题
在我国古代,男方家择定婚期,并在形式上商请女家同意,是指()
下列结构中具有芳香性的是()
血中直接测定的HCO3-实际数值应表示为
项背强直,肢体酸重,筋脉拘急,胸脘痞闷,身热,渴不欲饮,溲短赤,苔黄腻,脉滑数,选用
某地铁工程,车站主体结构采用明开法施上,区间隧道及出入口采用暗挖法施工。区间隧道埋深20m左右,其上方为民房及商场,施工区域内有热力、雨污水及电力洞等多种管线。工程施工前,施工单位根据没计文件及各种相关资料,发现隧道距各管线的净距均在3.5~4.5m之间,
对任何一个账户来说,期末余额都等于期初余额+本期借方发生额-本期贷方发生额。()
根据《税务登记管理办法》的规定,凡有法律、法规规定的应税收入、应税财产或应税行为的各类纳税人,均应当办理税务登记,但扣缴义务人则不需办理税务登记。()
一个再冥顽不灵的人,也知道要(),而不是锦衣夜行;一个再不慕虚荣的人,也会把荣誉的光环放大于家人之间。
研究表明,每天跑步的人比通常不跑步的人身体更健康。因此,每天跑步能够促进入的身体健康。最能削弱上述研究结论的是:
ChooseTWOlettersA-E.Writeyouranswersinboxes39and40onyouranswersheet.WhichTWOofthefollowingdoesthe
最新回复
(
0
)