题目描述：
判断两序列是否为同一二叉搜索树序列
输入：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：
如果序列相同则输出YES，否则输出NO
样例输入：
2
567432
543267
576342
0
样例输出：
YES
NO
代码
#include <iostream>
#include <string.h>
using namespace std;
struct Node{
Node* left ;
Node* right ;
char data ;
Node():left(NULL),right(NULL),data('*'){}
};
//插入有序树
void insertSortTree(Node * root, char data){
Node * p = root ;
Node * q = new Node ;
q->data = data ;
while(1){
if(p->data>data&&p->left)p=p->left;
else if(p->data<data&&p->right)p=p->right;
else if(p->data>data){
p->left = q ;
return;
}
else if(p->data<data){
p->right = q ;
return;
}
}
}
//销毁有序树
void destroySortTree(Node * root){
Node * p = root ;
if(p->left!=NULL)destroySortTree(p->left);
if(p->right!=NULL)destroySortTree(p->right);
delete p ;
}
//创建有序树
Node * createSortTree(char * datas , int n){
if(n<=0)return NULL;
Node * root = new Node ;
root->data = datas[0];
Node * p = root ;
for(int i = 1 ; i < n ;i++){
insertSortTree(root,datas[i]);
}
return root ;
}
//用到的变量
char x1[11];int ct1 = 0;
char x2[11];int ct2 = 0;
//前根序遍历
void pre_lst(Node * root,char* x,int* index){
if(root)x[(*index)++] = root->data ;
if(root->left)pre_lst(root->left,x,index) ;
if(root->right)pre_lst(root->right,x,index) ;
}
//比较前根序列
bool cmp(int n){
for(int i = 0 ; i < n ; i++){
if(x1[i]!=x2[i])return false;
}
return true ;
}
int main()
{
int T ;
int n;
Node * root1 = NULL;
Node * root2 = NULL;
int index1 ,index2 ;
while(1){
cin>>T ;if(T==0)break;
cin>>x1 ;
ct1 = strlen(x1);
root1 = createSortTree(x1,ct1);
index1 = 0 ;
pre_lst(root1,x1,&index1) ;
for(int i = 0 ; i < T ; i++ ){
cin>>x2 ;
ct2 = strlen(x2);
root2 = createSortTree(x2,ct2);
index2 = 0 ;
pre_lst(root2,x2,&index2) ;
if(cmp(ct1)){
cout<<"YES"<<endl;
}else cout<<"NO"<<endl;
destroySortTree(root2) ;
}
destroySortTree(root1) ;
}
return 0;
}
作者提醒
解题思路：
1.构建二叉排序树。(题目中叫做二叉搜索树，其时是一样的，就是对于二叉树的任何一个结点的所有左孩子结点都小于父结点，但是父节点都小于右孩子结点，好吧，我既然还能记得住，看来，大脑锈的不是很厉害)
2.对构建的二叉排序树尽心前序遍历，得到前序序列。（前序就是 前根序，后序就是 后根序，中序就是 中根序）
3.比较前根序列，一样就输出YES ，不一样就输出 NO