以二叉链表作为二叉树的存储结构，判别两颗树是否相等

判断两棵二叉树是否相等，可以分别从它们的根节点开始递归地比较它们的左子树和右子树是否相等。具体步骤如下：

1.判断两棵二叉树的根节点是否相等，如果不相等，则这两棵树肯定不相等，直接返回 false。

2.如果两棵树的根节点相等，再递归比较它们的左子树和右子树。如果左右子树都相等，则这两棵树相等，返回 true；否则返回 false。

递归的结束条件为，当任何一棵树的节点为空时，另一棵树的对应节点也必须为空，才能认为它们相等。

使用二叉链表作为二叉树的存储结构，每个节点包含了它的数据、左子节点和右子节点三个指针，可以方便地进行递归操作。

相关问题

用c++程序以二叉链表作为二叉树的存储结构，编写以下算法： （1）交换二叉树每个结点的左孩子和右孩子。 （2）判别两棵树是否相等。

在C++中，我们可以使用二叉链表来表示二叉树，然后分别编写两个函数来完成这两个任务。

**（1）交换二叉树每个结点的左孩子和右孩子**

首先，我们需要定义二叉链表节点结构体，包含一个值、左右指针。接下来，遍历整个二叉树，对每个节点执行交换操作：

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

void swapChildren(TreeNode*& root) {
    if (root) {
        std::swap(root->left, root->right);
        swapChildren(root->left);
        swapChildren(root->right);
    }
}

这个`swapChildren` 函数通过递归遍历树的每一个节点，将当前节点的`left` 和 `right` 指向的内容进行交换。

**（2）判别两棵树是否相等**

判断两棵二叉树是否相等，需要比较根节点的值是否相等以及它们的左右子树是否也相等：

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true; // 都为空，认为相等
    if (!p || !q) return false; // 有一个空，认为不等

    return p->val == q->val &&
           isSameTree(p->left, q->left) &&
           isSameTree(p->right, q->right);
}

这个`isSameTree` 函数采用递归的方式，如果两个节点都为空则返回true；若其中一个为空则返回false；如果节点值相等并且它们的子树也相等，则返回true。

C++编写程序：以二叉链表作为二叉树的存储结构，设计以下算法。 (1)统计二叉树的叶结点个数。 (2)判别两棵树是否相等。 (3)交换二叉树每个结点的左孩子和右孩子。（实验要求：采用二叉链表作为存储结构建立二叉树 ；采用递归算法对其进行遍历（先序、中序、后序） 将遍历结果输出）

在C++中，为了实现上述算法，我们需要首先创建一个二叉链表节点类，用于表示二叉树的节点，并包含左右孩子的指针。然后我们可以构建二叉树类，包括相应的功能：

1. 统计叶节点个数:

class TreeNode {
public:
    int val;
    TreeNode* left;
    TreeNode* right;
    // 构造函数和其他必要的操作...
};

size_t countLeaves(TreeNode* root) {
    if (!root || !root->left && !root->right) return 1; // 根节点是叶子
    else return countLeaves(root->left) + countLeaves(root->right);
}

2. 判别两棵树是否相等:

bool isSameTree(TreeNode* p, TreeNode* q) {
    if (!p && !q) return true;
    if (!p || !q || p->val != q->val) return false;
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

3. 交换节点的左右孩子:

void swapChildren(TreeNode* &node) {
    if (node) {
        std::swap(node->left, node->right);
        swapChildren(node->left);
        swapChildren(node->right);
    }
}

对于递归遍历（先序、中序、后序），你可以这样实现：
- 先序遍历（根-左-右）:

void preOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        result += to_string(root->val) + " ";
        preOrderTraversal(root->left, result);
        preOrderTraversal(root->right, result);
    }
}

- 中序遍历（左-根-右）:

void inOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        inOrderTraversal(root->left, result);
        result += to_string(root->val) + " ";
        inOrderTraversal(root->right, result);
    }
}

- 后序遍历（左-右-根）:

void postOrderTraversal(TreeNode* root, std::string& result) {
    if (root) {
        postOrderTraversal(root->left, result);
        postOrderTraversal(root->right, result);
        result += to_string(root->val) + " ";
    }
}

实验要求部分可以通过以下方式完成：
1. 创建二叉树实例并输入数据。
2. 调用相应遍历函数并输出结果。
3. 分别计算两棵已构造好的二叉树的叶节点数，比较它们是否相等。