首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include<stdio.h> #include<stdlib.h> typedef s
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include<stdio.h> #include<stdlib.h> typedef s
admin
2010-01-15
72
问题
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。
【说明】
本程序利用非递归算法实现二叉树后序遍历。
【函数】
#include<stdio.h>
#include<stdlib.h>
typedef struct node{/*二叉树的结点数据结构类型*/
char data;
struct node *left;
struct node *right;
}BTREE;
void SortTreelnsert(BTREE **tree, BTREE *s)
{
if(*tree==NULL)*tree=s;
else
if(s->data<(*tree)->data)
SortTreelnsert((1),s);
else if(s->data>=(*tree)->data)
SortTreelnsert((2),s);
}
void TraversalTree(BTREE *tree)
{
BTREE *stack[1 000],*p;
int tag[1000],top=0;
p=tree;
do{
while(p !=NULL)
{
stack[++top]=p;
(3);
tag[top]=0; /*标记栈顶结点的左子树已进行过后序遍历*/
}
while(top>0&&(4))/*栈顶结点的右子树是否被后序遍历过*/
{
p=stack[top--];
putchar(p->data);
}
if(top>0)/*对栈顶结点的右子树进行后序遍历*/
{
(5);
tag[top]=1;
}
}while(top>0);
}
void PrintSortTree(BTREE *tree)
{
if(tree !=NULL)
{
printSortTree(tree->left);
putchar(tree->data);
pdntSortTree(tree->right);
}
}
main()
{
BTREE *root=NULL, *node;
char ch;
ch=getchar();
while(ch !=’#’)
{
node=(BTREE*)malloc(sizeof(BTREE));
node->data=ch;
node->left=node->right=NULL;
SortTreelnsert(&root, node);
ch=getchar();
}
PrintSortTree(root);
putchar(’\n’);
TraversalTree(root);
}
选项
答案
(1)&(*tree)->left (2)&(*tree)->right (3)p=p->left (4)tag[top]==1 (5)p=stack[top]->right
解析
本题考查二叉树后序遍历的非递归实现。
二叉树后序遍历的特点是首先按后序遍历根结点的左子树,然后按后序遍历根结点的右子树,再访问根结点。后序遍历得到的序列根结点总在最后,我们可以用栈结构来实现后序遍历。下面来具体[分析]程序。
第(1)空很明显是函数SortTreeInsert()的第一个参数,此函数的功能是建立一棵排序二叉树,此空在条件判断语句下面,如果条件成立,说明待插入结点的值小于当前结点的值,根据排序二叉树的生成原理,应该把待插入结点插入到当前结点的左子树中,因此,此空的参数是指向当前结点左子树的地址。这里需要注意的是,这个参数是一个二重指针,需要在一重指针前加一个取地址操作符“&”。所以,此空答案为&(*tree)->left。
第(2)空也是函数SortTreeInsert()的第一个参数,但调用这个函数的条件与上面不一样,此空是在待插入结点的值大于等于当前结点的值的时候调用函数,根据排序二叉树的生成原理,此时应该把待插入结点插入到当前结点的右子树中,因此,此空答案为&(*tree)->right。
第(3)空在函数TraversalTree()中,此函数用来对树进行后序遍历,此空在一个循环体中,从程序中可以看出这个循环体的功能是将排序二叉树的所有左子树结点入栈,因此,在当前结点入栈后,接下来是它的孩子结点入栈,所以,此空答案为p=p->left。
第(4)空是循环的判断条件,其作用在注释中已经给出,是判断栈顶结点的右子树是否被后序遍历过。从上面程序tag[top]=0表示栈顶结点的左子树已进行过后序遍历可以推断出,tag[top]的值是用来标记栈顶结点的左右子树已进行过后序遍历,因此,此空答案为tag[top]==1。
第(5)空在条件判断语句下面,而条件判断语句为真表明要对栈顶结点的右子树进行后序遍历,那么就应该让当前需处理结点的指针指向栈顶结点的右孩子,而指向当前需要处理结点的指针变量是p,因此,此空答案为p=stack[top]->right。
转载请注明原文地址:https://kaotiyun.com/show/RBjZ777K
本试题收录于:
程序员下午应用技术考试题库软考初级分类
0
程序员下午应用技术考试
软考初级
相关试题推荐
下列快捷功能按钮中,可以在画好的图形内填充颜色的是(49)。
在Word2007中,若用户需要将一篇文章中的字符串“Internet”全部替换为字符串“因特网”,则可以在编辑菜单中选择()命令。
数据分析报告的编写原则中不包括(70)。
在Word中打开英文文档或者在文档中输入英文信息时,系统会自动对拼写和语法进行检查,如果出现红色波形下划线则表示存在(50)。
______不属于企业信息系统存在的问题。
打开DOC文档48.doc,有如下表格,欲在空白单元格中计算出整行其他四个单元格的数值之和,应在空白单元格中插入公式(48)。
某公司下设4个分公司A、B、C、D,上月各分公司的销售额及其在总公司所占比例如下表所示。由于此表单受潮,有些数据看不清了,但还可以推算出来。根据推算, D公司上月的销售额为(68)万元。
由若干条直线段和圆弧等构成的图形,可以用一系列指令来描述。用这种方法描述的图形称为_________。
180的正约数(能整除180的自然数,包括l和180本身)的个数是________。
阅读下列HTML文本和说明,在该HTML文本中存在5处错误,请指出错误所在的行号、错误原因以及改正的方法。[说明]这是一个简单的HTML文本,显示作者个人主页的登录界面。[HTML文本](1)<HTML>(2)<B
随机试题
既然你计划移居加拿大,那你必须努力适应寒冷的气候。
设fn-2(x)=e2x+1,则fn(x)|x=0=0
男性,35岁,讲话中突然剧烈头痛、呕吐。检查:BP140/90mmHg,神志清楚,颈部明显抵抗,四肢肌力正常,双侧Babinski征(﹣)。患者常见的并发症为
前阴后阴为何脏所主
小规模纳税企业应当按照不含税销售额和规定的增值税征收率计算交纳增值税,销售货物或提供应税劳务时只能开具普通发票,不能开具增值税专用发票。()
负责考评的人员到实际工作地点调查工作完成的情况,对工作地点有关人员提供的绩效考核信息,考评人员客观、如实记录、并要求提供绩效信息对所提供信息的验证签字,以确保绩效信息的准确性。这是绩效信息采集方法中的()。
以下是针对《陶瓷艺术》一课拟定的三种不同的教学设计思路,请参照第一种思路的分析方法分别对第二种、第三种思路的优缺点进行简短分析。例子:第一种思路:具有“课堂化"特色的思路。在教室里进行欣赏、评述、交流、讨论。教师最好能准备有特色的陶瓷器皿和其他用品,既
以下资料,回答96-100题2008年,该省城镇单位从业人员数约为:
【S1】【S5】
TheArtofFriendshipMakingFriendsinMidlifeOneeveningafewyearsagoIfoundmyselfinananxiety.Nothingwasreall
最新回复
(
0
)