广州网站建设 易点wordpress ip 插件

广州网站建设 易点,wordpress ip 插件,重庆市建设工程安全管理网站,网站 建设初步题目描述输入一串二叉树#xff0c;输出其前序遍历。输入格式第一行为二叉树的节点数 n。(1≤n≤26)后面 n 行#xff0c;第一个字母为节点#xff0c;后两个字母分别为其左右儿子。特别地#xff0c;数据保证第一行读入的节点必为根节点。空节点用 * 表示输出格式二叉树的…题目描述输入一串二叉树输出其前序遍历。输入格式第一行为二叉树的节点数 n。(1≤n≤26)后面 n 行第一个字母为节点后两个字母分别为其左右儿子。特别地数据保证第一行读入的节点必为根节点。空节点用*表示输出格式二叉树的前序遍历。输入输出样例输入 #1复制运行6 abc bdi cj* d** i** j**输出 #1复制运行abdicj核心逻辑在处理二叉树时初学者习惯用k*2/k*21存储左右儿子。但这种顺序存储遇到世代单传子树只有单边子树的深树会使下标呈指数级爆炸。本方案采用静态链表思路用结构体数组存节点配合一个计数器cnt分配空间。无论树长成什么样空间复杂度始终稳定在O(N)。实现步骤定义结构每个node记录l和r的数组下标而不是物理地址。动态赋值第一行输入确定根节点tre[1]。后续输入格式为父节点 左孩子 右孩子。暴力查找核心每次读入一行就去数组里扫一遍找到那个 data 匹配的节点然后把它的 l 和 r 指向新分配的 cnt 位置。递归输出标准的先序遍历根-左-右。关键点关于*的处理输入如果是*代表空就不给它分配cnt下标直接跳过即可。查找效率目前代码找父节点用的是O(N)$遍历对于N2000的题足够了但如果节点上万建议换成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){ couttre[root].data; if(tre[root].l) preorder(tre[root].l); if(tre[root].r) preorder(tre[root].r); } int main(){ int n; cinn; int cnt1;//代表存进树中的节点数 cina; //第一行必为根节点先单独赋值 tre[1].dataa[0]; if(a[1]!*){//代表有左儿子 tre[1].lcnt; tre[cnt].dataa[1]; } if(a[2]!*){//代表有右儿子 tre[1].rcnt; tre[cnt].dataa[2]; } for(int i2;in;i){ cina; for(int i1;icnt;i){ if(tre[i].dataa[0]){//找这次读入的匹配树中哪一个节点 if(a[1]!*){//代表有左儿子 tre[i].lcnt; tre[cnt].dataa[1]; } if(a[2]!*){//代表有右儿子 tre[i].rcnt; tre[cnt].dataa[2]; } } } } preorder(1); return 0; }