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

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

题目

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

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

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

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

输出样例：
1
2
4
3
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* index, int n) {if (*index >= n || strcmp(tokens[*index], "#") == 0) {(*index)++;return NULL;}TreeNode* node = createNode(atoi(tokens[*index]));(*index)++;node->left = buildTree(tokens, index, n);node->right = buildTree(tokens, index, n);return node;
}// 前序遍历二叉树（根-左-右）
void preOrderTraversal(TreeNode* root) {if (root == NULL) return;printf("%d\n", root->data);preOrderTraversal(root->left);preOrderTraversal(root->right);
}int main() {int n;scanf("%d", &n);// 消耗掉scanf后的换行符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");}int index = 0;TreeNode* root = buildTree(tokens, &index, n);preOrderTraversal(root);return 0;
}