【无标题】

04-树4 是否同一棵二叉搜索树

分数 25

作者 陈越

单位 浙江大学

给定一个插入序列就可以唯一确定一棵二叉搜索树。然而，一棵给定的二叉搜索树却可以由多种不同的插入序列得到。例如分别按照序列{2, 1, 3}和{2, 3, 1}插入初始为空的二叉搜索树，都得到一样的结果。于是对于输入的各种插入序列，你需要判断它们是否能生成一样的二叉搜索树。

输入格式:

输入包含若干组测试数据。每组数据的第1行给出两个正整数N (≤10)和L，分别是每个序列插入元素的个数和需要检查的序列个数。第2行给出N个以空格分隔的正整数，作为初始插入序列。随后L行，每行给出N个插入的元素，属于L个需要检查的序列。

简单起见，我们保证每个插入序列都是1到N的一个排列。当读到N为0时，标志输入结束，这组数据不要处理。

输出格式:

对每一组需要检查的序列，如果其生成的二叉搜索树跟对应的初始序列生成的一样，输出“Yes”，否则输出“No”。

输入样例:

4 2
3 1 4 2
3 4 1 2
3 2 4 1
2 1
2 1
1 2
0

输出样例:

Yes
No
No

代码如下：

#include <iostream>

using namespace std;

typedef struct TNode* BinTree;
struct TNode
{
    int data;
    BinTree lchild,rchild;
};

BinTree NewNode(int val);   //新建一个结点
BinTree Create(int *a,int n); //创建一棵树
void Insert(BinTree &BST,int val); //在树中插入一个值
bool Is_same(BinTree p,BinTree q); //判断两棵树是否相等，是同一棵二叉搜索树

int main()
{
    int n,l;
    while(scanf("%d",&n),n!=0)
    {
        scanf("%d",&l);
        int a[n],b[n];
        for(int i=0;i<n;++i)
            scanf("%d",&a[i]);
        BinTree p=Create(a,n);
        while(l--)
        {
            for(int i=0;i<n;++i)
                scanf("%d",&b[i]);
            BinTree q=Create(b,n);
            if(Is_same(p,q))
                printf("Yes\n");
            else
                printf("No\n");
        }
    }
    return 0;
}

BinTree NewNode(int val)
{
    BinTree node=new TNode;
    node->data=val;
    node->lchild=node->rchild=NULL;
    return node;
}

BinTree Create(int *a,int n)
{
    BinTree BST=NULL;
    for(int i=0;i<n;++i)
        Insert(BST,a[i]);
    return BST;
}

void Insert(BinTree &BST,int val)
{
    if(BST==NULL)
    {
        BST=NewNode(val);
        return;
    }

    if(val < BST->data)
        Insert(BST->lchild,val);
    else
        Insert(BST->rchild,val);
}

bool Is_same(BinTree p,BinTree q)
{
    if(p==NULL&&q==NULL) //如果两棵都是空树
        return true;
    else if(p==NULL || q==NULL) //如果有一棵是空树
        return false;
    else if(p->data!=q->data) //如果两棵树的根节点的数据域不相等
        return false;
    else return Is_same(p->lchild,q->lchild) && Is_same(p->rchild,q->rchild); //进行左右子树比较
}