问答题 已知二叉排序树以二叉链表做存储结构,试编写算法按从大到小的顺序输出二叉排序树的各结点。
【正确答案】算法由主函数和创建二叉排序树、在二叉排序树中插入结点、中序遍历二叉排序树、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方式中序遍历二叉排序树,数据序列由大到小*/
【答案解析】