是否二叉搜索树

  看到这题目时我的想法是用递归来判断 我想只要根大于左子树且小于右子树根结点就可以 但是，这个想法是错误的，         3      2        5  1    10  4     6 这个就不是二叉搜索树。所以怎么来判断一颗树是否为二叉搜索树呢。     我们要判断这个树根结点是不是大于左子树最大值，且小于右子树最小值 一直递归判断，   但是只有根结点的函数不够，所以我们要再写一个函数，有最大值，有最小值   如果一个结点是空或者是叶结点，那么就是真 然后，如果左右都是二叉搜索树，且我们根和最大最小符合条件，那么就可以返回真       ------------------------------------------------------------------------------------------------------------ update   在左右都为真时，如果左子树存在， 我们（*min)  = lmin  是做什么呢 我们看到上面Is_BST()中把&lmin传下去，也就是说我们把上一层的指针指向下一层，这样一层层递归下去，只要是二叉搜索树，且有左子树，就一直传递下去 一直到它没有左子树时，我们指向那个没有左子树的根节点的值 in order words 就是用最开始进去的指针一直往左走，直带没有左结点为止 （5）有左，（5）lmin指向(4)lmin (4)有左        （4）lmin指向（3）lmin .........多次后 （2）lmin 指向（1）根 如下最开时（5）*min指向（5）lmin 换种情况也一样 这时我们在判断第一层时（5）中的min 和max就是最大和最小了， 个人认为这好像一个链表emmmmmm   　　　　　　　　　　5 　　　　　　　　4 　　　　　　3 　　　　2 　　　1       习题4.3 是否二叉搜索树 (25 分)  

本题要求实现函数，判断给定二叉树是否二叉搜索树。

函数接口定义：

bool IsBST ( BinTree T );

 

其中BinTree结构定义如下：

typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

 

函数IsBST须判断给定的T是否二叉搜索树，即满足如下定义的二叉树：

定义：一个二叉搜索树是一棵二叉树，它可以为空。如果不为空，它将满足以下性质：

• 非空左子树的所有键值小于其根结点的键值。
• 非空右子树的所有键值大于其根结点的键值。
• 左、右子树都是二叉搜索树。

如果T是二叉搜索树，则函数返回true，否则返回false。

裁判测试程序样例：

#include 
#include 

typedef enum { false, true } bool;
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
    ElementType Data;
    BinTree Left;
    BinTree Right;
};

BinTree BuildTree(); /* 由裁判实现，细节不表 */
bool IsBST ( BinTree T );

int main()
{
    BinTree T;

    T = BuildTree();
    if ( IsBST(T) ) printf("Yes\n");
    else printf("No\n");

    return 0;
}
/* 你的代码将被嵌在这里 */

 

输入样例1：如下图

输出样例1：

Yes

  结尾无空行

输入样例2：如下图

输出样例2：

No

bool Is_BST(BinTree T,int *min,int *max)
{
int lmin,lmax,rmin,rmax,Left_flag,Right_flag;
//空树为二叉搜索
if(!T)
return true;
//只有一个根结点同上
if(!(T->Left)&&!(T->Right))
{
*min = *max = T->Data;
return true;
}
//判断一颗树是否为二叉搜索树，就是判断根结点的值是否大于左子树最大值，是否小于右子树最小值
//然后一直递归判断每一个结点是否是二叉搜索树，时间复杂度为O(NlogN)
Left_flag = Right_flag = false;

if((T->Left&&
Is_BST(T->Left,&lmin,&lmax)
&&T->Data>lmax)||!T->Left)
{
Left_flag = true;
}
if((T->Right&&
Is_BST(T->Right,&rmin,&rmax)
&&T->DataRight)
{
Right_flag = true;
}
if(Left_flag&&Right_flag)
{
if(T->Left)
(*min) = lmin;
else
(*min) = T->Data;
if(T->Right)
(*max) = rmax;
else
(*max) = T->Data;
return true;
}
else return false;
}

bool IsBST ( BinTree T )
{
int min=-1,max=-1;
return Is_BST(T,&min,&max);
}