C语言实现根据前序遍历和中序遍历构建二叉树
时间: 2023-06-03 18:07:36 浏览: 72
好的,我可以回答这个问题。构建二叉树的过程可以分为两步:1. 根据前序遍历确定根节点;2. 根据中序遍历确定左子树和右子树。这样,我们就可以递归的构建整棵树。具体的实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 树的节点结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 根据前序遍历和中序遍历构建二叉树
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];
root->left = NULL;
root->right = NULL;
// 在中序遍历中找到根节点的位置
int rootIndex;
for (rootIndex = 0; rootIndex < inorderSize; rootIndex++) {
if (inorder[rootIndex] == preorder[0]) {
break;
}
}
// 递归构建左子树和右子树
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 preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
// 中序遍历
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
// 后序遍历
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, 7};
int inorder[] = {4, 2, 5, 1, 6, 3, 7};
int size = sizeof(preorder) / sizeof(int);
TreeNode* root = buildTree(preorder, size, inorder, size);
printf("先序遍历: ");
preorderTraversal(root);
printf("\n中序遍历: ");
inorderTraversal(root);
printf("\n后序遍历: ");
postorderTraversal(root);
return 0;
}
```
输出结果为:
```c
先序遍历: 1 2 4 5 3 6 7
中序遍历: 4 2 5 1 6 3 7
后序遍历: 4 5 2 6 7 3 1
```
希望我的回答能够帮助到您!