# 判断是否为二叉排序树

typedef struct node
{
int data;
struct node *lchild;
struct node *rchild;
} Bitree;

``50 34 89 23 42 63 90 -1``

``Yes``

``````
#include "stdio.h"
#include "iostream"
using namespace std;
#include "stdlib.h"
typedef struct node
{
int data;
struct node *lchild;
struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree()
{
int num,i,n;
Bitree *t,*s;
t=NULL;
num=0;
scanf("%d",&n);
while(n!=-1)
{
s=(Bitree *)malloc(sizeof(Bitree));
s->data=n;
s->lchild=s->rchild=NULL;
num++;
if(!t)t=s;
B[num]=s;
scanf("%d",&n);
}
for(i=1;i<=num;i++)
{
if(B[i]->data!=0)
{
if(2*i<=num && B[2*i]->data!=0)
B[i]->lchild=B[2*i];
if(2*i+1<=num && B[2*i+1]->data!=0)
B[i]->rchild=B[2*i+1];
}
}
return t;
}bool IsSearchTree(Bitree *t)  //递归遍历二叉树是否为二叉排序树
{
if(!t)        //空二叉树情况
return true;
else if(!(t->lchild) && !(t->rchild))   //左右子树都无情况
return true;
else if((t->lchild) && !(t->rchild))    //只有左子树情况
{
if(t->lchild->data>t->data)
return false;
else
return IsSearchTree(t->lchild);
}
else if((t->rchild) && !(t->lchild))   //只有右子树情况
{
if(t->rchild->data<t->data)
return false;
else
return IsSearchTree(t->rchild);
}
else         //左右子树全有情况
{
if((t->lchild->data>t->data) || (t->rchild->data<t->data))
return false;
else
return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );
}
}
int main()
{
Bitree *tree;
tree=CreateBiTree();
if(IsSearchTree(tree))printf("Yes\n");
else printf("No\n");
return 0;
}
``````

``````
#include "stdio.h"
#include "iostream"
using namespace std;
#include "stdlib.h"
typedef struct node
{
int data;
struct node *lchild;
struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree()
{
int num,i,n;
Bitree *t,*s;
t=NULL;
num=0;
scanf("%d",&n);
while(n!=-1)
{
s=(Bitree *)malloc(sizeof(Bitree));
s->data=n;
s->lchild=s->rchild=NULL;
num++;
if(!t)t=s;
B[num]=s;
scanf("%d",&n);
}
for(i=1;i<=num;i++)
{
if(B[i]->data!=0)
{
if(2*i<=num && B[2*i]->data!=0)
B[i]->lchild=B[2*i];
if(2*i+1<=num && B[2*i+1]->data!=0)
B[i]->rchild=B[2*i+1];
}
}
return t;
}bool IsSearchTree(Bitree *t)  //递归遍历二叉树是否为二叉排序树
{
if(!t)        //空二叉树情况
return true;
else if(!(t->lchild) && !(t->rchild))   //左右子树都无情况
return true;
else if((t->lchild) && !(t->rchild))    //只有左子树情况
{
if(t->lchild->data>t->data)
return false;
else
return IsSearchTree(t->lchild);
}
else if((t->rchild) && !(t->lchild))   //只有右子树情况
{
if(t->rchild->data<t->data)
return false;
else
return IsSearchTree(t->rchild);
}
else         //左右子树全有情况
{
if((t->lchild->data>t->data) || (t->rchild->data<t->data))
return false;
else
return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );
}
}
int main()
{
Bitree *tree;
tree=CreateBiTree();
if(IsSearchTree(tree))printf("Yes\n");
else printf("No\n");
return 0;
}
``````