判断是否为二叉排序树

判断是否为二叉排序树

时间： 1ms        内存：128M

描述：

编写一个算法，判断给定二叉树是否为二叉排序树。

输入：

输入为该二叉树的层序遍历，输入0代表虚节点，输入-1结束。

编写一个算法，判断一个二叉树是否为二叉排序树。

二叉树节点的定义为

typedef struct node

{

    int data;

    struct node *lchild;

    struct node *rchild;

} Bitree;

 

需要编写的算法为bool IsSearchTree(Bitree *t)

若是，返回true,否则返回false。

输出：

输出为该二叉树是否为二叉排序树，若是，输出Yes，否则输出No。

示例输入：

50 34 89 23 42 63 90 -1

示例输出：

Yes

提示：

参考答案（内存最优[1776]）：

#include "stdio.h"
#include "iostream"
using namespace std;
#include "stdlib.h"
typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree()
{
    int num,i,n;
    Bitree *t,*s;
    t=NULL;
    num=0;
    scanf("%d",&n);
    while(n!=-1)
    {
        s=(Bitree *)malloc(sizeof(Bitree));
        s->data=n;
        s->lchild=s->rchild=NULL;
        num++;
        if(!t)t=s;
        B[num]=s;
        scanf("%d",&n);
    }
    for(i=1;i<=num;i++)
    {
        if(B[i]->data!=0)
        {
            if(2*i<=num && B[2*i]->data!=0)
                B[i]->lchild=B[2*i];
            if(2*i+1<=num && B[2*i+1]->data!=0)
                B[i]->rchild=B[2*i+1];
        }
    }
    return t;
}bool IsSearchTree(Bitree *t)  //递归遍历二叉树是否为二叉排序树
{
    if(!t)        //空二叉树情况
        return true;
    else if(!(t->lchild) && !(t->rchild))   //左右子树都无情况
        return true;
    else if((t->lchild) && !(t->rchild))    //只有左子树情况
    {
        if(t->lchild->data>t->data)
            return false;
        else
            return IsSearchTree(t->lchild);
    }
    else if((t->rchild) && !(t->lchild))   //只有右子树情况
    {
        if(t->rchild->data<t->data)
            return false;
        else
            return IsSearchTree(t->rchild);
    }
    else         //左右子树全有情况
    {
        if((t->lchild->data>t->data) || (t->rchild->data<t->data))
            return false;
        else
            return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );
    }
}
int main()
{
    Bitree *tree;
    tree=CreateBiTree();
    if(IsSearchTree(tree))printf("Yes\n");
    else printf("No\n");
    return 0;
}

参考答案（时间最优[0]）：

#include "stdio.h"
#include "iostream"
using namespace std;
#include "stdlib.h"
typedef struct node
{
    int data;
    struct node *lchild;
    struct node *rchild;
} Bitree;
Bitree *B[100];
Bitree *CreateBiTree()
{
    int num,i,n;
    Bitree *t,*s;
    t=NULL;
    num=0;
    scanf("%d",&n);
    while(n!=-1)
    {
        s=(Bitree *)malloc(sizeof(Bitree));
        s->data=n;
        s->lchild=s->rchild=NULL;
        num++;
        if(!t)t=s;
        B[num]=s;
        scanf("%d",&n);
    }
    for(i=1;i<=num;i++)
    {
        if(B[i]->data!=0)
        {
            if(2*i<=num && B[2*i]->data!=0)
                B[i]->lchild=B[2*i];
            if(2*i+1<=num && B[2*i+1]->data!=0)
                B[i]->rchild=B[2*i+1];
        }
    }
    return t;
}bool IsSearchTree(Bitree *t)  //递归遍历二叉树是否为二叉排序树
{
    if(!t)        //空二叉树情况
        return true;
    else if(!(t->lchild) && !(t->rchild))   //左右子树都无情况
        return true;
    else if((t->lchild) && !(t->rchild))    //只有左子树情况
    {
        if(t->lchild->data>t->data)
            return false;
        else
            return IsSearchTree(t->lchild);
    }
    else if((t->rchild) && !(t->lchild))   //只有右子树情况
    {
        if(t->rchild->data<t->data)
            return false;
        else
            return IsSearchTree(t->rchild);
    }
    else         //左右子树全有情况
    {
        if((t->lchild->data>t->data) || (t->rchild->data<t->data))
            return false;
        else
            return ( IsSearchTree(t->lchild) && IsSearchTree(t->rchild) );
    }
}
int main()
{
    Bitree *tree;
    tree=CreateBiTree();
    if(IsSearchTree(tree))printf("Yes\n");
    else printf("No\n");
    return 0;
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。