浙大数据结构——03-树1 树的同构

本文主要是介绍浙大数据结构——03-树1 树的同构，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这道题我依然采用STL库的map，从而大幅减少了代码量

简单说一下思路，两棵树是否同构，只需比较俩树字母相同的结点是否同构，即是否左==左，右==右或者左==右，右==左。

1、条件准备

atree和btree是存两个数结点字母，第几个就存输入的第几个结点的字母。

map通过结点的字母作为键，从而找到两个子节点的信息

都要用char类型

#include <iostream>
#include <map>
using namespace std;char atree[15], btree[15];
map<char, pair<char, char>> ma, mb;

主函数先是加快cin,cout

然后初始化两棵树，并保存结点个数，然后用solve函数进行处理

int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int num;num = init(atree, ma);num = init(btree, mb);solve(num);return 0;
}

2、init函数

参数传递为要初始化的树的char数组和map，然后输入结点数。

循环输入第i个结点字母和其两子树的下标。

输入完后我们要把子树的下标转换成对应字母，

遍历结点数组，如果子节点不为‘-',则更新，将存的数字下标转为结点字母

int init(char *tree, map<char, pair<char, char>> &m)
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> tree[i];cin >> m[tree[i]].first >> m[tree[i]].second;}for (int i = 0; i < n; i++){if (m[tree[i]].first != '-'){m[tree[i]].first = tree[m[tree[i]].first - '0'];}if (m[tree[i]].second != '-'){m[tree[i]].second = tree[m[tree[i]].second - '0'];}}return n;
}

3、judge函数

judge函数用来判断该节点俩树是否同构。

即左==左，右==右或者左==右，右==左。

bool judge(char c)
{if (ma[c].first == mb[c].first && ma[c].second == mb[c].second)return 1;if (ma[c].first == mb[c].second && ma[c].second == mb[c].first)return 1;return 0;
}

4、solve函数

遍历其中一棵树的结点，判断是否同构，不同构则输出No,

如果所有结点同构则输出Yes

void solve(int n)
{for (int i = 0; i < n; i++){if (!judge(atree[i])){cout << "No";return;}}cout << "Yes";
}

5、总结

这道题使用了map来减少了代码量，其实这一部分也可以用数组实现，因为树中的结点字母不重复，用字母的ACSII码作为下标也可以存储子树。

完整代码如下：

#include <iostream>
#include <map>
using namespace std;char atree[15], btree[15];
map<char, pair<char, char>> ma, mb;int init(char *tree, map<char, pair<char, char>> &m)
{int n;cin >> n;for (int i = 0; i < n; i++){cin >> tree[i];cin >> m[tree[i]].first >> m[tree[i]].second;}for (int i = 0; i < n; i++){if (m[tree[i]].first != '-'){m[tree[i]].first = tree[m[tree[i]].first - '0'];}if (m[tree[i]].second != '-'){m[tree[i]].second = tree[m[tree[i]].second - '0'];}}return n;
}bool judge(char c)
{if (ma[c].first == mb[c].first && ma[c].second == mb[c].second)return 1;if (ma[c].first == mb[c].second && ma[c].second == mb[c].first)return 1;return 0;
}
void solve(int n)
{for (int i = 0; i < n; i++){if (!judge(atree[i])){cout << "No";return;}}cout << "Yes";
}int main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int num;num = init(atree, ma);num = init(btree, mb);solve(num);return 0;
}

这篇关于浙大数据结构——03-树1 树的同构的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---