帮我用c语言写个程序来比较两棵树是否相等
时间: 2023-10-05 18:05:24 浏览: 35
好的,以下是比较两棵树是否相等的C语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
int isSameTree(struct TreeNode* p, struct TreeNode* q) {
if (p == NULL && q == NULL) return 1;
if (p == NULL || q == NULL) return 0;
if (p->val != q->val) return 0;
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
int main() {
// 构造两棵树
struct TreeNode* p = (struct TreeNode*)malloc(sizeof(struct TreeNode));
struct TreeNode* q = (struct TreeNode*)malloc(sizeof(struct TreeNode));
p->val = 1;
q->val = 1;
p->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
p->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
q->left = (struct TreeNode*)malloc(sizeof(struct TreeNode));
q->right = (struct TreeNode*)malloc(sizeof(struct TreeNode));
p->left->val = 2;
p->right->val = 3;
q->left->val = 2;
q->right->val = 3;
p->left->left = NULL;
p->left->right = NULL;
p->right->left = NULL;
p->right->right = NULL;
q->left->left = NULL;
q->left->right = NULL;
q->right->left = NULL;
q->right->right = NULL;
if (isSameTree(p, q))
printf("两棵树相等\n");
else
printf("两棵树不相等\n");
return 0;
}
```
这个程序中,我们定义了一个`TreeNode`结构体表示树节点,其中包含了一个整数`val`表示节点的值,以及指向左右子节点的指针`left`和`right`。
`isSameTree`函数接受两棵树的根节点指针`p`和`q`,递归比较两棵树是否相等。如果两棵树都为空,则返回`1`;如果其中一棵树为空,则返回`0`;如果两棵树的根节点的值不相等,则返回`0`;否则递归比较左右子树是否相等。
在`main`函数中,我们构造了两棵树并调用`isSameTree`函数进行比较,输出比较结果。