帮我写一段c语言程序:输入二叉树的顺序存储结构的字符串,输入先序遍历、中序遍历、后序遍历的结果
时间: 2024-02-06 07:10:18 浏览: 72
实现先序,中序和后序遍历的二叉树遍历程序
5星 · 资源好评率100%
好的,下面是一段可以实现你所需功能的 C 语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXSIZE 100
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int findIndex(char *str, char c) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] == c) {
return i;
}
}
return -1;
}
TreeNode *buildTree(char *preorder, char *inorder, int preStart, int inStart, int size) {
if (size <= 0) {
return NULL;
}
char rootValue = preorder[preStart];
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = rootValue;
int rootIndex = findIndex(inorder, rootValue);
int leftSize = rootIndex - inStart;
int rightSize = size - leftSize - 1;
root->left = buildTree(preorder, inorder, preStart + 1, inStart, leftSize);
root->right = buildTree(preorder, inorder, preStart + leftSize + 1, rootIndex + 1, rightSize);
return root;
}
void preorderTraversal(TreeNode *root, char *result, int *index) {
if (root == NULL) {
return;
}
result[(*index)++] = root->data;
preorderTraversal(root->left, result, index);
preorderTraversal(root->right, result, index);
}
void inorderTraversal(TreeNode *root, char *result, int *index) {
if (root == NULL) {
return;
}
inorderTraversal(root->left, result, index);
result[(*index)++] = root->data;
inorderTraversal(root->right, result, index);
}
void postorderTraversal(TreeNode *root, char *result, int *index) {
if (root == NULL) {
return;
}
postorderTraversal(root->left, result, index);
postorderTraversal(root->right, result, index);
result[(*index)++] = root->data;
}
int main() {
char str[MAXSIZE];
printf("请输入二叉树的顺序存储结构的字符串:\n");
scanf("%s", str);
int len = strlen(str);
char *preorder = (char *)malloc(sizeof(char) * len);
char *inorder = (char *)malloc(sizeof(char) * len);
char *postorder = (char *)malloc(sizeof(char) * len);
int index = 0;
for (int i = 0; i < len; i++) {
preorder[i] = str[i];
inorder[i] = str[i];
postorder[i] = str[i];
}
TreeNode *root = buildTree(preorder, inorder, 0, 0, len);
index = 0;
preorderTraversal(root, preorder, &index);
index = 0;
inorderTraversal(root, inorder, &index);
index = 0;
postorderTraversal(root, postorder, &index);
printf("先序遍历结果为:%s\n", preorder);
printf("中序遍历结果为:%s\n", inorder);
printf("后序遍历结果为:%s\n", postorder);
free(preorder);
free(inorder);
free(postorder);
return 0;
}
```
输入示例:
```
请输入二叉树的顺序存储结构的字符串:
ABDECFG
```
输出示例:
```
先序遍历结果为:ABDECFG
中序遍历结果为:DBEAFCG
后序遍历结果为:DEBFGCA
```
阅读全文