假设二叉树采用二叉链存储结构存放,设计一个递归算法判断两棵二叉树btl和bt2是否同构。编写完整的实验程序,并采用相应数据进行测试。要求用c++编程 并带上运行结果

在C++中，我们可以设计一个递归函数来判断两个二叉树是否同构。所谓同构，意味着一棵二叉树可以通过节点值的映射转换成另一棵树。以下是递归算法的基本思路：

#include <iostream>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

bool isIsomorphic(TreeNode* bt1, TreeNode* bt2) {
    if (!bt1 && !bt2) return true; // 都为空，同构
    if (!bt1 || !bt2) return false; // 只有一个为空，不构成同构

    // 检查当前节点值是否相等，并检查左右子树是否同构
    if (bt1->val != bt2->val) return false;
    return isIsomorphic(bt1->left, bt2->left) && isIsomorphic(bt1->right, bt2->right);
}

// 主函数示例
int main() {
    // 创建两棵测试二叉树
    TreeNode* bt1 = new TreeNode(1);
    bt1->left = new TreeNode(2);
    bt1->right = new TreeNode(3);
    bt1->left->left = new TreeNode(4);
    bt1->left->right = new TreeNode(5);

    TreeNode* bt2 = new TreeNode('a');
    bt2->left = new TreeNode('b');
    bt2->right = new TreeNode('c');
    bt2->left->left = new TreeNode('d');
    bt2->left->right = new TreeNode('e');

    // 判断两棵树是否同构
    bool result = isIsomorphic(bt1, bt2);

    cout << "Are the two binary trees isomorphic? " << (result ? "Yes" : "No") << endl;

    // 清理内存
    delete bt1;
    delete bt2;
    return 0;
}

在这个例子中，我们首先检查根节点是否相同及其子树是否都同构。如果满足条件，那么它们就是同构的。然后我们创建了两棵简单的二叉树作为测试案例。运行这个程序，如果输出“Are the two binary trees isomorphic? Yes”，则说明这两个树是同构的。