帮我写一段c语言程序:输入二叉树的顺序存储结构的字符串例如ABC##DE#G##F###,输入先序遍历ABCDEGF、中序遍历CBEGDFA、后序遍历CGEFDBA
时间: 2023-12-18 11:02:16 浏览: 85
很高兴为您提供帮助!下面是实现二叉树顺序存储结构字符串转换为三种遍历方式的c语言程序:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据顺序存储结构字符串创建二叉树
TreeNode *createBinaryTree(char *str) {
static int i = 0;
TreeNode *node = NULL;
if (str[i] != '#') {
node = (TreeNode *)malloc(sizeof(TreeNode));
node->val = str[i];
i++;
node->left = createBinaryTree(str);
i++;
node->right = createBinaryTree(str);
} else {
i++;
}
return node;
}
// 先序遍历二叉树
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c", root->val);
preOrder(root->left);
preOrder(root->right);
}
// 中序遍历二叉树
void inOrder(TreeNode *root) {
if (root == NULL) {
return;
}
inOrder(root->left);
printf("%c", root->val);
inOrder(root->right);
}
// 后序遍历二叉树
void postOrder(TreeNode *root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
printf("%c", root->val);
}
int main() {
char str[MAX_SIZE];
printf("请输入二叉树的顺序存储结构字符串:");
scanf("%s", str);
TreeNode *root = createBinaryTree(str);
printf("先序遍历结果:");
preOrder(root);
printf("\n");
printf("中序遍历结果:");
inOrder(root);
printf("\n");
printf("后序遍历结果:");
postOrder(root);
printf("\n");
return 0;
}
```
注意,这里的顺序存储结构字符串中,'#'表示空节点。在程序中,我们使用递归的方式根据字符串创建二叉树,并实现了先序、中序、后序三种遍历方式。
阅读全文