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

在二叉链表表示的二叉树中，判断两个二叉树是否相等通常涉及深度优先遍历（如前序、中序或后序遍历），并将每个节点的值进行比较。以下是使用递归的方式实现这一功能：

1. 定义一个辅助函数，比如`isSameTree(p, q)`，其中`p`和`q`分别代表两个二叉链表的根节点。

2. 检查`p`和`q`是否为空，如果都为空，则说明两棵树都是空的，它们相等，返回`true`。
3. 如果只有一个节点为空，说明一棵树有一个节点而另一棵没有，它们不相等，返回`false`。
4. 如果`p`和`q`都不为空，比较`p`和`q`的值是否相等。如果相等，再对`p`的左子节点和`q`的左子节点，以及`p`的右子节点和`q`的右子节点递归地调用`isSameTree`函数。
5. 如果`p`和`q`的当前节点值不相等，立即返回`false`。

def isSameTree(p, q):
    if p is None and q is None:
        return True
    elif p is None or q is None:
        return False
    else:
        return p.val == q.val and isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

相关问题

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

注释在代码中已经给出。