数据结构判断两棵树是否相等

算法思想

判断两棵二叉树是否相等，主要有以下几个步骤：

1. 递归比较：如果两棵树的根节点的数据相等，则继续递归地比较左右子树。
2. 递归终止条件：
   • 如果两棵树都为空，则认为它们相等。
   • 如果一棵树为空，另一棵树不为空，则认为它们不相等。
   • 如果根节点的数据不同，则认为它们不相等。
3. 递归推进：如果根节点数据相同，继续比较左子树和右子树

程序设计

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

// 定义二叉树节点结构体
typedef int TElemType;  // 假设数据类型为int，可根据需要修改
typedef struct BiTNode {
    TElemType data;
    struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

// 判断两棵二叉树是否相等的递归函数
int areTreesEqual(BiTree tree1, BiTree tree2) {
    // 如果两棵树都为空，认为相等
    if (tree1 == NULL && tree2 == NULL) {
        return 1;
    }

    // 如果一棵树为空，另一棵树不为空，则不相等
    if (tree1 == NULL || tree2 == NULL) {
        return 0;
    }

    // 如果根节点的数据不相等，则不相等
    if (tree1->data != tree2->data) {
        return 0;
    }

    // 递归判断左子树和右子树是否相等
    return areTreesEqual(tree1->lchild, tree2->lchild) && areTreesEqual(tree1->rchild, tree2->rchild);
}

// 创建一个新节点的函数
BiTree createNode(TElemType data) {
    BiTree newNode = (BiTree)malloc(sizeof(BiTNode));
    if (newNode) {
        newNode->data = data;
        newNode->lchild = newNode->rchild = NULL;
    }
    return newNode;
}

// 主函数测试
int main() {
    // 创建两棵相同的树
    BiTree tree1 = createNode(1);
    tree1->lchild = createNode(2);
    tree1->rchild = createNode(3);

    BiTree tree2 = createNode(1);
    tree2->lchild = createNode(2);
    tree2->rchild = createNode(3);

    // 判断两棵树是否相等
    if (areTreesEqual(tree1, tree2)) {
        printf("The trees are equal.\n");
    }
    else {
        printf("The trees are not equal.\n");
    }

    return 0;
}