数据结构上机——判断二叉排序树

//判断二叉排序树的程序代码
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
//二叉链表的结构类型定义
const int maxsize=1024;
typedef int keytype;
typedef struct node
{
  keytype key;
  struct node *lchild,*rchild;
}bitree;

bitree*creattree();
void preorder(bitree*);
int inorder(bitree*);

int main()
{
  bitree*pb;
  pb=creattree();
  preorder(pb);
  printf("\n");
  if(inorder(pb)==1)printf("是二叉排序树！\n");
  else printf("不是二叉排序树！\n");
}

//二叉树的建立
bitree*creattree()
{
  keytype x;
  bitree*Q[maxsize];
  int front,rear;
  bitree*root,*s;
  root=NULL;
  front=1;rear=0;
  printf("按层次输入二叉排序树的整型结点数据，0表示虚结点，-1表示结束：\n");
  scanf("%d",&x);//输入0表示虚结点，-1表示结束
  while(x!=-1)
  {
    s=NULL;
    if(x!=0)
    {
      s=(bitree*)malloc(sizeof(bitree));
      s->key=x;
      s->lchild=NULL;
      s->rchild=NULL;
    }
    rear++;
    Q[rear]=s;
    if(rear==1)root=s;
    else
    {
      if(s&&Q[front])
        if(rear%2==0)Q[front]->lchild=s;
        else Q[front]->rchild=s;
      if(rear%2==1)front++;
    }
    scanf("%d",&x);
  }
  return root;
}

//二叉树的输出
void preorder(bitree*p)
{
  if(p!=NULL)
  {
    printf("%d",p->key);
    if(p->lchild!=NULL||p->rchild!=NULL)
    {
      printf("(");
      preorder(p->lchild);
      if(p->rchild!=NULL) printf(",");
      preorder(p->rchild);
      printf(")");
    }
  }
}

//添加判断二叉排序树算法
int inorder(bitree*p)
{
  //是二叉排序树返回1，不是返回0 
  int l,r;
  int pre[20]={0};
  int i=0;
  pre[i]=p->key;
  if(p==NULL)return 1;//由于虚结点存在，分情况讨论 
  else if(p->lchild==NULL&&p->rchild==NULL)return 1; //叶子结点 
  else if(p->rchild==NULL&&p->lchild!=NULL) //只有左子树 
  {
    if((p->lchild->key>p->key)||(p->lchild->key<pre[0]))return 0;  
    else{
    return inorder(p->lchild);
    i++;
    }
  }
  else if(p->lchild==NULL&&p->rchild!=NULL)//只有右字树 
  {
    if((p->rchild->key<p->key)||(p->rchild->key>pre[0]))return 0;
    else{
    return inorder(p->rchild);
    i++;
    }
  }
  else//左右子树均存在 
  {
    if((p->lchild->key>p->key)||(p->lchild->key<pre[0])||(p->rchild->key<p->key)||(p->rchild->key>pre[0]))return 0;
    else{
    return inorder(p->lchild)&&inorder(p->rchild);
    i++;
    }
  }
}

此题难度较大
有两个主要问题
1、虚结点的存在需要导致分类
2、一种特殊情况：p的左孩子的右孩子大于p，我的做法是通过一个数组来记录祖先的数值，应该可以有更好的方法。
附：验证数据 5 3 7 2 4 4 8-1