洛谷 P1305：新二叉树 ← DFS + 字符索引数组 + map

​【题目来源】https://www.luogu.com.cn/problem/P1305【题目描述】输入一串二叉树输出其前序遍历。【输入格式】第一行为二叉树的节点数 n。(1≤n≤26)后面 n 行第一个字母为节点后两个字母分别为其左右儿子。特别地数据保证第一行读入的节点必为根节点。空节点用 * 表示。【输出格式】二叉树的前序遍历。【输入样例】6abcbdicj*d**i**j**【输出样例】abdicj【数据范围】1≤n≤26【算法分析】● 字符可以作为数组下标这本质上是因为“字符类型”可以被隐式或显式地转换为“整数类型”。​ 在计算机内部字符是以其对应的整型编码值如 ASCII 或 Unicode 码点来存储和处理的。因此当你使用一个字符作为数组下标时编译器会自动将其转换为对应的整数并用这个整数来索引数组。● 语句mapchar,char ls,rs;在代码中提供了一个灵活、安全的键值存储用于表示二叉树中每个节点到其左右孩子节点的映射关系。相比固定大小的数组它避免了因字符 ASCII 码范围不确定而可能导致的数组越界问题详见https://blog.csdn.net/hnjzsyjyj/article/details/160991953是处理此类映射问题的更通用、更安全的方案。【算法代码】#includebits/stdc.h using namespace std; mapchar,char ls,rs; char root; void dfs(char rt) { if(rt*) return; coutrt; dfs(ls[rt]); dfs(rs[rt]); } int main() { int n; cinn; for(int i1; in; i) { char rt,le,ri; cinrtleri; if(i1) rootrt; ls[rt]le; rs[rt]ri; } dfs(root); return 0; } /* in: 6 abc bdi cj* d** i** j** out: abdicj */【参考文献】https://blog.csdn.net/hnjzsyjyj/article/details/160515496https://blog.csdn.net/hnjzsyjyj/article/details/160991953​