【PTA数据结构 | C语言版】根据层序序列重构二叉树

本专栏持续输出数据结构题目集，欢迎订阅。

题目

请编写程序，根据给定二叉树的层序序列化结果，重构二叉树，并输出其层序遍历结果。

输入格式：
输入首先给出一个不超 20 的正整数 n，随后一行给出 n 个层序序列的元素。其中键值都是不超过 9 位的正整数，空结点对应符号 #。

输出格式：
输出二叉树的层序遍历结果，每个数字占一行。

输入样例：
11
1 2 3 # 4 5 # # # # #

输出样例：
1
2
3
4
5

代码

#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct TreeNode {int data;struct TreeNode *left;struct TreeNode *right;
} TreeNode;TreeNode* createNode(int data) {TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));node->data = data;node->left = NULL;node->right = NULL;return node;
}TreeNode* buildTree(char** tokens, int n) {if (n == 0 || strcmp(tokens[0], "#") == 0) return NULL;TreeNode* root = createNode(atoi(tokens[0]));TreeNode* queue[1000];int front = 0, rear = 0;queue[rear++] = root;int i = 1;while (i < n && front < rear) {TreeNode* current = queue[front++];// 处理左子节点if (i < n && strcmp(tokens[i], "#") != 0) {current->left = createNode(atoi(tokens[i]));queue[rear++] = current->left;}i++;// 处理右子节点if (i < n && strcmp(tokens[i], "#") != 0) {current->right = createNode(atoi(tokens[i]));queue[rear++] = current->right;}i++;}return root;
}void levelOrderTraversal(TreeNode* root) {if (root == NULL) return;TreeNode* queue[1000];int front = 0, rear = 0;queue[rear++] = root;while (front < rear) {TreeNode* current = queue[front++];printf("%d\n", current->data);if (current->left != NULL) queue[rear++] = current->left;if (current->right != NULL) queue[rear++] = current->right;}
}void freeTree(TreeNode* root) {if (root == NULL) return;freeTree(root->left);freeTree(root->right);free(root);
}int main() {int n;scanf("%d", &n);getchar();  // 消耗换行符char input[1000];fgets(input, sizeof(input), stdin);char* tokens[100];int count = 0;char* token = strtok(input, " \n");while (token != NULL && count < n) {tokens[count++] = token;token = strtok(NULL, " \n");}TreeNode* root = buildTree(tokens, n);levelOrderTraversal(root);freeTree(root);return 0;
}