首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include<stdio.h> #include<stdlib.h> typedef s
阅读以下说明和C语言函数,将应填入(n)处的语句写在对应栏内。 【说明】 本程序利用非递归算法实现二叉树后序遍历。 【函数】 #include<stdio.h> #include<stdlib.h> typedef s
admin
2010-01-15
77
问题
阅读以下说明和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
程序员下午应用技术考试
软考初级
相关试题推荐
信息系统运行过程中的数据备份工作不包括________________。
数据的收集方式可有多种,分别适用于各种情况。以下数据收集方式,不恰当的是______。
某村领导要求信息处理技术员估计该村一池塘中的鱼的大致数量。该技术员想出了一个办法:先从池塘中捕出30条鱼,在每条鱼身上做一记号后,又放回池塘。几天后,再从该池塘中捕出40条鱼,发现其中有2条是有记号的。因此,他估计该池塘鱼的数量大致为(68)条(假设这几天
计算机采用二进制的好处不包括______。
数据录入工作有两个指标:录入速度和错误率。一般而言,数据录入员在录入大批数据时,录入速度会(65),错误率会(66)。65
甲、乙两队同时开凿一条640米长的隧道。甲队从一端起,每天掘进7米;乙队从另一端起,每天比甲队多掘进2米,两队在距离隧道中点(30)米的地方会合。
打开DOC文档48.doc,有如下表格,欲在空白单元格中计算出整行其他四个单元格的数值之和,应在空白单元格中插入公式(48)。
删除Windows中某个应用程序的快捷方式,意味着(39)。
在Excel2007中,若在单元格A1中输入函数“=ROUNDUP(3.1415926,2)”,按回车键后,则A1单元格中的值为______。
解决网络安全问题的技术分为主动防御保护技术和被动防御保护技术两大类,__________属于被动防御保护技术。
随机试题
关于高钾血症的处理错误的是
善治血淋、尿血的药物是
炒炭后常用于止血的药物是蜜炙后多用于止咳平喘的药物是
组织设计的原则包括()。
2010年10月5日,甲公司与乙公司签订技术转让合同,该合同约定:甲公司将A发明专利权转让给乙公司,转让款为200万元;乙公司在合同签订后三个工作日内付40万元,在办理完转让登记手续后三个月内付160万元。同时,甲公司告知乙公司,甲公司曾于2009年11月
外商投资企业必须符合下列哪些条件才能作为发起人()
根据下列资料。回答问题。2013年1—10月份,全国民间固定资产投资223427亿元,同比增长23.4%,增速比1—9月份加快0.1个百分点。民间固定资产投资占固定资产投资的比重为63.5%。分地区看,东部地区民间固定资产投资10849
下列关于清末对诉讼法律修订的表述,正确的是()。
AnIntelligentCarDrivingneedssharpeyes,keenears,quickbrain,andcoordinationbetweenhandsandthebrain.Manyhumandr
I’musuallyfairlyskepticalaboutanyresearchthatconcludesthatpeopleareeitherhappierorunhappierormoreorlesscerta
最新回复
(
0
)