数据结构实验之二叉树一：树的同构

数据结构实验之二叉树一：树的同构

Time Limit: 1000ms   Memory limit: 65536K  有疑问？点这里^_^

题目描述

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。

图1

 

图2

现给定两棵树，请你判断它们是否是同构的。

输入

 输入数据包含多组，每组数据给出2棵二叉树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出”-”。给出的数据间用一个空格分隔。 注意：题目保证每个结点中存储的字母是不同的。

输出

 如果两棵树是同构的，输出“Yes”，否则输出“No”。

示例输入

8 A 1 2 B 3 4 C 5 - D - - E 6 - G 7 - F - - H - - 8 G - 4 B 7 6 F - - A 5 1 H - - C 0 - D - - E 2 -

示例输出

Yes

注意用c++的输入输出会导致超内存，最后无奈还是改成了c.

#include<stdio.h>

#include<string.h> #include<stdlib.h> struct TNode {     char data;     struct TNode *Lchild ,*Rchild;

} ;

struct node {     char data;     int a,b; } q[100]; //用于存储节点信息

TNode* Create(TNode *T,int N)

{     T=(TNode*)malloc(sizeof(TNode));     T->Lchild=NULL;     T->Rchild=NULL;     T->data=q[N].data;     if(q[N].a!=-1) //次子树不为空，从它递归继续建树         T->Lchild=Create(T->Lchild,q[N].a);     if(q[N].b!=-1)         T->Rchild=Create(T->Rchild,q[N].b);     return T; } int num=0; int v[100]; int Judge(TNode *T,TNode *t) {     if(!T&&!t) //两棵数均为空     {         return 1;     }     else if(T&&t)     {         if(T->data!=t->data) return 0; //两节点数据相同         else num++; //最后由num的值来判定正误         if((Judge(T->Lchild,t->Lchild) && Judge(T->Rchild, t->Rchild)) || (Judge(T->Rchild,t->Lchild) && Judge (T->Lchild, t->Rchild)))              return 1;   // 当1左子树=2左子树，1右=2右，或者1左子树=2右子树，1右=2左         else return 0;     }     else return 0; } int main() {     int n,m;     char s1[10],s2[10],s3[10];     while(~scanf("%d",&n))     {         memset(v,0,sizeof(v)); //数组清零         for(int i=0; i<n; i++)         {             scanf("%s%s%s",s1,s2,s3);             q[i].data=s1[0];             if(s2[0]=='-') q[i].a=-1;             else             {                 q[i].a=s2[0]-'0'; //类型转换                 v[q[i].a]=1;             }             if(s3[0]=='-') q[i].b=-1;             else             {                 q[i].b=s3[0]-'0';                 v[q[i].b]=1;             }         }         TNode *root;         if(n!=0)         {             int j;             for(j=0; j<n; j++){                 if(!v[j]) break; //确定初始的参数值             }            root=Create(root,j);         }         scanf("%d",&m);         memset(v,0,sizeof(v)); //数组清零         for(int i=0; i<m; i++)         {             scanf("%s%s%s",s1,s2,s3);             q[i].data=s1[0];             if(s2[0]=='-') q[i].a=-1;             else             {                 q[i].a=s2[0]-'0';                 v[q[i].a]=1;             }             if(s3[0]=='-') q[i].b=-1;             else             {                 q[i].b=s3[0]-'0';                 v[q[i].b]=1;             }         }         TNode *Root;         int j;         for(j=0; j<m; j++)             if(!v[j]) break;        Root=Create(Root,j);         num=0;         Judge(root,Root);         if(num==n)             printf("Yes\n");         else             printf("No\n");     }         memset(v,0,sizeof(v)); //数组清零     return 0; }