给定一颗二叉树,要求输出遍历该二叉树得到的先序、中序、后序遍历序列。 输入 输入数据分为多组,第一行是测试数据的组数n,下面的n行分别代表一棵二叉树。每棵二叉树的结点均为正整数,数据为0代表当前结点为空,数据为-1代表二叉树数据输入结束,-1不作处理。二叉树的构造按照层次顺序(即第1层1个整数,第2层2个,第3层4个,第4层有8个......,如果某个结点不存在以0代替,总共不超过100) 输出 输出每棵二叉树的先序、中序、后序遍历序列,每个序列占一行。 样例输入 2 1 -1 1 2 3 4 5 0 6 -1 样例输出 1 1 1 1 2 4 5 3 6 4 2 5 1 3 6 4 5 2 6 3 1 提示 输出的每个节点值前有一个空格。C语言代码
时间: 2024-02-15 09:02:50 浏览: 24
好的,下面是使用C语言实现的代码,其中包括了二叉树的建立和三种遍历方式的实现:
```
#include<stdio.h>
#include<stdlib.h>
// 二叉树结点的定义
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 建立二叉树
TreeNode* createTree(int* nums, int i, int n) {
if (i >= n || nums[i] == 0) return NULL;
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = nums[i];
root->left = createTree(nums, 2*i+1, n);
root->right = createTree(nums, 2*i+2, n);
return root;
}
// 先序遍历
void preorder(TreeNode* root) {
if (root) {
printf("%d ", root->val);
preorder(root->left);
preorder(root->right);
}
}
// 中序遍历
void inorder(TreeNode* root) {
if (root) {
inorder(root->left);
printf("%d ", root->val);
inorder(root->right);
}
}
// 后序遍历
void postorder(TreeNode* root) {
if (root) {
postorder(root->left);
postorder(root->right);
printf("%d ", root->val);
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
int nums[100];
int num;
int i = 0;
while (1) {
scanf("%d", &num);
if (num == -1) break;
nums[i++] = num;
}
TreeNode* root = createTree(nums, 0, i);
preorder(root);
printf("\n");
inorder(root);
printf("\n");
postorder(root);
printf("\n");
}
return 0;
}
```
以上代码中,我们定义了一个 `TreeNode` 结构体,其中包括了结点值和左右子树指针。接着,我们使用 `createTree` 函数来建立二叉树,其实现过程是递归的。在建立好二叉树之后,我们分别使用 `preorder`、`inorder` 和 `postorder` 函数来进行三种遍历方式。最后,我们在每棵二叉树遍历结束后输出一个换行符,以便区分不同二叉树的遍历结果。