新二叉树（洛谷P1305）
题目描述
输入一串二叉树，输出其前序遍历。
输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，第一个字母为节点，后两个字母分别为其左右儿子。特别地，数据保证第一行读入的节点必为根节点。
空节点用*表示
输出格式
二叉树的前序遍历。
输入输出样例
输入 #1复制运行
6 abc bdi cj* d** i** j**
输出 #1复制运行
abdicj
核心逻辑：
在处理二叉树时，初学者习惯用k*2/k*2+1存储左右儿子。但这种顺序存储遇到世代单传子树（只有单边子树的深树）会使下标呈指数级爆炸。
本方案采用静态链表思路：用结构体数组存节点，配合一个计数器cnt分配空间。无论树长成什么样，空间复杂度始终稳定在O(N)。
实现步骤
定义结构：每个
node记录l和r的数组下标，而不是物理地址。动态赋值：
第一行输入确定根节点
tre[1]。后续输入格式为
父节点 左孩子 右孩子。
暴力查找（核心）：
每次读入一行，就去数组里扫一遍，找到那个 data 匹配的节点，然后把它的 l 和 r 指向新分配的 cnt 位置。
递归输出：标准的先序遍历（根->左->右）。
关键点
关于
*的处理：输入如果是*代表空，就不给它分配cnt下标，直接跳过即可。查找效率：目前代码找父节点用的是O(N)$遍历，对于N=2000的题足够了，但如果节点上万，建议换成
unordered_map来秒查位置。空间预留：
tre[2000]的大小要根据题目N的范围来定，不开太小,也不开太大。
总结
“数组模拟链表”的做法是竞赛里的“万金油”，既能省去new内存的耗时，又能防止顺序存储的内存溢出。
完整代码
//用链式存储 顺序存储如果是世代单纯 效率太低 #include <iostream> using namespace std; string a; struct node{ int l; int r; char data; }tre[2000]; void preorder(int root){ cout<<tre[root].data; if(tre[root].l) preorder(tre[root].l); if(tre[root].r) preorder(tre[root].r); } int main(){ int n; cin>>n; int cnt=1;//代表存进树中的节点数 cin>>a; //第一行必为根节点，先单独赋值 tre[1].data=a[0]; if(a[1]!='*'){//代表有左儿子 tre[1].l=++cnt; tre[cnt].data=a[1]; } if(a[2]!='*'){//代表有右儿子 tre[1].r=++cnt; tre[cnt].data=a[2]; } for(int i=2;i<=n;i++){ cin>>a; for(int i=1;i<=cnt;i++){ if(tre[i].data==a[0]){//找这次读入的匹配树中哪一个节点 if(a[1]!='*'){//代表有左儿子 tre[i].l=++cnt; tre[cnt].data=a[1]; } if(a[2]!='*'){//代表有右儿子 tre[i].r=++cnt; tre[cnt].data=a[2]; } } } } preorder(1); return 0; }