判断二叉树是否为二叉排序树
课堂上跟老师小争论了一下，确实是自己写的判断算法有问题。一直闭门造车了，有时候适当的上网找一下资料会事半功倍的。恩……
二叉排序树很重要的一个概念是整个左（右）子树都小于（大）于根，符合这个条件的才是真正的二叉排序树。之前的算法一是证明根的值与左右节点的值符合关系，这是错误的。
具体一想就可以明白……
最简单的算法，就是中序遍历了。闲话少说，代码为证：

#include<iostream.h>

typedef struct node
{
int data;
struct node *left, *right;
}NODE,*BSTree;

//递归判断二叉树是否为排序树，leftbound，rightbound位左右界限，即最小最大值
bool judge(NODE *p, int leftbound, int rightbound)
{
if (p==NULL)
return true;

if (p-> data <= leftbound || p-> data >= rightbound)
return false;

if (!judge(p-> left,leftbound,p-> data))
return false;

if (!judge(p-> right, p-> data,rightbound))
return false;

return true;
}

//扩展的前序遍历结果建立二叉树
void PreOrderCreate(BSTree &T)
{
int data;
BSTree NewNode;

cin>>data;

if(data==0)
return;

NewNode=new NODE;
T=NewNode;
T->left=NULL;
T->right=NULL;

T->data=data;
PreOrderCreate(T->left);
PreOrderCreate(T->right);
}
//中序遍历二叉树
void InOrderTraverse(BSTree &T)
{
if(T==NULL)
return;

InOrderTraverse(T->left);

cout<<T->data<<" ";

InOrderTraverse(T->right);
}

void main()
{
BSTree BStree=NULL;

PreOrderCreate(BStree);
cout<<"The tree already built!"<<endl;

cout<<endl<<"Inorder sort:"<<endl;
InOrderTraverse(BStree);
cout<<endl;

if(judge(BStree,0,20))
cout<<"Yes! this is binary sort tree!"<<endl;
else
cout<<"No! this is not binary sort tree!"<<endl;

}