编写一个判别给定二叉树是否为二叉排序树的算法，设二叉树的结点为（

二叉排序树的特点:
若根结点的左子树不空,则左子树上所有结点的值均小于它的根结点的值.
若根结点的右子树不空,则右子树上所有结点的值均大于它的根结点的值

如果左子树结点的值比根结点的大,或者右子树结点的值比根结点的小,
则不是二叉排序树.

测试结果1:
创建二叉树,输入先序遍历序列 (0是空结点):5 3 1 0 0 0 7 6 0 0 0

(非递归)判定: 是 二叉排序树
(递归法)判定: 是 二叉排序树

扩展二叉树示意图:
          5
      /      \
     3        7
    / \      / \
   1   0    6   0
  / \      / \ 
 0   0    0   0


测试结果2:
创建二叉树,输入先序遍历序列 (0是空结点):5 1 3 0 0 0 7 6 0 0 0

(非递归)判定: 不是 二叉排序树
(递归法)判定: 不是 二叉排序树

扩展二叉树示意图:
          5
      /      \
     1        7
    / \      / \
   3   0    6   0
  / \      / \ 
 0   0    0   0


//C语言测试程序
#include
#include
struct Bitree
{
    int data;
    struct Bitree *lChild;
    struct Bitree *rChild;
};

//用"先序遍历"算法创建二叉树
void CreateBiTree(struct Bitree **bt)
{
    int s;
    scanf("%d",&s); //输入数据
    if(s==0)        //0是空节点
    {
        *bt=NULL;
    }
    else
    {
        *bt=(struct Bitree *)malloc(sizeof(struct Bitree));
        (*bt)->data=s;
        CreateBiTree(&((*bt)->lChild));
        CreateBiTree(&((*bt)->rChild));
    }
}

//判别是否为二叉排序树(非递归)
int checkTreeByStack(struct Bitree *root)
{
    struct stack_node //栈的结构体
    {
        struct Bitree *bt;
    };
    struct stack_node stack[100]; //栈
    int top=0;                    //栈顶, 从top=1开始存放数据
    struct Bitree *p;             //当前二叉树结点

    if(root==NULL)
    {
        return 1;
    }

    p=root;
    top++;
    stack[top].bt=p;  //根结点入栈
    while(top != 0)
    {
        p=stack[top].bt;
        top--;
        if(p->rChild != NULL)
        {
            if(p->rChild->data < p->data)
            {
                return 0;  // 0:不是二叉排序树
            }
            top++;
            stack[top].bt=p->rChild;  //右分支入栈
        }
        if(p->lChild != NULL)
        {
            if(p->lChild->data > p->data)
            {
                return 0;  // 0:不是二叉排序树
            }
            top++;
            stack[top].bt=p->lChild;  //左分支入栈
        }
    }
    return 1; // 1:是二叉排序树
}

//判别是否为二叉排序树(递归法)
int IsSearchTree(struct Bitree *root)
{
    if(!root)
    {
        return 1;
    }
    else if(!(root->lChild) && !(root->rChild))   //左,右子树都没有
    {
        return 1;
    }
    else if((root->lChild) && !(root->rChild))    //只有左子树
    {
        if(root->lChild->data > root->data)
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return IsSearchTree(root->lChild);
        }
    }
    else if((root->rChild) && !(root->lChild))   //只有右子树
    {
        if(root->rChild->data < root->data)
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return IsSearchTree(root->rChild);
        }
    }
    else    //左,右子树都有
    {
        if((root->lChild->data > root->data) || (root->rChild->data < root->data))
        {
            return 0;  // 0:不是二叉排序树
        }
        else
        {
            return ( IsSearchTree(root->lChild) && IsSearchTree(root->rChild) );
        }
    }
}

int main()
{
    struct Bitree *root;
    int result;
    int retOther;

    printf("创建二叉树,输入先序遍历序列 (0是空结点): ");
    CreateBiTree(&root);

    //判别是否为二叉排序树(非递归)
    result = checkTreeByStack(root);
    printf("\n(非递归)判定: ");
    if(result==0)
    {
        printf("不是 二叉排序树\n");
    }
    else
    {
        printf("是 二叉排序树\n");
    }

    //判别是否为二叉排序树(递归法)
    retOther = IsSearchTree(root);
    printf("(递归法)判定: ");
    if(retOther == 0)
    {
        printf("不是 二叉排序树\n");
    }
    else
    {
        printf("是 二叉排序树\n");
    }

    printf("\n");
    return 0;
}

遥知不是雪，为有暗香来。没错，就是我

泠泠七弦上，静听松风寒。...