写在最前面
按照课程讲解的思路来写, 逻辑关系能够理解清楚了, 但是实际运行起来实在是有问题, 虽然在 PTA 上能够通过. 但是我自己看不出问题来, 并且, 看了一遍又一遍仍然看不出来!(可能自己太笨..) 这就说明有着很严肃的问题!
所以, 与其这样纠结, 不如按照自己理解的思路来写一遍.
补充一下题目要求
给定两棵树 T1 和 T2. 如果 T1 可以通过若干次左右孩子互换就变成 T2, 则我们称两棵树是 "同构" 的. 例如图 1 给出的两棵树就是同构的, 因为我们把其中一棵树的结点 A,B,G 的左右孩子互换后, 就得到另外一棵树. 而图 2 就不是同构的.
现给定两棵树, 请你判断它们是否是同构的.
输入格式:
输入给出 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
课程讲解的思路
- #include <cstdio>
- #include <cstdlib>
- // 按题目的意思, 存储树的是静态链表
- // 即建一个结构, 里面三个变量 char 型结点字母, int 型的左右孩子的位置
- #define MaxTree 10 // 题目的意思: 最多十个结点
- #define ElementType char
- #define Tree int
- #define Null -1
- Tree BuildTree(struct TreeNode T[]);
- int Isomorphic(Tree R1, Tree R2);
- // 建一个二叉树的结构, 并用数组的元素指向该结构
- struct TreeNode
- {
- ElementType Element;
- Tree Left;
- Tree Right;
- }T1[MaxTree], T2[MaxTree];
- // 这样就可以直接按题目要求进行逐行读入了
- // 程序的整体框架
- int main()
- {
- Tree R1, R2;
- R1 = BuildTree(T1);
- //printf("%d\n", R1);
- R2 = BuildTree(T2);
- //printf("%d\n", R2);
- if (Isomorphic(R1, R2)) // 返回 1 说明同构, 返回 0 说明不同构
- printf("Yes\n");
- else
- printf("No\n");
- return 0;
- }
- // 建二叉树
- //1, 将结点, 左右孩子的位置读入数组结构
- //2, 通过遍历数组, 找出头结点
- // 没有其他结点指向的就是头结点, 所以可以用一个标志
- Tree BuildTree(struct TreeNode T[])
- {
- int N;
- int Isnode[MaxTree] = {0};
- char cl, cr; // 因为有'-'存在, 所以先用 char 型变量暂存, 然后再放到结构里
- scanf("%d\n", &N);
- if (N) {
- for (int i = 0; i <N; i++) {
- scanf("%c %c %c\n", &T[i].Element, &cl, &cr); //'-'在结构里用 - 1 表示
- if (cl != '-') {
- T[i].Left = cl - '0'; // 在这里可以同时加入对于根结点的判断
- Isnode[T[i].Left] = 1;
- }
- else
- T[i].Left = Null;
- if (cr != '-') {
- T[i].Right = cr - '0';
- Isnode[T[i].Right] = 1;
- }
- else
- T[i].Right = Null;
- }
- // 最后遍历一遍结构数组, Isnode 为 0 的就是头结点
- for (int m = 0; m < N; m++) {
- if (!Isnode[m])
- return m;
- }
- }
- return Null;
- }
- // 下面来判断是否为同构
- // 都为空树, 直接返回 1; 一个空一个不空, 直接返回 0
- // 都不空: 结点不同, 直接 0; 结点相同, 再看子树
- // 左子树同不存在, 就递归调用右子树
- // 左子树存在, 看是否相等, 不相等就交换左右子树, 再递归调用
- 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
- return (Isomorphic(T1[R1].Left, T2[R2].Right) && Isomorphic(T1[R1].Right, T2[R2].Left));
- }
自己理解的思路
- #include <cstdio>
- #include <cstdlib>
- #define MaxTree 10
- #define Null -1
- struct TreeNode
- {
- char Element;
- int Left;
- int Right;
- }T1[MaxTree], T2[MaxTree];
- int MadeTree (struct TreeNode T[]);
- int Isomorphic(int R1, int R2);
- int main()
- {
- int R1, R2;
- R1 = MadeTree(T1);
- R2 = MadeTree(T2);
- if (Isomorphic(R1, R2))
- printf("Yes\n");
- else
- printf("No\n");
- return 0;
- }
- int MadeTree(struct TreeNode T[])
- {
- int N;
- scanf("%d\n", &N);
- if (!N)
- return Null;
- else {
- char l,r;
- int Root[MaxTree] = {0};
- for (int i = 0; i < N; i++) {
- scanf("%c %c %c\n", &T[i].Element, &l, &r);
- if (l != '-') {
- T[i].Left = l - '0';
- Root[T[i].Left] = 1;
- }
- else
- T[i].Left = Null;
- if (r != '-') {
- T[i].Right = r - '0';
- Root[T[i].Right] = 1;
- }
- else
- T[i].Right = Null;
- }
- for (int m = 0; m < N; m++) {
- if (!Root[m])
- return m;
- }
- }
- return Null;
- }
- int Isomorphic(int R1, int 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
- return (Isomorphic(T1[R1].Left, T2[R2].Right) &&
- Isomorphic(T1[R1].Right, T2[R2].Left));
- }
但是这样写, 好像并没有什么本质的区别, 和照抄没啥两样......
然后本地运行还是有问题: 不是正常的回车结束.
暂时还没想明白是啥问题, 应该是输入输出有关.
来源: http://www.bubuko.com/infodetail-3053109.html