以二叉链表作为二叉树的存储结构，编写如下算法：判别两颗树是否相等

好的，我知道了。以下是以二叉链表作为二叉树的存储结构，判断两颗树是否相等的算法，代码如下：

class TreeNode:
    def __init__(self, val=0):
        self.val = val
        self.left = None
        self.right = None

def is_equal(root1, root2):
    if root1 is None and root2 is None:
        return True
    if root1 is None or root2 is None:
        return False
    if root1.val != root2.val:
        return False
    return is_equal(root1.left, root2.left) and is_equal(root1.right, root2.right)

这个算法的时间复杂度为 O(n)，其中 n 是两颗树中节点的数量之和。算法的思路是递归比较两颗树的左子树和右子树是否相等，如果树的根节点的值也相等，则这两颗树相等。注意我们在比较时要判断节点是否为空，否则可能会出现空指针错误。

相关问题

用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++编写判别两棵树是否相等的算法。

二叉树的二叉链表存储结构定义如下：

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

其中，`data`表示节点的数据，`lchild`和`rchild`分别指向节点的左子树和右子树。

判断两棵二叉树是否相等的算法如下：

int isSameTree(BiTree p, BiTree q) {
    if (p == NULL && q == NULL) {  // 两棵树均为空，相等
        return 1;
    } else if (p == NULL || q == NULL) {  // 一棵树为空，不相等
        return 0;
    } else if (p->data != q->data) {  // 数据不相等，不相等
        return 0;
    } else {  // 递归判断左子树和右子树
        return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
    }
}

首先判断两棵树是否均为空，若均为空，则两棵树相等；若一棵树为空，则两棵树不相等。若两棵树均不为空，但数据不相等，则两棵树不相等。若两棵树数据相等，则递归判断左子树和右子树是否相等。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

typedef struct BiTNode {
    int data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

BiTree createTree()
{
    int data;
    scanf("%d", &data);
    if (data == -1) {
        return NULL;
    } else {
        BiTree root = (BiTree)malloc(sizeof(BiTNode));
        root->data = data;
        root->lchild = createTree();
        root->rchild = createTree();
        return root;
    }
}

int isSameTree(BiTree p, BiTree q) {
    if (p == NULL && q == NULL) {
        return 1;
    } else if (p == NULL || q == NULL) {
        return 0;
    } else if (p->data != q->data) {
        return 0;
    } else {
        return isSameTree(p->lchild, q->lchild) && isSameTree(p->rchild, q->rchild);
    }
}

int main()
{
    BiTree p = createTree();
    BiTree q = createTree();
    if (isSameTree(p, q)) {
        printf("Two trees are same.\n");
    } else {
        printf("Two trees are not same.\n");
    }
    return 0;
}