以二叉链表作为二叉树的存储结构，编写以下算法2）判别两棵树是否相等。 [题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。

ChitGPT: 您好，我是ChitGPT，一个基于GPT模型的AI对话系统，可以和您进行自然语言的交互。关于您的问题，以二叉链表作为二叉树的存储结构，我们可以先判断当前节点是否相等，然后递归判断左右子树是否相等。以下是算法实现：

bool isEqual(Node* root1, Node* root2){
if(root1 == nullptr && root2 == nullptr){
return true;
}
else if(root1 == nullptr || root2 == nullptr){
return false;
}
else if(root1->val != root2->val){
return false;
}
else{
return isEqual(root1->left, root2->left) && isEqual(root1->right, root2->right);
}
}

其中，Node是表示二叉树节点的结构体，包含val、left和right三个字段。使用递归函数isEqual可以判断两棵二叉树是否相等，时间复杂度为O(n)，其中n为二叉树节点数。

相关问题

以二叉链表作为二叉树的存储结构，使用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;
}

以二叉链表作为二叉树的存储结构， 编写以下算法： (2) 判别 两棵树是否相等。用c语言写出完整的代码与注释

以下是用 C 语言实现判断两棵树是否相等的算法，基于二叉链表存储结构：

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

/* 定义二叉树节点 */
typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

/* 创建新节点 */
TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/* 判断两棵树是否相等 */
bool isSameTree(TreeNode* p, TreeNode* q) {
    /* 两个指针都为空，则相等 */
    if (p == NULL && q == NULL) {
        return true;
    }
    /* 一个指针为空，另一个不为空，则不相等 */
    if (p == NULL || q == NULL) {
        return false;
    }
    /* 当前节点的值不同，则不相等 */
    if (p->val != q->val) {
        return false;
    }
    /* 递归判断左右子树是否相等 */
    return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}

/* 测试 */
int main() {
    /* 构造两棵树 */
    TreeNode* p = createNode(1);
    p->left = createNode(2);
    p->right = createNode(3);

    TreeNode* q = createNode(1);
    q->left = createNode(2);
    q->right = createNode(3);

    /* 判断两棵树是否相等 */
    if (isSameTree(p, q)) {
        printf("两棵树相等\n");
    } else {
        printf("两棵树不相等\n");
    }

    return 0;
}

注释在代码中已经给出。