判断二叉树是否相等c语言
时间: 2023-08-14 18:06:31 浏览: 118
判断两棵二叉树是否相等的C语言代码如下:
```c
#include <stdbool.h>
// 二叉树结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 判断两棵二叉树是否相等
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
// 如果两棵树都为空,则相等
if (p == NULL && q == NULL) {
return true;
}
// 如果只有一棵树为空,则不相等
else if (p == NULL || q == NULL) {
return false;
}
// 如果根节点的值不相等,则不相等
else if (p->val != q->val) {
return false;
}
// 递归判断左右子树是否相等
else {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
```
该代码首先判断两棵树是否都为空,如果是,则相等;如果只有一棵树为空,则不相等;如果根节点的值不相等,则不相等;否则,递归判断左右子树是否相等。
相关问题
判断二叉树是否相等c
判断两棵二叉树是否相等的C语言代码如下:
```c
#include <stdbool.h>
// 二叉树结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 判断两棵二叉树是否相等
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
// 如果两棵树都为空,则相等
if (p == NULL && q == NULL) {
return true;
}
// 如果只有一棵树为空,则不相等
else if (p == NULL || q == NULL) {
return false;
}
// 如果根节点的值不相等,则不相等
else if (p->val != q->val) {
return false;
}
// 递归判断左右子树是否相等
else {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
}
```
该代码首先判断两棵树是否都为空,如果是,则相等;如果只有一棵树为空,则不相等;如果根节点的值不相等,则不相等;否则,递归判断左右子树是否相等。
C语言实现通过比较二叉树的前序中序后序遍历来判断二叉树是否相等
以下是一个简单的 C 语言程序,用于通过比较二叉树的前序、中序和后序遍历来判断二叉树是否相等:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
};
struct TreeNode* createNode(char val) {
struct TreeNode* node = malloc(sizeof(struct TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
void preorderTraversal(struct TreeNode* root, char* res, int* index) {
if (root == NULL) {
res[(*index)++] = '#';
return;
}
res[(*index)++] = root->val;
preorderTraversal(root->left, res, index);
preorderTraversal(root->right, res, index);
}
void inorderTraversal(struct TreeNode* root, char* res, int* index) {
if (root == NULL) {
res[(*index)++] = '#';
return;
}
inorderTraversal(root->left, res, index);
res[(*index)++] = root->val;
inorderTraversal(root->right, res, index);
}
void postorderTraversal(struct TreeNode* root, char* res, int* index) {
if (root == NULL) {
res[(*index)++] = '#';
return;
}
postorderTraversal(root->left, res, index);
postorderTraversal(root->right, res, index);
res[(*index)++] = root->val;
}
int isEqual(char* s1, char* s2) {
return strcmp(s1, s2) == 0;
}
int isSameTree(struct TreeNode* p, struct TreeNode* q) {
char preorder1[1000], preorder2[1000];
char inorder1[1000], inorder2[1000];
char postorder1[1000], postorder2[1000];
int index1 = 0, index2 = 0;
preorderTraversal(p, preorder1, &index1);
preorderTraversal(q, preorder2, &index2);
index1 = 0, index2 = 0;
inorderTraversal(p, inorder1, &index1);
inorderTraversal(q, inorder2, &index2);
index1 = 0, index2 = 0;
postorderTraversal(p, postorder1, &index1);
postorderTraversal(q, postorder2, &index2);
return isEqual(preorder1, preorder2) && isEqual(inorder1, inorder2) && isEqual(postorder1, postorder2);
}
int main() {
struct TreeNode* p = createNode('A');
p->left = createNode('B');
p->right = createNode('C');
p->left->left = createNode('D');
p->left->right = createNode('E');
p->right->left = createNode('F');
p->right->right = createNode('G');
struct TreeNode* q = createNode('A');
q->left = createNode('B');
q->right = createNode('C');
q->left->left = createNode('D');
q->left->right = createNode('E');
q->right->left = createNode('F');
q->right->right = createNode('H');
printf("%d\n", isSameTree(p, q));
return 0;
}
```
这个程序定义了一个 `TreeNode` 结构体,包含一个字符值、一个指向左子节点的指针和一个指向右子节点的指针。`createNode` 函数用于创建一个新的节点,`preorderTraversal` 函数、`inorderTraversal` 函数和 `postorderTraversal` 函数分别用于获取一棵二叉树的前序遍历、中序遍历和后序遍历序列,`isEqual` 函数用于判断两个字符串是否相等,`isSameTree` 函数用于判断两棵二叉树是否相等。在 `main` 函数中创建了两棵二叉树 `p` 和 `q`,并调用 `isSameTree` 函数判断它们是否相等。在 `isSameTree` 函数中,分别获取两棵二叉树的前序遍历、中序遍历和后序遍历序列,然后判断这三个序列是否相等即可。