pta 编程题6 树的同构

其它pta数据结构编程题请参见：pta

题目请参见：树的同构

因题目中左右子树是按照下标给出，因此用数组存放树是更好的方法。

判断两棵树是否同构：用递归的方法。如果当前两个结点都为空，则返回TRUE；如果一个结点空一个不空，或者两个结点都不为空但是结点存储的数据不同，则返回FALSE。然后递归地的调用函数，判断是否左子树和左子树相同且右子树和右子树相同，或者左子树和左子树相同且右子树和右子树相同。

 1 #include <iostream>
 2 using namespace std;
 3 
 4 struct Node
 5 {
 6     char data;
 7     int left;
 8     int right;
 9 };
10 
11 int buildTree(Node tree[]);
12 bool isSame(Node tree1[], int root1, Node tree2[], int root2);
13 
14 int main()
15 {
16     Node tree1[10], tree2[10];
17     int root1, root2;
18     root1 = buildTree(tree1);
19     root2 = buildTree(tree2);
20     if (isSame(tree1, root1, tree2, root2)) cout << "Yes";
21     else cout << "No";
22     return 0;
23 }
24 
25 int buildTree(Node tree[])
26 {
27     int num, i, root = -1;
28     char d, l, r;
29     cin >> num;
30     int judgeRoot[10] = {};
31     for (i = 0; i < num; i++)
32     {
33         cin >> d >> l >> r;
34         tree[i].data = d;
35         if (l != '-')
36         {
37             tree[i].left = l - '0';
38             judgeRoot[l - '0'] = 1;
39         }
40         else tree[i].left = -1;
41         if (r != '-')
42         {
43             tree[i].right = r - '0';
44             judgeRoot[r - '0'] = 1;
45         }
46         else tree[i].right = -1;
47     }
48     for (i = 0; i < num; i++)
49     {
50         if (judgeRoot[i] == 0) root = i;
51     }
52     return root;
53 }
54 
55 bool isSame(Node tree1[], int r1, Node tree2[], int r2)
56 {
57     if (r1 == -1 && r2 == -1) return true;
58     if (r1 == -1 && r2 > -1 || r1 > -1 && r2 == -1) return false;
59     if (tree1[r1].data != tree2[r2].data) return false;
60     return isSame(tree1, tree1[r1].left, tree2, tree2[r2].left)
61         && isSame(tree1, tree1[r1].right, tree2, tree2[r2].right)
62         || isSame(tree1, tree1[r1].left, tree2, tree2[r2].right)
63         && isSame(tree1, tree1[r1].right, tree2, tree2[r2].left);
64 }