设计一个C语言算法,判别两棵二叉树是否相等。
时间: 2023-06-20 11:03:44 浏览: 277
以下是一个递归的算法,用于判断两棵二叉树是否相等。
```c
#include <stdio.h>
#include <stdlib.h>
/* 定义二叉树结构体 */
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
/* 判断两棵二叉树是否相等 */
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);
}
/* 创建二叉树 */
TreeNode* createTree(int* nums, int n, int index) {
if (index >= n || nums[index] == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = nums[index];
root->left = createTree(nums, n, index * 2 + 1);
root->right = createTree(nums, n, index * 2 + 2);
return root;
}
/* 测试 */
int main() {
int nums1[] = {1, 2, 3};
int nums2[] = {1, 2, 3};
TreeNode* p = createTree(nums1, 3, 0);
TreeNode* q = createTree(nums2, 3, 0);
if (isSameTree(p, q)) {
printf("两棵二叉树相等\n");
} else {
printf("两棵二叉树不相等\n");
}
return 0;
}
```
以上代码中,`isSameTree`函数用于判断两棵二叉树是否相等。如果两棵树都为空,则它们相等;如果只有一棵树为空,则它们不相等;如果根节点不相等,则它们不相等;否则,递归判断左右子树是否相等。`createTree`函数用于创建二叉树,其中`-1`表示空节点。`main`函数用于测试,创建两棵相同的二叉树,并判断它们是否相等。
阅读全文
相关推荐
![rar](https://img-home.csdnimg.cn/images/20241231044955.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)