写一个能将二叉树的前序遍历和中序遍历转为后序遍历的C++程序
时间: 2023-05-26 22:01:46 浏览: 59
#include <stdio.h>
#include <stdlib.h>
/*定义二叉树结构体*/
struct TreeNode {
char val;
struct TreeNode *left;
struct TreeNode *right;
};
/*创建二叉树*/
struct TreeNode* buildTree(char* preorder, char* inorder, int inorder_start, int inorder_end) {
static int preorder_index = 0; // 静态变量,记录前序遍历数组的索引位置
// 如果中序遍历的开始位置大于结束位置,表示当前二叉树为空
if (inorder_start > inorder_end) {
return NULL;
}
// 创建当前根节点,并将其值赋为前序遍历数组中的下一个元素
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = preorder[preorder_index++];
// 在中序遍历数组中搜索当前根节点的位置
int inorder_index;
for (int i = inorder_start; i <= inorder_end; i++) {
if (inorder[i] == root->val) {
inorder_index = i;
break;
}
}
// 递归构建当前根节点的左子树和右子树
root->left = buildTree(preorder, inorder, inorder_start, inorder_index-1);
root->right = buildTree(preorder, inorder, inorder_index+1, inorder_end);
return root;
}
/*后序遍历二叉树*/
void postorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%c ", root->val);
}
int main() {
char preorder[] = {'A', 'B', 'D', 'E', 'C', 'F'};
char inorder[] = {'D', 'B', 'E', 'A', 'F', 'C'};
int len = sizeof(preorder) / sizeof(char);
struct TreeNode* root = buildTree(preorder, inorder, 0, len-1);
printf("后序遍历结果为:");
postorderTraversal(root);
return 0;
}