﻿ Isomorphic - 小墨迹
chevron_right 首页 » 考试速查 » Isomorphic
Isomorphic
2020-11-06 | 考试速查 | 1 条评论 | 55 次阅读 | 81字

4-11 Isomorphic (10分)
Two trees, T1 and T2, are isomorphic if T1 can be transformed into T2 by swapping left and right children of (some of the) nodes in T1. For instance, the two trees in Figure 1 are isomorphic because they are the same if the children of A, B, and G, but not the other nodes, are swapped. Give a polynomial time algorithm to decide if two trees are isomorphic.

Figure 1
Format of functions:
int Isomorphic( Tree T1, Tree T2 );
where Tree is defined as the following:

typedef struct TreeNode *Tree;
struct TreeNode {

``````ElementType Element;
Tree  Left;
Tree  Right;``````

};
The function is supposed to return 1 if T1 and T2 are indeed isomorphic, or 0 if not.

Sample program of judge:

# include <stdlib.h>

typedef char ElementType;

typedef struct TreeNode *Tree;
struct TreeNode {

``````ElementType Element;
Tree  Left;
Tree  Right;``````

};

Tree BuildTree(); / details omitted /

int Isomorphic( Tree T1, Tree T2 );

int main()
{

``````Tree T1, T2;
T1 = BuildTree();
T2 = BuildTree();
printf(“%d\n”, Isomorphic(T1, T2));
return 0;``````

}

/ Your function will be put here /

Sample Output 1 (for the trees shown in Figure 1):

``````
/*
** 一次只比较一个节点，剩下的事情交给递归去干罢
** 缺点是，时间复杂度大幅提升。
** 两个节点共有四个子节点，令其分别对应和交叉比较
** 取或运算
*/
int Isomorphic(Tree T1, Tree T2){
/* 一个为空 */
if(!T1 && T2){
return 0;
}else if (T1 && !T2){
return 0;
}
/* 两个为空 */
if (T1 == T2){
return 1;
}
/* 本身不相等 */
if (T1->Element != T2->Element){
return 0;
}
/* 左子相等 */
if (Isomorphic(T1->Left,T2->Left)
|| Isomorphic(T1->Left,T2->Right)
){
/* 判断右子 */

}else
{
return 0;
}
if (Isomorphic(T1->Right,T2->Right)
|| Isomorphic(T1->Right,T2->Left)
){
return 1;
}

return 0;
}
``````

### 添加新评论                              iuio博主
November 6th, 2020 at 11:45 am

好红，每当想起你，枫叶就会被染红。

arrow_forward 下一篇