二叉树的先序遍历为abdec,中序遍历为dbcae,求后序遍历,请用C语言实现上述实验项目,运行程序
时间: 2024-10-12 17:06:18 浏览: 30
Python实现输入二叉树的先序和中序遍历,再输出后序遍历操作示例
5星 · 资源好评率100%
二叉树的后序遍历是先访问左子树,然后访问右子树,最后访问根节点。根据给定的先序遍历和中序遍历,我们可以重建二叉树,然后进行后序遍历。
以下是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 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 = sizeof(preorder) - 1;
TreeNode* root = buildTree(preorder, inorder, len);
postorderTraversal(root);
return 0;
}
```
运行上述程序,可以得到后序遍历的结果。
阅读全文