C语言用先序中序构建二叉树
时间: 2023-10-21 09:12:27 浏览: 45
在 C 语言中,可以使用递归的方法来实现先序中序构建二叉树。具体步骤如下:
1. 定义二叉树节点类型,包含节点值、左子树指针和右子树指针。
```c
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};
```
2. 编写递归函数 `buildTree()`,接收先序遍历序列 `preorder`、中序遍历序列 `inorder` 和序列长度 `len` 作为参数。该函数返回构建好的二叉树的根节点。
3. 在 `buildTree()` 中,首先定义变量 `root` 作为当前子树的根节点,其值为先序遍历序列的第一个元素。然后在中序遍历序列中查找到 `root` 的位置,将序列分为左子树和右子树。
4. 接着,使用递归的方式分别构建左子树和右子树,并将其分别作为 `root` 的左子树和右子树。
代码实现如下:
```c
struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
if (preorderSize == 0 || inorderSize == 0) {
return NULL;
}
struct TreeNode *root = (struct TreeNode *)malloc(sizeof(struct TreeNode));
root->val = preorder[0];
int i = 0;
for (; i < inorderSize; i++) {
if (inorder[i] == root->val) {
break;
}
}
root->left = buildTree(preorder+1, i, inorder, i);
root->right = buildTree(preorder+1+i, preorderSize-i-1, inorder+i+1, inorderSize-i-1);
return root;
}
```
在调用 `buildTree()` 函数时,需要将先序遍历序列 `preorder`、中序遍历序列 `inorder` 和序列长度 `len` 作为参数传入。例如,构建先序遍历序列为 `{3,9,20,15,7}`,中序遍历序列为 `{9,3,15,20,7}` 的二叉树,可以这样调用:
```c
int preorder[] = {3,9,20,15,7};
int inorder[] = {9,3,15,20,7};
struct TreeNode *root = buildTree(preorder, 5, inorder, 5);
```