判断一棵二叉树是否为二叉排序树

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； （3）左、右子树也分别为二叉排序树；

#include<stdio.h>
#include<stdlib.h>
#define MIN  -256;
typedef int TElemType;
typedef struct BiTNode
{
    TElemType data;
    struct BiTNode *lchild,*rchild; //左右孩子指针 
}BiTNode,*BiTree;

//判断一棵二叉树是不是二叉排序树  
//思路：二叉排序树的特点是，若左子树非空，则左子树上结点的值均小于根结点的值；  
//若右子树非空，则右子树上结点的值均大于根结点的值。所以根据这一特点，可以看出  
//二叉排序树的中序遍历是一个递增序列。  

int prev = MIN;
int flag = true;
bool InOrderTraverse(BiTree T)
{

    if(T->lchild != NULL && flag)
    {
        InOrderTraverse(T->lchild);
    }
    if(T->data<prev)
    {
        flag = false;
    }
    prev = T->data;
    if(T->rchild != NULL && flag){
        InOrderTraverse(T->rchild);
    }
    return flag;
}

void CreateBiTree(BiTree * T)   //二叉树的建立
{
    TElemType data;
    scanf("%d",&data);
    if(data==-1)
    {
        *T=NULL;
    }
    else
    {
        *T=(BiTree)malloc(sizeof(BiTNode));
    }
    if(!*T)
    {
        return ;
    }
    else
    {
        (*T)->data=data;
        CreateBiTree(&(*T)->lchild);    //构造左子树
        CreateBiTree(&(*T)->rchild);    //构造右子树
    }   
}

//***********测试代码************  
//           10               
//         /                      
//        7              
//       /                 
//      4  8  
//            
//           9  

//***********测试代码************  
//           10               
//         /                      
//        1              
//       /                 
//      4  8  
//            
//           9  
int main()
{
    BiTree root;
    printf("请输入数据:
");
    CreateBiTree(&root);
    bool flag = InOrderTraverse(root);
    if(flag)
    {
        printf("
该二叉树是排序二叉树
");
    }else
    {
        printf("
该二叉树不是排序二叉树
");
    }
    return 0;
}