MOOC 树的同构
思路
- 二叉树表示
采用结构数组表示二叉树:静态链表
#define MaxTree 10 //结构数组的最大容量
#define ElemType char
#define Tree int
#define Null -1
//结构数组表示树，静态链表
struct TreeNode
{
ElemType Element; //节点的值，此处为字符型
Tree Left; //指向左子树的值
Tree Right; //指向右子树的值
}T1[MaxTree], T2[MaxTree]; //两个结构数组，分别存放相应的节点
- 建二叉树
返回根节点的值
//建二叉树
Tree BuildTree(struct TreeNode T[])
{
char cl, cr; //左右字符
int check[MaxTree]; //用于检测根节点
int Root = -1; //空树对应的是-1!!!!!!!!!!!
int i = 0;
int N; //节点个数
cin >> N;
if(N)
{
for(i=0; i<N; i++)
{
check[i] = 0;
}
for(i=0; i<N; i++)
{
cin >> T[i].Element >> cl >> cr;
if(cl != '-') //该节点的左子树不为空
{
T[i].Left = cl - '0'; //将字符转化为数字
check[T[i].Left] = 1; //该节点所对应的值已经被指向了，不可能为根节点了
}
else
{
T[i].Left = Null; //左子树为空对应的left为空值为-1
}
if(cr != '-')
{
T[i].Right = cr - '0';
check[T[i].Right] = 1;
}
else
{
T[i].Right = Null;
}
}
for(i=0; i<N; i++) //寻找根节点
{
if(!check[i])
break;
}
Root = i; //T[i]中没有任何节点left(cl)和right(cr)指向它，此种节点只有一个
}
return Root;
}
- 同构判别
多种情况，需要递归实现
int Isomorphic(Tree R1, Tree R2)
{
//两棵树均为空
if((R1==Null) && (R2==Null))
{
return 1;
}
//R1和R2中有一个为空
if(((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)))
{
return 0; //不同构
}
//R1和R2树的根节点的值都不相等
if(T1[R1].Element != T2[R2].Element)
{
return 0; //不同构
}
//R1和R2的左子树均为空，就只需比较其右子树是否同构
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].Element==T2[T2[R2].Left].Element)))
{
return (Isomorphic(T1[R1].Left, T2[R2].Left) &&
Isomorphic(T1[R1].Right, T2[R2].Right));
}
else
{
return(Isomorphic(T1[R1].Left, T2[R2].Right) &&
Isomorphic(T1[R1].Right, T2[R2].Left));
}
}
完整程序：
#include <iostream>
using namespace std;
#define MaxTree 10 //结构数组的最大容量
#define ElemType char
#define Tree int
#define Null -1
//结构数组表示树，静态链表
struct TreeNode
{
ElemType Element; //节点的值，此处为字符型
Tree Left; //指向左子树的值
Tree Right; //指向右子树的值
}T1[MaxTree], T2[MaxTree]; //两个结构数组，分别存放相应的节点
//建二叉树
Tree BuildTree(struct TreeNode T[])
{
char cl, cr; //左右字符
int check[MaxTree]; //用于检测根节点
int Root = -1; //空树对应的是-1!!!!!!!!!!!
int i = 0;
int N; //节点个数
cin >> N;
if(N)
{
for(i=0; i<N; i++)
{
check[i] = 0;
}
for(i=0; i<N; i++)
{
cin >> T[i].Element >> cl >> cr;
if(cl != '-') //该节点的左子树不为空
{
T[i].Left = cl - '0'; //将字符转化为数字
check[T[i].Left] = 1; //该节点所对应的值已经被指向了，不可能为根节点了
}
else
{
T[i].Left = Null; //左子树为空对应的left为空值为-1
}
if(cr != '-')
{
T[i].Right = cr - '0';
check[T[i].Right] = 1;
}
else
{
T[i].Right = Null;
}
}
for(i=0; i<N; i++) //寻找根节点
{
if(!check[i])
break;
}
Root = i; //T[i]中没有任何节点left(cl)和right(cr)指向它，此种节点只有一个
}
return Root;
}
int Isomorphic(Tree R1, Tree R2)
{
//两棵树均为空
if((R1==Null) && (R2==Null))
{
return 1;
}
//R1和R2中有一个为空
if(((R1==Null)&&(R2!=Null)) || ((R1!=Null)&&(R2==Null)))
{
return 0; //不同构
}
//R1和R2树的根节点的值都不相等
if(T1[R1].Element != T2[R2].Element)
{
return 0; //不同构
}
//R1和R2的左子树均为空，就只需比较其右子树是否同构
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].Element==T2[T2[R2].Left].Element)))
{
return (Isomorphic(T1[R1].Left, T2[R2].Left) &&
Isomorphic(T1[R1].Right, T2[R2].Right));
}
else
{
return(Isomorphic(T1[R1].Left, T2[R2].Right) &&
Isomorphic(T1[R1].Right, T2[R2].Left));
}
}
int main()
{
Tree R1, R2;
R1 = BuildTree(T1); //建二叉树，返回根节点的值
R2 = BuildTree(T2);
if(Isomorphic(R1, R2)) //判断是否同构
{
cout << "Yes" << endl;
}
else
{
cout << "No" << endl;
}
return 0;
}