给出一棵二叉树的中序遍历和前序遍历,求它的后序遍历,请给出完整c语言代码
时间: 2023-07-24 08:11:16 浏览: 119
下面是给出的二叉树结构体定义和求解后序遍历的完整C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int search(int arr[], int start, int end, int value) {
int i;
for (i = start; i <= end; i++) {
if (arr[i] == value) {
return i;
}
}
return -1;
}
TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {
if (preorderSize <= 0 || inorderSize <= 0) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
int rootIndex = search(inorder, 0, inorderSize - 1, root->val);
root->left = buildTree(preorder + 1, rootIndex, inorder, rootIndex);
root->right = buildTree(preorder + rootIndex + 1, preorderSize - rootIndex - 1, inorder + rootIndex + 1, inorderSize - rootIndex - 1);
return root;
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
int main() {
int preorder[] = {1, 2, 4, 5, 3, 6};
int inorder[] = {4, 2, 5, 1, 3, 6};
int size = sizeof(preorder) / sizeof(int);
TreeNode* root = buildTree(preorder, size, inorder, size);
printf("The postorder traversal of the binary tree is: ");
postorderTraversal(root);
printf("\n");
return 0;
}
```
上述代码中,search函数用于在中序遍历数组中找到根节点的位置;buildTree函数用于递归构建二叉树;postorderTraversal函数用于递归遍历二叉树并输出后序遍历结果。在主函数中,我们给出了一个示例,构建了一棵二叉树,并输出了它的后序遍历结果。
阅读全文