03-树1 树的同构

#include <stdio.h> #include <stdlib.h> #define MaxTree 10 #define ElementType char #define Tree int #define Null -1 //c语言中NULL表示0，这里定义空指针Null表示-1 struct TreeNode { ElementType Element; Tree Left; Tree Right; } T1[MaxTree], T2[MaxTree]; Tree BuildTree(struct TreeNode T[]); int Isomorphic(Tree R1, Tree R2); 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[]) { int N; char cl, cr; scanf("%d\n",&N); Tree Root=Null; if(N) { int check[N]; int i; for(i=0; i<N; i++){ check[i]=0; } 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; } else { T[i].Left=Null; } 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; } return Root; } int Isomorphic(Tree R1, Tree R2){ //返回 1\0 ；难点：这几种基本情况不要遗漏 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)); }