编写一个c语言程序,判断两颗二叉树b1和b2是否等价的递归模型f(b1,b1)
时间: 2024-11-22 08:43:33 浏览: 2
判断两颗二叉树是否相似(C语言)
5星 · 资源好评率100%
在C语言中,编写一个递归函数来判断两棵二叉树(b1和b2)是否等价通常涉及到深度优先搜索(DFS),可以使用结构体表示二叉树节点,并比较两个节点的值以及它们的左右子树是否都为空或对应子树也相等。这里是一个简单的递归模型:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 判断两个树是否等价的递归函数
int f(TreeNode* b1, TreeNode* b2) {
// 如果两个节点都为空,说明等价
if (b1 == NULL && b2 == NULL)
return 1;
// 如果只有一个节点为空或者值不等,说明不等价
else if (b1 == NULL || b2 == NULL || b1->val != b2->val)
return 0;
// 否则,分别递归地检查左右子树是否等价
return f(b1->left, b2->left) && f(b1->right, b2->right);
}
// 主函数用于测试
int main() {
// 创建并初始化示例二叉树
TreeNode* b1 = ...; // 初始化第一个树
TreeNode* b2 = ...; // 初始化第二个树
int result = f(b1, b2);
printf("The trees are %s equivalent.\n", result ? "equally" : "not");
return 0;
}
```
在这个函数中,我们首先检查根节点是否为空,接着检查值是否相等。如果满足这两个条件,则递归地对左右子树进行相同的检查。如果任何时候其中一个条件不满足,就立即返回0,表示不等价。
阅读全文