《数据结构》03-树1 树的同构

àì夳堔傛蜴生んèń 2022-05-15 15:00 204阅读 0赞

# 题目 #

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。  
![20181030101711752.jpg][]  
 图 一 图一 图一  
![20181030101745453.jpg][]  
 图 二 图二 图二  
现给定两棵树，请你判断它们是否是同构的。  
**输入格式:**  
输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。

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

**输入样例1（对应图1）：**

> 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 -

**输出样例1:**

> Yes

**输入样例2（对应图2）：**

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

**输出样例2:**

> No

# 分析 #

我们先想办法把根找到，找到根了整个树就出来了  
观察输入，输入是 `值 左儿子 右儿子`，根结点不会作为别的结点的儿子结点出现，即输入的 0 ~ N-1 个结点中，没有在左右儿子结点位置出现过的就是根结点，比如样例 1 的第一个树，0 未输入，所以 0 号结点是根结点  
考虑实现寻找根结点，设定 root 变量为初值，随着每次读取一行结点信息，root 累加行号，遇到左右儿子结点编号减取相应的数值即可，最终 root 的值就是该树的根结点

找到根结点，考虑如何判断是否同构，还是继续观察，所谓"同构"就是还是儿子结点还是儿子结点，不变，只是左儿子右儿子可能互换位置  
所以设定规则如下：

1.  如果结点都是空，返回 true
2.  如果只有某一个结点为空，返回 false
3.  如果结点值不同，返回 false
4.  如果左儿子都不为空且值相等，分别进入左右儿子结点
5.  否则调换左右儿子位置进入左右儿子结点

#include<iostream>
    #include<malloc.h>
    #define null -1
    using namespace std;
    struct TreeNode{
        
    	char data;    // 存值 
    	int left;   // 左子树的下标 
    	int right;  // 右子树的下标 
    }T1[10],T2[10];
    // 返回根结点 
    int create(struct TreeNode T[]){
        
    	int n;
    	int root = 0;
    	char left,right;
    	cin>>n;
    	if(!n)
    		return null;
    	for(int i=0;i<n;i++){
        
    		cin>>T[i].data>>left>>right;
    		if(left=='-')
    			T[i].left = null;
    		else{
        
    			T[i].left = left-'0';
    			root -= T[i].left;
    		}
    		if(right=='-')
    			T[i].right = null;
    		else{
        
    			T[i].right = right-'0';
    			root -= T[i].right;
    		}
    		// 0 累加到 n-1 
    		root +=i;	
    	}
    	return root;
    }
    // 判断是否同构
    bool judge(int R1,int R2){
        
    	if(R1 == null && R2 == null)   // 都为空 
    		return true;
    	if(R1 == null && R2 != null || R1 != null && R2 == null)    // 一个为空，一个不为空
    		return false;
    	if(T1[R1].data != T2[R2].data)   // 值不同
    		return false;
    	if((T1[R1].left != null && T2[R2].left != null )&&(T1[T1[R1].left].data == T2[T2[R2].left].data))  // 左儿子不为空且值相等
    		return judge(T1[R1].left,T2[R2].left) && judge(T1[R1].right,T2[R2].right);
    	else   // 左儿子不为空且值不等  或者 某一个左儿子为空 
    		return judge(T1[R1].right,T2[R2].left) && judge(T1[R1].left,T2[R2].right);
    } 
    int main(){
        
    	int R1,R2;
    	R1 = create(T1);
    	R2 = create(T2);
    	if(judge(R1,R2))
    		cout<<"Yes";
    	else
    		cout<<"No";
    	return 0;
    }

[20181030101711752.jpg]: /images/20220503/004dd9c9dd8245bc9db1dd6bede73627.png
[20181030101745453.jpg]: /images/20220503/15c00b77679f4d539c38686af58181e3.png