输入格式: 首先输入一个整数T,表示测试数据的组数,然后是T组测试数据。每组测试数据在一行中输入一个字符串(不含空格且长度不超过80),表示二叉树的先序遍历序列(其中@表示虚结点)。 输出格式: 对于每组测试,输出层次遍历的结果。
时间: 2024-10-09 15:04:30 浏览: 40
Java实现OJ多组测试数据的输入方法
5星 · 资源好评率100%
在C语言中,你可以使用递归和栈来解决这个问题。给定二叉树的先序遍历序列(含虚拟节点@),我们需要根据这个顺序构建并层次遍历整个树。层次遍历也被称为宽度优先搜索(BFS)。以下是一个基本的解决方案:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct TreeNode {
char data;
struct TreeNode *left, *right;
} TreeNode;
TreeNode* buildTree(char* preorder) {
int i = 0, n = strlen(preorder);
if (n == 0) return NULL;
// 找到当前节点的位置
while (preorder[i] != '@') i++;
// 创建新节点
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = preorder[0];
root->left = root->right = NULL;
// 递归构建左右子树
root->left = buildTree(preorder + 1); // 假设左孩子在后继位置
root->right = buildTree(preorder + i + 1); // 剩余的都是右孩子
return root;
}
void levelOrderTraversal(TreeNode* root, int level, char str[]) {
if (root == NULL) return;
if (level == 0) { // 层级为0时,添加根节点到结果数组
str[level] = root->data;
str[level+1] = '\0';
printf("%s\n", str);
} else {
levelOrderTraversal(root->left, level - 1, str);
levelOrderTraversal(root->right, level - 1, str);
}
}
int main() {
int T;
scanf("%d", &T);
for (int t = 0; t < T; t++) {
char preorder[90]; // 保证至少能存储80个字符和一个终止符
fgets(preorder, sizeof(preorder), stdin); // 防止读取换行符
preorder[strlen(preorder) - 1] = '\0'; // 去除末尾的换行符
TreeNode* root = buildTree(preorder);
char result[90]; // 存储层次遍历结果
memset(result, 0, sizeof(result)); // 初始化为0防止乱码
// 层次遍历
levelOrderTraversal(root, 0, result);
// 输出结果
printf("Case %d: %s\n", t+1, result);
}
return 0;
}
```
在这个程序中,我们首先定义了一个`buildTree`函数用于从先序遍历序列创建二叉树,然后用`levelOrderTraversal`函数进行层次遍历。`main`函数处理测试数据和循环次数。
运行此程序时,请确保提供每个测试案例的先序遍历序列,每个案例之间用换行符分隔。
阅读全文