pta 编程题6 树的同构

逃离我推掉我的手 2021-10-24 01:52 277阅读 0赞

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

题目请参见：[树的同构][Link 1]

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

判断两棵树是否同构：用递归的方法。如果当前两个结点都为空，则返回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 }

转载于:https://www.cnblogs.com/lxc1910/p/8684020.html

[pta]: http://www.cnblogs.com/lxc1910/p/8811251.html
[Link 1]: https://pintia.cn/problem-sets/951072707007700992/problems/975887310869037056