已知二叉树的先序遍历和中序遍历,求二叉树的后序遍历。 如:二叉树的先序遍历为abdec,中序遍历为dbcae,求后序遍历。 请用C语言实现上述实验项目
时间: 2024-10-13 14:02:38 浏览: 40
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
5星 · 资源好评率100%
要实现这个功能,我们可以先根据先序遍历和中序遍历的结果构建二叉树,然后进行后序遍历。以下是C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
TreeNode* buildTree(char* preorder, char* inorder, int len) {
if (len == 0) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
int i;
for (i = 0; i < len; i++) {
if (inorder[i] == preorder[0]) break;
}
root->left = buildTree(preorder + 1, inorder, i);
root->right = buildTree(preorder + i + 1, inorder + i + 1, len - i - 1);
return root;
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c", root->val);
}
int main() {
char preorder[] = "abdec";
char inorder[] = "dbcae";
int len = strlen(preorder);
TreeNode* root = buildTree(preorder, inorder, len);
postorderTraversal(root);
return 0;
}
```
这段代码首先定义了一个二叉树结构体`TreeNode`,然后实现了两个函数:`buildTree`用于根据先序遍历和中序遍历的结果构建二叉树,`postorderTraversal`用于进行后序遍历。在`main`函数中,我们调用这两个函数来完成任务。
阅读全文