已知一个二叉树的中序遍历序列和后序遍历序列,求这棵树的前序遍历序列。c语言 【输入形式】 一个树的中序遍历序列 该树后序遍历序列,中间用空格分开。输入序列中仅含有小写字母,且没有重复的字母 【输出形式】 一个树的前序遍历序列
时间: 2024-05-08 20:18:33 浏览: 97
C++数据结构已知二叉树的前序遍历与中序遍历结果求后序遍历.pdf
5星 · 资源好评率100%
听起来像是道经典的二叉树遍历问题呢!根据已知条件,我们可以用递归的方法来构建这棵二叉树,再进行前序遍历即可求出答案。以下是我编写的 C 代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_SIZE 100
typedef struct TreeNode {
char value;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
void initNode(TreeNode *node, char value) {
node->value = value;
node->left = NULL;
node->right = NULL;
}
void freeTree(TreeNode *root) {
if (root == NULL) {
return;
}
freeTree(root->left);
freeTree(root->right);
free(root);
}
TreeNode *buildTree(char *inorder, char *postorder, int len) {
if (len <= 0) {
return NULL;
}
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
initNode(node, postorder[len-1]);
int i;
for (i = 0; i < len; i++) {
if (inorder[i] == postorder[len-1]) {
break;
}
}
node->left = buildTree(inorder, postorder, i);
node->right = buildTree(inorder+i+1, postorder+i, len-i-1);
return node;
}
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
printf("%c ", root->value);
preOrder(root->left);
preOrder(root->right);
}
int main() {
char inorder[MAX_SIZE], postorder[MAX_SIZE];
scanf("%s %s", inorder, postorder);
int len = strlen(inorder);
TreeNode *root = buildTree(inorder, postorder, len);
preOrder(root);
freeTree(root);
return 0;
}
```
根据题意,我们首先读入中序遍历和后序遍历序列,然后根据递归的思想来构建这棵二叉树,最后进行前序遍历即可得到答案。祝你顺利解题!
阅读全文