C++ 树同构问题

2024年8月28日 | 阅读 4 分钟

计算机科学中树同构的难题在于，它需要识别两个给定树是否共享同构关系。这涉及到研究一个树是否可以通过交换某些节点的左右子节点来转换成另一个树。在这篇博文中，我们将深入探讨树同构问题的复杂性，概述其相关性，并提供一个 C++ 实现，以及一个详细的示例。

什么是树同构？

树同构问题是算法推理中的一个关键概念，经常出现在数据结构、图论和模式识别等不同领域。它是一个经典的、可以通过深度优先搜索 (DFS) 或其他树遍历方法有效解决的问题。

简单来说，如果可以在两个树 T1 和 T2 的节点之间建立一对一的映射，从而通过交换特定节点的左右子节点实现结构保持转换，那么这两个树就建立了同构关系。

C++ 实现

在 C++ 实现中，我们采用递归策略遍历树并验证它们的同构性质。

// Include directives
#include <iostream>
#include <unordered_map>
#include <vector>
 
// Namespace declaration
using namespace std;
 
// Tree Node Definition
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
 
// Function for checking tree isomorphism
bool isIsomorphic(TreeNode* root1, TreeNode* root2) {
    // Base cases
    if (!root1 && !root2)
        return true;
    if (!root1 || !root2)
        return false;
 
    // Verify root node equality
    if (root1->data != root2->data)
        return false;
 
    // Recursively check isomorphism
    return (isIsomorphic(root1->left, root2->left) && isIsomorphic(root1->right, root2->right)) ||
           (isIsomorphic(root1->left, root2->right) && isIsomorphic(root1->right, root2->left));
}
 
// Main function
int main() {
    // Example trees
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);
    tree1->left->left = new TreeNode(4);
    tree1->left->right = new TreeNode(5);
 
    TreeNode* tree2 = new TreeNode(1);
    tree2->left = new TreeNode(3);
    tree2->right = new TreeNode(2);
    tree2->right->left = new TreeNode(5);
    tree2->right->right = new TreeNode(4);
 
    // Check isomorphism
    if (isIsomorphic(tree1, tree2))
        cout << "The trees are isomorphic.\n";
    else
        cout << "The trees are not isomorphic.\n";
 
    return 0;
}

输出

The trees are isomorphic.

说明

在此示例中，我们定义了一个 TreeNode 结构来表示树节点。
isIsomorphic 函数使用递归来验证两个树是否同构。
在主函数中，创建了两个示例树，isIsomorphic 函数确定它们是否同构。

虽然上述 C++ 代码能有效确定两个树的同构性，但仍有机会进行优化和改进。通过结合额外的数据结构，我们可以提高代码的效率和可读性。具体来说，使用哈希表来存储节点之间的映射可以减少冗余比较。

示例

#include <iostream>
#include <unordered_map>
#include <vector>
 
using namespace std;
 
// Definition of Tree Node
struct TreeNode {
    int data;
    TreeNode* left;
    TreeNode* right;
 
    TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};
 
// Function to ascertain whether two trees are isomorphic
bool isIsomorphic(TreeNode* root1, TreeNode* root2, unordered_map<TreeNode*, TreeNode*>& mapping) {
    // Base cases
    if (!root1 && !root2)
        return true;
    if (!root1 || !root2)
        return false;
 
    // Confirm equality of root node values
    if (root1->data != root2->data)
        return false;
 
    // Check for existing mapping
    if (mapping.find(root1) != mapping.end() && mapping[root1] != root2)
        return false;
 
    // Establish mapping
    mapping[root1] = root2;
 
    // Recursively validate isomorphism
    return (isIsomorphic(root1->left, root2->left, mapping) && isIsomorphic(root1->right, root2->right, mapping)) ||
           (isIsomorphic(root1->left, root2->right, mapping) && isIsomorphic(root1->right, root2->left, mapping));
}
 
int main() {
    // Sample trees
    TreeNode* tree1 = new TreeNode(1);
    tree1->left = new TreeNode(2);
    tree1->right = new TreeNode(3);
    tree1->left->left = new TreeNode(4);
    tree1->left->right = new TreeNode(5);
 
    TreeNode* tree2 = new TreeNode(1);
    tree2->left = new TreeNode(3);
    tree2->right = new TreeNode(2);
    tree2->right->left = new TreeNode(5);
    tree2->right->right = new TreeNode(4);
 
    // Confirm isomorphism of the trees
    unordered_map<TreeNode*, TreeNode*> mapping;
    if (isIsomorphic(tree1, tree2, mapping))
        cout << "The trees are isomorphic.\n";
    else
        cout << "The trees are not isomorphic.\n";
 
    // Memory cleanup
    delete tree1;
    delete tree2;
 
    return 0;
}

输出

The trees are isomorphic.

结论

总之，对树同构问题的探索揭示了其复杂的性质及其在算法推理中的关键作用。虽然最初的 C++ 实现展示了功能性，但也突出了优化的机会。改进版本引入了哈希表，通过最小化冗余比较，提高了效率和可读性。这种方法对大型树尤其有利，优先考虑了性能因素。通过这些实现，我们不仅验证了同构性，还展示了解决方案的不断完善。这一过程强调了算法问题解决的动态性，强调了在编写精心设计的代码时对效率和优雅的不断追求。

下一主题C++ 中的线程安全队列

C++ 树同构问题

什么是树同构？

C++ 实现

说明

示例

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

C++ 教程

C++ 控制语句

C++ 函数

C++ 数组

C++ 类和对象

C++ 构造函数

C++ 继承

C++ 多态

C++ 抽象

C++ 命名空间

C++ 模板

C++ 字符串

C++ 指针

信号处理

C++ 异常

C++ 文件与流

C++ STL 教程

面试题

选择题

C++ 程序

C++ STL Stack

C++ STL Bitset

C++ STL Deque

C++ STL List

C++ STL Map

C++ STL Math

C++ STL priority_queue

C++ STL Queue

C++ STL Multiset

C++ STL Multimap

C++ STL Set

C++ STD Strings

C++ STL Vector

C++ 操纵符

C++ STL Algorithms

C++ Algorithm

C++ Iterators

C++ 杂项

C++ 树同构问题

什么是树同构？

C++ 实现

说明

示例

结论

相关帖子

C++ 字典

C++ unordered_multimap bucket_size() 函数

C++ 关联数组

C++ 静态成员函数

C++ 可折叠二叉树

C++ 栈溢出已检测

基本 C++ 命令

C++ 中的 match_results prefix() 和 suffix()

如何使用正则表达式在 C++ 中验证图像文件扩展名

在 C++ 中绘制不使用浮点运算的圆

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题