http://acm.hdu.edu.cn/showproblem.php?pid=3791用静态链表做,用结构体数组来存储二叉树,然后比较它们是否相同即可。两种静态链表可以做。
代码如下:
//方法一:
#include <iostream>
#include <string>
using namespace std;
struct d
{
char data;
int left,right;
}bitree[1024],temp[1024];
bool eq(struct d a[],struct d b[])
{
int i;
for(i=1;i<1024 && a[i].data==b[i].data;i++);
if(i==1024)
return true;
return false;
}
int main()
{
int t,lenth,i,j;
string str;
while(cin>>t,t)
{
cin>>str;
for(i=1;i<1024;i++)
bitree[i].data=-1;
lenth=str.length ();
bitree[1].data =str[0];
for(i=1;i<lenth;i++)
{
j=1;
while(bitree[j].data!=-1)
{
if(str[i]>bitree[j].data)
j=2*j+1;
else
j=2*j;
}
bitree[j].data=str[i];
}
while(t--)
{
for(i=1;i<1024;i++)
temp[i].data=-1;
cin>>str;
lenth=str.length ();
temp[1].data =str[0];
for(i=1;i<lenth;i++)
{
j=1;
while(temp[j].data!=-1)
{
if(str[i]>temp[j].data)
j=2*j+1;
else
j=2*j;
}
temp[j].data=str[i];
}
if(eq(bitree,temp))
cout<<"YES\n";
else
cout<<"NO\n";
}
}
return 0;
}
//方法二
#include <iostream>
#include <string>
using namespace std;
struct d
{
int left,right;
}bitree[10],temp[10];
bool eq(struct d a[],struct d b[])
{
int i;
for(i=0;i<10&& a[i].left==b[i].left && a[i].right ==b[i].right ;i++);
if(i==10)
return true;
return false;
}
void insert(int node,int root,struct d a[])
{
if(node>root)
{
if(a[root].right ==-1)
a[root].right =node;
else
insert(node,a[root].right ,a);
}
else
{
if(a[root].left ==-1)
a[root].left =node;
else
insert(node,a[root].left ,a);
}
}
int main()
{
int t,lenth,i,j,root,tempr;
string str;
while(cin>>t,t)
{
cin>>str;
for(i=0;i<10;i++)
bitree[i].left=bitree[i].right =-1;
lenth=str.length ();
root =str[0]-'0';
for(i=1;i<lenth;i++)
{
insert(str[i]-'0',root,bitree);
}
while(t--)
{
cin>>str;
for(i=0;i<10;i++)
temp[i].left=temp[i].right =-1;
lenth=str.length ();
tempr =str[0]-'0';
for(i=1;i<lenth;i++)
{
insert(str[i]-'0',tempr,temp);
}
if(eq(bitree,temp) && root==tempr)
cout<<"YES\n";
else
cout<<"NO\n";
}
}
return 0;
}
posted on 2011-04-04 19:13
大大木马 阅读(578)
评论(0) 编辑 收藏 引用