用c语言代码建立二叉树的二叉链表存储结构,要求编程实现如下功能:1假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树2应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作
时间: 2024-01-23 14:10:12 浏览: 150
设两棵二叉树的根结点地址分别为P及Q,采用二叉链表的形式存储这二棵树上所有的结点。请编写程序,判断它们是否相似。
好的,请稍等,我先为您编写一个C语言代码,实现您所需的功能。
```c
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据先序遍历序列构建二叉树
TreeNode *createTree(char *preorder, int *index) {
char ch = preorder[(*index)++];
if (ch == '#') {
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = ch;
node->left = createTree(preorder, index);
node->right = createTree(preorder, index);
return node;
}
// 判断两棵二叉树是否相等
int isEqualTree(TreeNode *root1, TreeNode *root2) {
if (root1 == NULL && root2 == NULL) {
return 1;
} else if (root1 == NULL || root2 == NULL) {
return 0;
} else if (root1->data != root2->data) {
return 0;
} else {
return isEqualTree(root1->left, root2->left) && isEqualTree(root1->right, root2->right);
}
}
int main() {
char preorder1[] = "ABD#G###CE##FH###";
char preorder2[] = "ABD#G###CE##FH###";
int index = 0;
TreeNode *root1 = createTree(preorder1, &index);
index = 0;
TreeNode *root2 = createTree(preorder2, &index);
if (isEqualTree(root1, root2)) {
printf("两棵二叉树相等\n");
} else {
printf("两棵二叉树不相等\n");
}
return 0;
}
```
以上代码实现了根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树,以及应用二叉树的遍历操作来实现判断两棵二叉树是否相等的操作。在这里,我们使用了递归的方法来实现树的遍历和比较操作。
阅读全文