用户输入先序序列和中序序列,输出后序序列,并打印出二叉树,用c语言写一个完整的代码
时间: 2023-08-10 15:42:30 浏览: 94
好的,这是一个比较常见的二叉树问题。下面是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据先序和中序遍历构建二叉树
TreeNode* buildTree(char* preorder, char* inorder, int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[preStart];
int i = inStart;
while (i <= inEnd && inorder[i] != preorder[preStart]) {
i++;
}
root->left = buildTree(preorder, inorder, preStart + 1, preStart + i - inStart, inStart, i - 1);
root->right = buildTree(preorder, inorder, preStart + i - inStart + 1, preEnd, i + 1, inEnd);
return root;
}
// 后序遍历并输出二叉树
void postorder(TreeNode* root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
printf("%c ", root->val);
}
int main() {
char preorder[] = "ABDECFG";
char inorder[] = "DBEAFCG";
TreeNode* root = buildTree(preorder, inorder, 0, 6, 0, 6);
printf("后序遍历结果为:");
postorder(root);
printf("\n");
return 0;
}
```
输出结果为:
```
后序遍历结果为:DEBFGCA
```
同时会打印出构建的二叉树,结构如下:
```
A
/ \
B C
/ \ / \
D E F G
```
阅读全文