首页 > 代码库 > 二叉搜索树

二叉搜索树

2024-11-03 03:47:02   204人阅读

题目描述：
判断两序列是否为同一二叉搜索树序列
输入：
开始一个数n，(1<=n<=20) 表示有n个需要判断，n= 0 的时候输入结束。
接下去一行是一个序列，序列长度小于10，包含(0~9)的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。
接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。
输出：
如果序列相同则输出YES，否则输出NO
样例输入：
2 567432 543267 576342 0
样例输出：
YES NO
 
#include<iostream>
#include<stdio.h>
#include<string.h>
using namespace std;
 
struct node {
node *lchild;
node *rchild;
char c;
}tree[110];
 
int loc;
int temp;
char str1[25],str2[25];
node* creat(){
tree[loc].lchild = tree[loc].rchild = NULL;
loc++;
return &tree[loc-1];
}
 
 
void mid(node *t){
if (t->lchild){
mid(t->lchild);
}
str1[temp++]=t->c;
if (t->rchild){
mid(t->rchild);
}
}
 
void pre(node *t){
str2[temp++]=t->c;
if (t->lchild){
pre(t->lchild);
}
if (t->rchild){
pre(t->rchild);
}
}
node * insert (node *t, int x){
if (!t){
t=creat();
t->c=x;
return t;
}
else if (t->c>x){
t->lchild=insert(t->lchild,x);
}
else if (t->c<x){
t->rchild=insert(t->rchild,x);
}
return t;
}
 
int main(){
int n;
string s;
string ss;
node *t;
node *tt;
while (cin>>n && n!=0){
cin>>s;
loc=0;
char x;
t=NULL;
int ll=s.length();
for (int i=0;i<ll;i++){
x=s[i];
t=insert(t,x);
}
temp=0; pre(t);
temp=0; mid(t);
str1[ll]=0;
str2[ll]=0;
string ans1=str1;
string ans2=str2;
 
while (n--){
cin>>ss;
loc=0;
char x;
tt=NULL;
for (int i=0;i<s.length();i++){
x=ss[i];
tt=insert(tt,x);
}
temp=0; pre(t);
temp=0; mid(t);
if (ans1 == str1 && ans2 == str2){
cout<<"YES"<<endl;
}
else cout<<"NO"<<endl;
}
 
}
 
return 0;
}
 
跟二叉排序树那道题没什么区别

二叉搜索树


联系
我们