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

题目描述

给定两棵树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

提示

测试数据对应图1

#include <stdio.h> #include<string.h> #include<stdlib.h> typedef char element; typedef int Bment; typedef struct BNode {    element data;    BNode *lchild,*rchild; }*BiTree; struct node//存储树的根和子树的元素； {     element root;     Bment l,r; }p[20]; Bment sign[11];//标记左右子树是否存在； BiTree CreateBiTree(BiTree &T,int n) //建立二叉树 {     T=new BNode;     T->data=p[n].root;     T->lchild=NULL;     T->rchild=NULL;     if(p[n].l!=-1)         T->lchild=CreateBiTree(T->lchild,p[n].l);     if(p[n].r!=-1)         T->rchild=CreateBiTree(T->rchild,p[n].r);      return T; } int CompareBiTree(BiTree &T,BiTree &T1)//比较是否同构 {     if(!T&&!T1)//空树同构         return 1;     else if(T&&T1)     {         if(T->data!=T1->data)             return 0;         else if((CompareBiTree(T->lchild,T1->lchild)&&CompareBiTree(T->rchild,T1->rchild))||(CompareBiTree(T->rchild,T1->lchild)&&CompareBiTree(T->lchild,T1->rchild)))//同构的条件；             return 1;         else             return 0;     }     else         return 0; } int main() {     int n,i;     char s[6],w[6],t[6];//存储根左右子树的值；     while(~scanf("%d",&n))     {         memset(sign,0,sizeof(sign));//清零函数；         for(i=0;i<n;i++)         {             scanf("%s%s%s",s,w,t);             p[i].root=s[0];             if(w[0]!='-')             {                 p[i].l=w[0]-'0';                 sign[p[i].l]=1;//判断子树是否存在的标记；             }             else                 p[i].l=-1;             if(t[0]!='-')             {                 p[i].r=t[0]-'0';                 sign[p[i].r]=1;             }             else                 p[i].r=-1;         }         for(i=0;i<n;i++)         {             if(!sign[i])                 break;         }         BiTree T;         T=CreateBiTree(T,i);//树的生成；         scanf("%d",&n);         memset(sign,0,sizeof(sign));//初始化；         for(i=0;i<n;i++)         {             scanf("%s%s%s",s,w,t);             p[i].root=s[0];             if(w[0]!='-')             {                 p[i].l=w[0]-'0';                 sign[p[i].l]=1;             }             else                 p[i].l=-1;             if(t[0]!='-')             {                 p[i].r=t[0]-'0';                 sign[p[i].r]=1;             }             else                 p[i].r=-1;         }         for(i=0;i<n;i++)             if(!sign[i])              break;         BiTree T1;         T1=CreateBiTree(T1,i);//生成树；         if(CompareBiTree(T,T1))//树是否同构；             printf("Yes\n");         else             printf("No\n");     }     return 0; }

#include <bits/stdc++.h> #define null -1 using namespace std; struct node {     char data;     int lchild;     int rchild; } T1[20], T2[20]; int creat(node T[], int N) {     int k=null;     char c[2], lc[2], rc[2];     int check[20];     memset(check, 0, sizeof(check));     if(N)     {         for(int i = 0; i < N; i++)         {             scanf("%s %s %s", c, lc,  rc);             T[i].data = c[0];             if(lc[0] != '-')             {                 T[i].lchild = lc[0]-'0';                 check[T[i].lchild] = 1;             }             else                 T[i].lchild = null;             if(rc[0] != '-')             {                 T[i].rchild = rc[0]-'0';                 check[T[i].rchild] = 1;             }             else                 T[i].rchild = null;         }         for(int j = 0; j < N; j++)         {             if(!check[j])             {                 k = j;                 break;             }         }     }     return k; } int judge(int R1, int R2) {     if(R1 == null&&R2 == null)         return 1;     if((R1 == null&&R2 != null)||(R1 != null&&R2 == null))         return 0;     if(T1[R1].data != T2[R2].data)         return 0;     if(T1[R1].lchild == null&&T2[R2].lchild == null)         return judge(T1[R1].rchild, T2[R2].rchild);     if(T1[R1].lchild != null             &&T2[R2].lchild != null             &&T1[T1[R1].lchild].data == T2[T2[R2].lchild].data)         return (judge(T1[R1].lchild, T2[R2].lchild)&&judge(T1[R1].rchild, T2[R2].rchild));     return (judge(T1[R1].lchild, T2[R2].rchild)&&judge(T1[R1].rchild, T2[R2].lchild)); } int main() {     int n, m;     int R1, R2;     while(~scanf("%d", &n))     {         R1 = creat(T1, n);         scanf("%d", &m);         R2 = creat(T2, m);         if(judge(R1, R2) == 1)             printf("Yes\n");         else             printf("No\n");     }     return 0; }