已知一个二叉树,由前序遍历和后序遍历构建二叉树的C语言代码
时间: 2023-11-23 07:05:57 浏览: 68
二叉树遍历的还原
以下是由前序遍历和后序遍历构建二叉树的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) {
for (int 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) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = preorder[0];
if (preorderSize == 1) {
root->left = NULL;
root->right = NULL;
return root;
}
int index = search(inorder, 0, inorderSize - 1, preorder[0]);
int leftSize = index;
int rightSize = inorderSize - index - 1;
root->left = buildTree(preorder + 1, leftSize, inorder, leftSize);
root->right = buildTree(preorder + leftSize + 1, rightSize, inorder + index + 1, rightSize);
return root;
}
void postorder(TreeNode* root) {
if (root == NULL) {
return;
}
postorder(root->left);
postorder(root->right);
printf("%d ", root->val);
}
int main() {
int preorder[] = { 1, 2, 4, 5, 3, 6, 7 };
int inorder[] = { 4, 2, 5, 1, 6, 3, 7 };
int size = sizeof(preorder) / sizeof(preorder[0]);
TreeNode* root = buildTree(preorder, size, inorder, size);
printf("The postorder traversal of the constructed binary tree is: ");
postorder(root);
return 0;
}
```
这个代码会构建一个二叉树,然后输出后序遍历的结果。你可以将前序遍历和后序遍历的数组改成你需要的输入。
阅读全文