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

妖狐艹你老母 2022-07-19 05:16 135阅读 0赞

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

####  ####

#### Time Limit: 1000MS Memory limit: 65536K ####

## 题目描述 ##

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

图1

![3340_2.png][]

图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<malloc.h> #include<stdlib.h> //定义树 struct tree { char data; struct tree *lc,*rc; }; //定义结构体存放数据 struct node { char letter;//字母 int lnum; int rnum; }; struct node h1[1000],h2[1000]; //创建树 struct tree *creat(int i) { struct tree *root; root=(struct tree*)malloc(sizeof(struct tree)); root->lc = root->rc = NULL;//初始时把左右孩子置为空 root->data=h1[i].letter; if(h1[i].lnum!=-1) {root->lc=creat(h1[i].lnum);} if(h1[i].rnum!=-1) {root->rc=creat(h1[i].rnum);} return root; }; //数组输入 struct tree *in(int len) { int i; char a[100],b[100],c[100]; struct tree *root,*root2; int f[20]; memset(f,0,sizeof(f));//将数组初始化为0 for(i=0;i<len;i++) { scanf("%s %s %s",&a,&b,&c); h1[i].letter=a[0]; if(b[0]=='-') { h1[i].lnum=-1; } else { h1[i].lnum=b[0]-'0'; f[h1[i].lnum]=1; } if(c[0]=='-') { h1[i].rnum=-1; } else { h1[i].rnum=c[0]-'0'; f[h1[i].rnum]=1; } } /*for(i=0;i<len;i++) { if(f[i]!=1) { break; } }*/ for(i = 0;i < len;i++) if(f[i]==0) break; root = creat(i); return root; } //前序遍历 void fristput(struct tree *root) { if(root!=NULL) { printf("%c",root->data); fristput(root->lc); fristput(root->rc); } } //判断是否为同构 int judge(struct tree *root1,struct tree *root2) { if(root1==NULL&&root2==NULL) { return 1; } else if(root1!=NULL&&root2!=NULL) { if(root1->data==root2->data) { if((judge(root1->lc,root2->lc)&&judge(root1->rc,root2->rc))||(judge(root1->lc,root2->rc)&&judge(root1->rc,root2->lc))) { return 1; } } } return 0; } int main() { int n,m; while(~scanf("%d",&n)) { struct tree *root1,*root2; root1=in(n); //fristput(root1); // printf("\n"); scanf("%d",&m); root2=in(m); //fristput(root2); // printf("\n"); int t; t=judge(root1,root2); if(t==1) { printf("Yes\n"); } else { printf("No\n"); } } return 0; }`         ##

[3340_1.png]: /images/20220718/a32b2cc4835845c789a1588fe7e07f2c.png
[3340_2.png]: /images/20220718/f9661ad1a61344c3b6594e8ed1e858e4.png