PTA 数据结构与算法题目集 7-3 树的同构

学习陈越老师的数据结构课程时的作业
7-3 树的同构（25 分）

给定两棵树T1和T2。如果T1可以通过若干次左右孩子互换就变成T2，则我们称两棵树是“同构”的。例如图1给出的两棵树就是同构的，因为我们把其中一棵树的结点A、B、G的左右孩子互换后，就得到另外一棵树。而图2就不是同构的。 PTA 数据结构与算法题目集 7-3 树的同构现给定两棵树，请你判断它们是否是同构的。

输入格式:

输入给出2棵二叉树树的信息。对于每棵树，首先在一行中给出一个非负整数N (≤10)，即该树的结点数（此时假设结点从0到N−1编号）；随后N行，第i行对应编号第i个结点，给出该结点中存储的1个英文大写字母、其左孩子结点的编号、右孩子结点的编号。如果孩子结点为空，则在相应位置上给出“-”。给出的数据间用一个空格分隔。注意：题目保证每个结点中存储的字母是不同的。
输出格式:

如果两棵树是同构的，输出“Yes”，否则输出“No”。
输入样例1（对应图1）：

8
A 1 2
B 3 4
C 5 -
D - -
E 6 -
G 7 -
F - -
H - -
8
G - 4
B 7 6
F - -
A 5 1
H - -
C 0 -
D - -
E 2 -

输出样例1:

Yes

输入样例2（对应图2）：

8
B 5 7
F - -
A 0 3
C 6 -
H - -
D - -
G 4 -
E 1 -
8
D 6 -
B 5 -
E - -
H - -
C 0 2
G - 3
F - -
A 1 4

输出样例2:

No

思路：利用一个结构体存储树的一个叶子节点，把一棵树的所有叶子节点存储在一个vector中，结构体有左儿子、右儿子和当前节点的值，左右儿子存储的是相应的节点在vector中的下标。判断的时候，首先找出树根的位置。每个节点都存在一个vector中，把所有出现过的左右儿子的下标都记录下来，没有出现过的那个下标对应的节点就是根节点。

#include <iostream>
#include <vector>
#include <set>
using namespace std;
struct point{
    char element;
    int left;
    int right;
    point(char _element, int _left, int _right):
            element(_element), left(_left), right(_right){}
};

typedef vector<point> tree_type;
tree_type r1;
tree_type r2;
set<int> check;  // 使用集合因为集合可以自动排序，方便对比

void createTree(tree_type &tree, int num, int &root)
{
    check.clear();
    if(num==0) {
        root = -1;
        return ;
    }
    char temp_element_name, temp_cl, temp_cr;
    for (int i = 0; i < num; ++i) {
        cin>>temp_element_name>>temp_cl>>temp_cr;
        int cl = temp_cl=='-'? -1: temp_cl-'0';
        int cr = temp_cr=='-'? -1: temp_cr-'0';
        tree.emplace_back(point(temp_element_name, cl, cr));
        check.insert(cl);
        check.insert(cr);
    }
    int temp_r_root = 0;  // 查找树根，如果某个下标没有出现过，那么那个下标在vector中对应的就是根节点
    for(auto item = ++check.begin(); item != check.end(); item++)
    {
        if(temp_r_root != *item)
            break;
        else
            temp_r_root++;
    }
    root = temp_r_root;
}
int Isomorphic(int r1_root, int r2_root){
    if(r1_root == -1 and r2_root == -1)   // 判断是不是都是空树
        return 1;
    else if((r1_root == -1 and r2_root != -1) or (r1_root != -1 and r2_root == -1))  // 判断是否一个空一个不空
        return 0;
    else if(r1[r1_root].element != r2[r2_root].element)  // 判断当前的值是否相同
        return 0;
    else if(r1[r1_root].left == -1 and r2[r2_root].left == -1)  // 如果左儿子都为空，则判断右儿子
        return Isomorphic(r1[r1_root].right, r2[r2_root].right);
    else if(r1[r1[r1_root].left].element == r2[r2[r2_root].left].element)  // 如果左儿子不空，且左儿子相同，则两个树不必交换对比
        return Isomorphic(r1[r1_root].left, r2[r2_root].left) and Isomorphic(r1[r1_root].right, r2[r2_root].right);
    else  // 如果左儿子不空，且左儿子不同，则两个树交换对比
        return Isomorphic(r1[r1_root].left, r2[r2_root].right) and Isomorphic(r1[r1_root].right, r2[r2_root].left);
}
int main() {

    int r1_num, r2_num, r1_root, r2_root;

    //  保存第一颗树
    cin>>r1_num;
    createTree(r1, r1_num, r1_root);

    //  保存第二颗树
    cin>>r2_num;
    createTree(r2, r2_num, r2_root);

    int result = Isomorphic(r1_root, r2_root);
    if(result) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

}

PTA 数据结构与算法题目集 7-3 树的同构

相关推荐