【正确答案】算法由主函数和创建二叉排序树、在二叉排序树中插入结点、中序遍历二叉排序树、RNL方式中序遍历二叉排序树五个函数组成。其中RNL方式中序遍历二叉排序树算法类似于中序遍历二叉排序树算法,区别在于该算法在中序遍历二叉排序树时,先访问右子树,再访问左子树,以实现对二叉排序树按从大到小的顺序输出。
程序如下:
#include<stdio.h>
#define QUEUESIZE 20
typedef struct binode{ /*定义结点数据类型*/
int data;
struct binode*ichild,*rchild;
}BTNODE,*BINTREE;
BINTREE insertbst(BINTREE s,BINTREE t)/*在二叉排序树中插入结点*/
{
if(t==NULL)
t=s; /*如果二叉排序树为空树,则插入的结点为根结点*/
else
if(s->data<t->data) /*如果该结点的数据小于根结点的数据则插入左子树*/
t->lchild=insertbst(s,t->lchild);
else /*否则插入右子树*/
t->rchild=insertbst(s,t->rchild);
return t;
}
BINTREE createordbt() /*创建二叉排序树,输入0结束*/
{
BINTREE s,t;
int x;
t=NULL;
scanf("/%d",&x); /*输入结点数据*/
while(x!=0)
{
s=(BINTREE)malloc(sizeof(BTNODE));
s->data=x; /*为生成的结点赋值*/
s->ichild=NULL;
s->rchild=NULL;
t=insertbst(s,t); /*调用插入函数*/
scanf("/%d",&x);
}
return t;
}
void inorder(BINTREE t) /*中序遍历二叉排序树,结点输出序列为由小到大*/
{
if(t!=NULL)
{
inorder(t->ichild);
printf("/%d",t->data); /*打印结点数值*/
inorder(t->rchiid);
}
}
void rlinorder(BINTREE t) /*RNL方式中序遍历二叉排序树,结点输出序列为由大到小*/
{
if(t!=NULL)
{
rlinorder(t->rchild);
printf("/%d",t->data); /*打印结点数值*/
rlinorder(t->lchild);
{
}
main()
{
BINTREE root;
printf("\n");
root=createordbt(); /*调用创建二叉排序树函数*/
inorder(root); /*调用中序遍历二叉排序树函数*/
printf("\n");
rlinorder(root);r /*调用RNL方式中序遍历二叉排序树函数*/
}
程序执行输出情况为:
3 5 6 2 8 5 0(回车) /*创建二又排序树,输入整型数值的序列,以0结束*/
2 3 5 56 8 /*按LNR方式中序遍历二叉排序树,数据序列由小到大*/
8 6 5 5 3 2 /*按RNL方式中序遍历二叉排序树,数据序列由大到小*/
【答案解析】