用C语言解决给定一棵满二叉树树先序遍历的输出结果,求该树中序遍历的输出结果。
时间: 2023-09-25 12:15:57 浏览: 85
二叉树的遍历输出c语言
3星 · 编辑精心推荐
假设满二叉树的节点结构体如下:
```c
typedef struct Node {
int val; // 节点值
Node *left; // 左子节点
Node *right; // 右子节点
} Node;
```
先序遍历的输出结果存储在一个数组中,我们可以通过递归的方式构建二叉树,并在递归过程中进行中序遍历输出。
具体实现如下:
```c
void buildTree(Node **node, int *preorder, int start, int end, int *index) {
if (start > end) {
*node = NULL;
return;
}
// 构造当前节点
*node = (Node*)malloc(sizeof(Node));
(*node)->val = preorder[*index];
(*node)->left = NULL;
(*node)->right = NULL;
(*index)++;
if (start == end) {
return;
}
int mid = (start + end) / 2;
buildTree(&((*node)->left), preorder, start, mid, index);
buildTree(&((*node)->right), preorder, mid + 1, end, index);
}
void inorderTraversal(Node *node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%d ", node->val);
inorderTraversal(node->right);
}
int main() {
int preorder[] = {1, 2, 4, 5, 3, 6, 7};
int n = sizeof(preorder) / sizeof(preorder[0]);
int index = 0;
Node *root = NULL;
buildTree(&root, preorder, 0, n - 1, &index);
inorderTraversal(root);
return 0;
}
```
输出结果为:`4 2 5 1 6 3 7`。
阅读全文