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

算法思想

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

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;
}