学步园

这是我首先想到的算法：

bool Judge(PBinTree pbt)
{
     PBinTreeNode   pLeft, pRight;
     bool    bLeft = false, bRight=false, bRootl=false, bRootr=false;

     if(pbt == NULL)
         return true;

     // 判断根节点
     pLeft = pbt->left;
     pRight = pbt->right;
     if(pLeft && pLeft->data <= pbt->data)
     {
          bRootl = true;
     }
     else
     {
           return false;
     }

     if(pRight && pRight->data >= pbt->data)
     {
          bRootr = true;
     }
     else
     {
          return false;
     }

     // 判断左右子树
     bLeft = Judge(pLeft);
     bRight = Judge(pRight);

     // 同时满足条件才叫二叉排序树
     return( bLeft && bRight && bRootl && bRootr);
}

但是不能处理

      400
  200     600
100 900 500 700

这样的情况

应该是这样的算法

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

int   judge(NODE   *p,   int   leftbound,   int   rightbound)   { 
    if   (p==NULL)   return   1; 
    if   (p-> data   <   leftbound   ||   p-> data   >   rightbound)   return   0;//不要等号 
    if   (!judge(p-> left,leftbound,p-> data))   return   0; 
    if   (!judge(p-> right,   p-> data,rightbound))   return   0; 
    return   1; 
}

 根值为value,   则左子树值都小于根,   右子树值大于根.   即左子树值   (-maxint,   value)   范围内,   右子树值在(value,   maxint)范围内. 

调用为 judge(root,-maxint,maxint)