二叉树同构
#include<iostream> #define MaxTree 10 #define ElementType char #define Tree int #define Null -1 using namespace std; struct TreeNode { ElementType element;// char Tree left;// int Tree right; } T1[MaxTree], T2[MaxTree]; // 返回root并填充结构数组 int buildTree(struct TreeNode t[]) { int n; cin >> n; Tree root = Null; if (n != 0) { int check[MaxTree]; for (int i = 0; i < n; i++) check[i] = 0; for (int i = 0; i < n; i++) { char cl, cr; cin>>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; } // 遍历check数组，寻找root for (int i = 0; i < n; i++) { if (check[i] != 1) { root = i; break; } } } // t[i]中没有任何节点的left与right指向它，它就是root return root; } bool isOmorphic(Tree r1, Tree r2) { if (r1 == Null && r2 == Null) return true; if ((r1 == Null && r2 != Null) || (r2 == Null && r1 != Null)) return false; if (T1[r1].element != T2[r2].element) return false; // 左右子树同构 if (isOmorphic(T1[r1].left, T2[r2].left) && isOmorphic(T1[r1].right, T2[r2].right)) return true; // 左右子树交换后同构 if (isOmorphic(T1[r1].left, T2[r2].right) && isOmorphic(T1[r1].right, T2[r2].left)) return true; return false; } int main() { Tree R1, R2; R1 = buildTree(T1); R2 = buildTree(T2); if (isOmorphic(R1, R2)) printf("Yes\n"); else printf("No\n"); system("PAUSE"); return 0; }