数据结构系列内容的学习目录 → \rightarrow →浙大版数据结构学习系列内容汇总。
题意理解： 给定两棵树T1和T2。如果T1可以通过若干次左右子结点互换就变成T2，则我们称两棵树是“同构”的。
现给定两棵树，如下图所示，请判断它们是否是同构的。
输入格式： 输入给出两棵二叉树的信息：
∘ \circ ∘ 先在一行中给出该树的结点数，随后n行；
∘ \circ ∘ 第 i 行对应编号第 i 个结点，给出该结点中存储的字母、其左子结点的编号、右子结点的编号；
∘ \circ ∘ 如果子结点为空，则在相应位置上给出“-”。
输入样例：
求解思路： 1. 二叉树表示
2. 建二叉树
3. 同构判别
二叉树表示： 结构数组表示二叉树，物理上的存储是数组，思想是一种链表思想，有链表的灵活性，但以数组形式存储，称其为静态链表。
二叉树用结构数组来表示，表示形式不是唯一的，也可以表示为如下图所示。
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1 //结点没有下标时，定义为-1，表示指向为空struct TreeNode
{ElementType Element;Tree Left; // 左子树的下标Tree Right; // 右子树的下标
}T1[MaxTree],T2[MaxTree];
程序框架搭建：
int main()
{建二叉树1建二叉树2判别是否同构并输出return 0 ;
需要设计的函数： 1. 读数据建二叉树
2. 二叉树同构判别
int main()
{Tree R1,R2;R1= BuildTree(T1);R2= BuildTree(T2);if(lsomorphic(R1,R2)) cout<< "是" << endl;else cout<< "否" << endl;return 0 ;
树的同构判断的完整实现代码如下所示。
#include<iostream>
using namespace std;
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1
struct TreeNode {ElementType data; // 存值 Tree left; // 左子树的下标 Tree right; // 右子树的下标
}T1[MaxTree], T2[MaxTree];// 返回根结点的第一种方法（根节点编号未出现在其他结点编号的后面，创建一个check数组来确定）
// 建二叉树，返回根结点
Tree BuildTree(struct TreeNode T[])
{int i;int n;int check[MaxTree]; //创建一个check数组来确定根节点，若在静态链表中未出现的下标则为根节点char left, right;Tree root = Null; //若n为0，返回Nullcin >> n;if (n) {for (i = 0; i < n; i++) {check[i] = 0;}for (i = 0; i < n; i++) {cin >> T[i].data >> left >> right;if (left != '-') {T[i].left = left - '0'; //若输入不为'-',那字符减去字符0转换为整型数值check[T[i].left] = 1; //把在静态链表中出现过的数值标记为1}else if (left == '-') {T[i].left = Null;}if (right != '-') {T[i].right = right - '0';check[T[i].right] = 1;}else if (right == '-') {T[i].right = Null;}}for (i = 0; i < n; i++) {if (!check[i]) {break;}}root = i;}return root;
}// 返回根结点的第二种方法 （根节点编号 = 行号和 - 左右结点编号和）
// 建二叉树，返回根结点
//Tree BuildTree(struct TreeNode T[])
//{
// int n; //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 Isomorphic(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)) //左儿子均为空{return Isomorphic(T1[R1].right, T2[R2].right);}if ((T1[R1].left != Null && T2[R2].left != Null) && (T1[T1[R1].left].data == T2[T2[R2].left].data)) // 左儿子不为空且值相等return Isomorphic(T1[R1].left, T2[R2].left) && Isomorphic(T1[R1].right, T2[R2].right);else // 左儿子不为空且值不等 或者 某一个左儿子为空（有可能左边和右边同构，右边和左边同构）return Isomorphic(T1[R1].right, T2[R2].left) && Isomorphic(T1[R1].left, T2[R2].right);
}
int main() {Tree R1, R2;R1 = BuildTree(T1);R2 = BuildTree(T2);cout << "是否同构？" << endl;if (Isomorphic(R1, R2))cout << "是" << endl;elsecout << "否" << endl;system("pause");return 0;
}
运行上述代码，进行测试。
- 测试1：输入题目中图a)的两棵树
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 -
代码运行的测试效果如下图所示（对应题目中的图a)）。
- 测试2：输入题目中图b)的两棵树
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
代码运行的测试效果如下图所示（对应题目中的图b)）。
