P1305 新二叉树

记录161#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间 int n; // 定义全局变量n表示二叉树的结点总数 int l[30],r[30]; // 定义大小为30的int数组用0-25的下标对应字母a-z的左右孩子 char root_char; // 用来保存整棵树的根节点字符 // 前序遍历函数根 - 左 - 右参数u是转化后的数字下标 void preOrder(int u){ if(u-1)return; // 递归终止条件如果下标为-1代表*空结点直接返回 coutchar(ua); // 将数字下标还原为字母并输出0aa preOrder(l[u]); // 递归遍历左子树 preOrder(r[u]); // 递归遍历右子树 } int main(){ // 主函数入口 ios::sync_with_stdio(false); // 关闭cin与stdio的同步加快输入输出速度 cin.tie(0); // 解除cin与cout的绑定进一步加快IO效率 cinn; // 输入二叉树的结点总数n char u,left,right; // 定义临时字符变量用来接收输入的根、左、右结点 for(int i0;in;i){ // 循环n次读入每个结点的子结点信息 cinuleftright; // 读入当前结点和它的左右儿子 if(i0)root_charu; // 题目保证第一行读入的节点必为根节点将其保存 // 核心映射将字母转化为数字下标。如果是*映射为-1作为空结点的标记 l[u-a](left*)?-1:(left-a); r[u-a](right*)?-1:(right-a); } preOrder(root_char-a); // 将根节点字符转化为数字下标开始进行前序遍历 return 0; // 主函数正常结束返回0 }题目传送门https://www.luogu.com.cn/problem/P1305前言我是一名专注信奥赛CSP-J/S、GESP的教练。如果你觉得这篇题解对你有帮助欢迎点击关注我的CSDN账号我会持续更新高质量算法解析。我深知算法思维的构建远比单纯通过题目更重要本系列题解不局限于AC代码的堆砌而是致力于拆解题目背后的逻辑链条与核心知识点备赛路上若遇瓶颈欢迎随时评论或私信我将甄选典型疑难问题通过视频讲解或撰写专项文章的形式为你提供深度答疑。核心解题思路这道题是一道非常经典的二叉树基础与递归遍历问题。问题转化字符到数字的映射题目输入的是字母形式的节点如a,b,c在 C 中如果直接用字符作为数组下标会比较麻烦。因此我们利用 ASCII 码的特性将字母a~z映射为数字0~25即u - a。这样我们就可以使用简单的整型数组来存储每个节点的左右孩子。算法设计前序遍历的递归实现前序遍历的规则是“根节点 →→ 左子树 →→ 右子树”。在代码中我们通过递归函数来实现首先访问当前节点输出当前节点的字母。然后递归调用函数去遍历左子树。最后递归调用函数去遍历右子树。题目保证第一行输入的必定是根节点因此我们只需从根节点开始调用前序遍历函数即可。代码分块详细解释1. 头文件、全局变量与数组定义#includebits/stdc.h // 引入万能头文件包含所有常用的标准库 using namespace std; // 使用标准命名空间 int n; // 定义全局变量n表示二叉树的结点总数 int l[30], r[30]; // 定义大小为30的int数组用0-25的下标对应字母a-z的左右孩子 char root_char; // 用来保存整棵树的根节点字符详细分析由于题目说明节点由字母a~z组成最多 26 个节点所以定义大小为 30 的数组l和r绰绰有余。l[i]存储字母ia的左孩子对应的数字下标r[i]存储右孩子对应的数字下标。全局变量root_char用于记录树的根节点。2. 核心逻辑前序遍历递归函数// 前序遍历函数根 - 左 - 右参数u是转化后的数字下标 void preOrder(int u){ if(u -1) return; // 递归终止条件如果下标为-1代表*空结点直接返回 cout char(u a); // 将数字下标还原为字母并输出0aa preOrder(l[u]); // 递归遍历左子树 preOrder(r[u]); // 递归遍历右子树 }详细分析这是二叉树遍历的灵魂。边界处理输入中的*代表空节点。我们在建树时将*映射为-1。当递归遇到-1时说明当前分支为空直接return回溯。访问根节点cout char(u a);将数字下标还原为对应的字母并立即输出这完美契合了前序遍历“先访问根”的规则。递归子树随后依次对左孩子l[u]和右孩子r[u]发起递归调用。3. 主函数数据读入与建树映射int main(){ ios::sync_with_stdio(false); // 关闭cin与stdio的同步加快输入输出速度 cin.tie(0); // 解除cin与cout的绑定进一步加快IO效率 cin n; // 输入二叉树的结点总数n char u, left, right; // 定义临时字符变量用来接收输入的根、左、右结点 for(int i 0; i n; i){ // 循环n次读入每个结点的子结点信息 cin u left right; // 读入当前结点和它的左右儿子 if(i 0) root_char u; // 题目保证第一行读入的节点必为根节点将其保存 // 核心映射将字母转化为数字下标。如果是*映射为-1作为空结点的标记 l[u - a] (left *) ? -1 : (left - a); r[u - a] (right *) ? -1 : (right - a); }详细分析这部分完成了从“字符描述”到“数组存储”的转换。利用三目运算符(条件) ? 值1 : 值2非常优雅地处理了空节点*的映射。如果输入是*则赋值为-1否则利用left - a将字母转化为对应的数字下标。题目明确说明第一行读入的必为根节点所以i0时记录根节点即可。4. 启动遍历与程序结束preOrder(root_char - a); // 将根节点字符转化为数字下标开始进行前序遍历 return 0; // 主函数正常结束返回0 }详细分析将根节点的字符转化为数字下标后作为参数传入preOrder函数启动整棵树的遍历。核心逻辑总结表代码模块核心变量/操作精炼作用解决的痛点字符映射u - a将字母节点转化为 0~25 的整数下标避免了使用复杂的 map 或字符数组下标简化了树的存储空节点标记(left*) ? -1 : ...将代表空节点的*映射为 -1为递归遍历提供了明确的终止条件边界处理根节点记录if(i0) root_charu锁定遍历的起始点确保前序遍历能从正确的根节点开始前序遍历cout ...; preOrder(l); preOrder(r);严格按照“根 →→ 左 →→ 右”的顺序递归完美实现了二叉树的前序遍历逻辑IO加速ios::sync_with_stdio(false)关闭 C 与 C 的标准流同步防止在递归输出大量字符时因 IO 瓶颈导致超时