问题：
判断两序列是否为同一二叉搜索树序列
输入：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：
如果序列相同则输出YES，否则输出NO
例如：
6
45021
12045
54120
45021
45012
21054
50412
0
输出：
NO
NO
YES
NO
NO
NO
分析：
二叉搜索树，就是一个二叉排序树，中序遍历，是从小到大排序的
首先，建立初始二叉排序树
接着，建立n颗要比较的二叉排序树，依次和初始二叉排序树进行比较
最后，比较两个二叉树是否一样，如果两个二叉树都是空，就返回true，如果两个二叉树都不为空，并且两个数据都相同，就比较两个树的左子树和右子树是不是都一样，进行递归，否则返回false；
比较函数：
bool is_same_tree(Node *&a,Node *&b){
if(a==NULL&&b==NULL){
return true;
}else if(a!=NULL&&b!=NULL&&a->data==b->data){
return is_same_tree(a->lchild,b->lchild)&&is_same_tree(a->rchild,b->rchild);
}
return false;
}
代码：
#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct Node{
int data;
struct Node *lchild;
struct Node *rchild;
};
Node* create_tree(Node *&t,int m){
if(t==NULL){
t=new Node;
t->data=m;
t->lchild=NULL;
t->rchild=NULL;
}else if(m>t->data){
create_tree(t->rchild,m);
}else if(m<t->data){
create_tree(t->lchild,m);
}
return t;
}
void pre(Node *&t){
if(t){
cout<<t->data<<" ";
pre(t->lchild);
pre(t->rchild);
}
}
void zhongxv(Node *&t){
if(t){
zhongxv(t->lchild);
cout<<t->data<<" ";
zhongxv(t->rchild);
}
}
bool is_same_tree(Node *&a,Node *&b){
if(a==NULL&&b==NULL){
return true;
}else if(a!=NULL&&b!=NULL&&a->data==b->data){
return is_same_tree(a->lchild,b->lchild)&&is_same_tree(a->rchild,b->rchild);
}
return false;
}
int main()
{
int n;
while(cin>>n){
if(n==0){
break;
}
getchar();
Node *t;
t=NULL;
//建立一颗二叉排序树
while(1){
char a=getchar();
if(a=='\n'){
break;
}
char b[1]={a};
int c;
sscanf(b,"%d",&c);
create_tree(t,c);
}
//中序遍历,测试是否建立成功，二叉树中序遍历，是从小到大排序的
//zhongxv(t);
//建立n颗二叉树，判断是否是同一个二叉树
while(n--){
Node *t1;
t1=NULL;
//建立一颗二叉排序树
while(1){
char a1=getchar();
if(a1=='\n'){
break;
}
char b1[1]={a1};
int c1;
sscanf(b1,"%d",&c1);
create_tree(t1,c1);
}
bool b=is_same_tree(t1,t);
if(b){
cout<<"YES"<<endl;
}else{
cout<<"NO"<<endl;
}
}
}
return 0;
}
结果：
