7-3 树的同构（附做题逻辑！！！）思路：

78 阅读 0 评论 52 点赞

我是靠谱客的博主清爽悟空，最近开发中收集的这篇文章主要介绍7-3 树的同构（附做题逻辑！！！）思路：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

欢迎观看我的博客，如有问题交流，欢迎评论区留言，一定尽快回复！（大家可以去看我的专栏，是所有文章的目录）
文章字体风格：
红色文字表示：重难点
蓝色文字表示：思路以及想法

在这里插入图片描述

7-3 树的同构

思路：
- 1. 搭建树，并且找到根节点（用一个函数解决）
- 2. 判断同构的逻辑
- 3. 总代码

思路：

本题是给我们两棵二叉树的信息，让我们构建二叉树，然后根据比较这两棵二叉树的每个节点是否相等，并且左右孩子是否对应相等或者是一个节点的左右孩子互换后，是否对应相等。
那么，首先我们需要通过所给信息构建二叉树，如何构建呢？我们需要先定义一个节点

typedef struct TNode {
	char data;
	int lchild, rchild;
}Tree;

1. 搭建树，并且找到根节点（用一个函数解决）

之后我们定义一个节点数组表示树。
之后我们就遍历所给信息，搭建树，就好了。
关键来了：我们怎么知道哪个代表根节点（由于题中所给信息，节点是随机排序的，我们只能通过哪个节点是没有被当做孩子的，那么这个节点就是根节点，这样找到根节点，我们才能正常遍历一棵二叉树）所以我们再定义一个数组，用于标记，当哪个节点被作为孩子节点了，那么我们就标记它为 1，最后剩下的一个数组位置对应的是0，这个数组角标，也就是根节点序号了。以上过程，我们可以作为一个函数（初始化二叉树函数）这样的话，我们就可以简化代码，并且返回值直接是二叉树的根节点

int InitTree(Tree *T) {
	int N,flag[10]={0};
	cin >> N;
	if (N == 0)
		return null;
	for (int i = 0; i < N; i++) {
		char l,r;
		cin >> T[i].data>>l>>r;
		if (l == '-')
			T[i].lchild = null;
		else {
			T[i].lchild = (int)(l - '0');
			flag[T[i].lchild] = 1;
		}
		if (r == '-')
			T[i].rchild = null;
		else {
			T[i].rchild = (int)(r - '0');
			flag[T[i].rchild] = 1;
		}
	}
	for (int i = 0; i < 10; i++)
		if (!flag[i])
			return i;
	return null;
}

2. 判断同构的逻辑

之后，我们得到了二叉树的根节点，
最最重点来了：如何判断两棵树是否同构呢？
我们通过递归，每次比较一个节点：

如果当前两个树的相同位置的节点，不相等，那么我们就直接返回false，但是如果两个树的相同位置的节点，相等，那么我们就直接返回true吗？不能直接返回true的，因为此节点下面的节点还有可能不相等，但是我们直接就返回true，就不能继续遍历下面的节点了。
所以只有当我们全部遍历完，没有返回false，那么才返回true。那什么时候是遍历完了呢，就是当两个节点同时为空；或者是两个节点相等并且没有孩子节点了，才能返回true
当判断条件都完成后，那么就继续遍历，怎么进行遍历呢？
就是 return + 递归

代码如下：

bool IsEmpty(Tree T) {
	if (T.lchild == null && T.rchild == null)
		return true;
	return false;
}
 
bool IsSame(Tree T1[],int i, Tree T2[], int j) {
	if ((i == -1 && j != -1) || (i != -1 && j == -1))
		return false;
	if (i == -1 && j == -1)
			return true;	
	if (IsEmpty(T1[i]) && IsEmpty(T2[j]) && T1[i].data == T2[i].data)
		return true;
	if (T1[i].data == T2[j].data)
		return ((IsSame(T1, T1[i].lchild, T2, T2[j].lchild) && IsSame(T1, T1[i].rchild, T2, T2[j].rchild)) || (IsSame(T1, T1[i].rchild, T2, T2[j].lchild) && IsSame(T1, T1[i].lchild, T2, T2[j].rchild)));
	return false;
}

3. 总代码

#include<iostream>
 
using namespace std;
 
const int null = -1;
 
typedef struct TNode {
	char data;
	int lchild, rchild;
}Tree;
 
int InitTree(Tree *T) {
	int N,flag[10]={0};
	cin >> N;
	if (N == 0)
		return null;
	for (int i = 0; i < N; i++) {
		char l,r;
		cin >> T[i].data>>l>>r;
		if (l == '-')
			T[i].lchild = null;
		else {
			T[i].lchild = (int)(l - '0');
			flag[T[i].lchild] = 1;
		}
		if (r == '-')
			T[i].rchild = null;
		else {
			T[i].rchild = (int)(r - '0');
			flag[T[i].rchild] = 1;
		}
	}
	for (int i = 0; i < 10; i++)
		if (!flag[i])
			return i;
	return null;
}
 
bool IsEmpty(Tree T) {
	if (T.lchild == null && T.rchild == null)
		return true;
	return false;
}
 
bool IsSame(Tree T1[],int i, Tree T2[], int j) {
	if ((i == -1 && j != -1) || (i != -1 && j == -1))
		return false;
	if (i == -1 && j == -1)
			return true;	
	if (IsEmpty(T1[i]) && IsEmpty(T2[j]) && T1[i].data == T2[i].data)
		return true;
	if (T1[i].data == T2[j].data)
		return ((IsSame(T1, T1[i].lchild, T2, T2[j].lchild) && IsSame(T1, T1[i].rchild, T2, T2[j].rchild)) || (IsSame(T1, T1[i].rchild, T2, T2[j].lchild) && IsSame(T1, T1[i].lchild, T2, T2[j].rchild)));
	return false;
}
 
int main() {
	Tree T1[10], T2[10];
	int Root1, Root2;
	Root1=InitTree(T1);
	Root2=InitTree(T2);
	if (IsSame(T1, Root1, T2, Root2))
		cout << "Yes";
	else 
		cout << "No";
	return 0;
}