資料結構上機——判斷二叉排序樹

//判斷二叉排序樹的程式代碼
#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++;
    }
  }
}