用c语言中序建立一棵二叉树
时间: 2023-10-04 20:06:02 浏览: 42
我们可以使用结构体来定义二叉树节点,包括节点值,左右子树指针。然后通过递归的方式来构建二叉树。
下面是示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
};
// 递归构建二叉树
struct TreeNode* buildTree(int* inorder, int inorderSize, int* postorder, int postorderSize) {
// 如果中序遍历序列为空,返回空节点
if (inorderSize == 0) {
return NULL;
}
// 新建根节点
struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
root->val = postorder[postorderSize - 1];
// 找到根节点在中序遍历序列中的索引
int index = 0;
for (int i = 0; i < inorderSize; i++) {
if (inorder[i] == root->val) {
index = i;
break;
}
}
// 递归构建左右子树
root->left = buildTree(inorder, index, postorder, index);
root->right = buildTree(inorder + index + 1, inorderSize - index - 1, postorder + index, postorderSize - index - 1);
return root;
}
// 中序遍历二叉树
void inorderTraversal(struct TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
int main() {
int inorder[] = { 9, 3, 15, 20, 7 };
int postorder[] = { 9, 15, 7, 20, 3 };
int size = sizeof(inorder) / sizeof(inorder[0]);
struct TreeNode* root = buildTree(inorder, size, postorder, size);
inorderTraversal(root);
return 0;
}
```
这里我们以中序遍历和后序遍历序列构建二叉树,并且输出中序遍历结果。可以根据需要更改遍历方式和输入序列类型。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)