目录
前言
题意理解
求解思路
二叉树表示
程序框架搭建
读数据建二叉树
二叉树同构判别
前言
本篇主要讲有关二叉树的同构判断。
题意理解
给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则称这两棵树是“同构”的。
例如：
左图通过若干次左右孩子的交换变成了右图。这两颗树是同构的。
这两棵树不同构。左图树中C有一个孩子G，右图树中C有两个孩子D,E。
题目：输入两棵二叉树的信息，判断是否同构。
输入格式：输入给出两棵二叉树的信息：
- 先在一行中给出该树的结点数，随后N行
- 第i行对应编号第i个结点，给出该结点中存储的字母、其左孩子结点的编号、右孩子结点的编号。
- 如果孩子结点为空，则在相应位置上给出“-”。
例：
###输入样例：
| 8 | |||
| 0 | A | 1 | 2 |
| 1 | B | 3 | 4 |
| 2 | C | 5 | - |
| 3 | D | - | - |
| 4 | E | 6 | - |
| 5 | G | 7 | - |
| 6 | F | - | - |
| 7 | H | - | - |
第一个整数8，表示此二叉树有8个结点。
每个结点的信息主要有三个数据，黑色字体的第一列代表了这个结点本身的信息，这里用A,B,C……代表了每个结点的信息；后面的两个整数分别代表了左右儿子对应的编号。
红色字体的一列是对每个结点的编号。比如A的左儿子是B,对应B的编号为1；A的右儿子是C，对应C的编号为2。
再例如：
###输入样例：
| 8 | |||
| 0 | G | - | 4 |
| 1 | B | 7 | 6 |
| 2 | F | - | - |
| 3 | A | 5 | 1 |
| 4 | H | - | - |
| 5 | C | 0 | - |
| 6 | D | - | - |
| 7 | E | 2 | - |
注意：在这样的输入表示方法里面，不要求根结点作为第一个数据输入，可按任意的顺序来输入每个结点的信息。
但是有很关键的一点：根结点在哪里？
没有哪个结点会指向根结点，根结点所对应的编号不会被输入，则没有被输入的编号对应根结点。
求解思路
要想解决这道题有三个问题：
- 二叉树的表示
- 构建二叉树
- 同构判别
二叉树表示
二叉树表示二叉树的表示方法最常见的是用链表，但也可以用数组来表示。
数组表示二叉树最典型的形式就是将二叉树看作一个完全二叉树，缺少的结点在数组里面空出来。
这里用结构数组表示二叉树：静态链表
即基本的存储用数组，把需要的结点信息存储在数组里面，但是左右儿子用类似链表的方法来表示，有一个数据来指示左儿子在哪里、右儿子在哪里。物理上的存储是用数组，但是采用了链表的思想。
例：
| A | B | C | D | ||
| Left | -1 | 2 | -1 | -1 | |
| Right | 1 | 3 | -1 | -1 | |
| 0 | 1 | 2 | 3 | 4 |
数组里的每个分量是一个结构，即每一列是数组的一个分量。这个结构包含三个信息，一个是结点本身的信息，另外Left与Right是指向左儿子与右儿子位置的下标。-1表示指向空的结点。
根据这样的表示方法可以定义相应的数据结构。
#define MaxTree 10
#define ElementType char
#define Tree int
#define Null -1struct TreeNode
{ElementType Element;Tree Left;Tree Right;
}T1[MaxTree],T2[MaxTree];注意：Left与Right不是指针，所以当它指向空缺的时候，不是用NULL(0),而是用Null(-1)。因为0是数组的下标，为了区分传统空指针的NULL,这里定义了一个 Null 。
二叉树用结构数组进行的表示不是唯一的。也可这样表示：
| C | D | B | A | ||
| Left | -1 | -1 | 0 | -1 | |
| Right | -1 | -1 | 1 | 3 | |
| 0 | 1 | 2 | 3 | 4 |
程序框架搭建
int main()
{
建二叉树1
建二叉树2
判别是否同构并输出
return 0;
}
需要设计函数：
读数据建二叉树
二叉树同构判别
int main()
{Tree R1,R2;R1=BuildTree(T1);R2=BuildTree(T2);if(Isomorphic(R1,R2)) //判别两棵树是否同构printf("Yes\n");else printf("No\n");return 0;
}读数据建二叉树
Tree BuildTree(struct TreeNode T[])
{……scanf("%d\n",&N); //读入结点信息N个if(N){for(i=0;i<N;i++) check[i]=0; //数组check对应N个结点for(i=0;i<N;i++){scanf("%c %c %c\n",&T[i].Element,&cl,&cr);//依次读入每个结点信息if(cl!='-'){ //若左儿子不为空T[i].Left = cl-'0'; //将字符转换为数字check[T[i].Left] = 1; //Left指向的结点的check值设为1}else T[i].Left = Null;if(cr!='-'){ //若右儿子不为空T[i].Right = cr-'0';check[T[i].Right] = 1; //Right指向的结点的check值设为1}else T[i].Right = Null; }for(i=0;i<N;i++) if(!check[i]) break; //根结点check值为0Root = i; //找出根结点}return Root;
}二叉树同构判别
int Isomorphic(Tree R1,Tree R2)
{if((R1==Null)&&(R2==Null)) //两颗空树return 1;if( ((R1==Null) && (R2!=Null))||((R1!=Null)&&(R2==Null)) ) //其中一个是空树 return 0;if(T1[R1].Element != T2[R2].Element) //两颗树根不同 return 0;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 /*两个左子树的元素不相同，判断1树的左子树是否与2树的右子树相同，1树的右子树是否与2树的左子树相同 */return (Isomorphic(T1[R1].Left,T2[R2].Right) && Isomorphic(T1[R1].Right,T2[R2].Left));
}
