P1185 绘制二叉树网页链接P1185 绘制二叉树题目描述二叉树是一种基本的数据结构它要么为空要么由根结点左子树和右子树组成同时左子树和右子树也分别是二叉树。当一颗二叉树高度为m − 1 m-1m−1时共有m mm层。若一棵二叉树除第m mm层外其他各层的结点数都达到最大且叶子结点都在第m mm层时则其为一棵满二叉树。现在需要你用程序来绘制一棵二叉树它由一棵满二叉树去掉若干结点而成。对于一棵满二叉树我们需要按照以下要求绘制结点用小写字母o表示对于一个父亲结点用/连接左子树用\连接右子树。定义[ i , j ] [i,j][i,j]为位于第i ii行第j jj列的某个字符。若[ i , j ] [i,j][i,j]为/那么[ i − 1 , j 1 ] [i-1,j1][i−1,j1]与[ i 1 , j − 1 ] [i1,j-1][i1,j−1]要么为o要么为/。若[ i , j ] [i,j][i,j]为\那么[ i − 1 , j − 1 ] [i-1,j-1][i−1,j−1]与[ i 1 , j 1 ] [i1,j1][i1,j1]要么为o要么为\。同样若[ i , j ] [i,j][i,j]为第1 ∼ m − 1 1\sim m-11∼m−1层的某个结点o那么[ i 1 , j − 1 ] [i1,j-1][i1,j−1]为/[ i 1 , j 1 ] [i1,j1][i1,j1]为\。对于第m mm层结点也就是叶子结点若两个属于同一个父亲那么它们之间由3 33个空格隔开若两个结点相邻但不属于同一个父亲那么它们之间由1 11个空格隔开。第m mm层左数第1 11个结点之前没有空格。最后需要在一棵绘制好的满二叉树上删除n nn个结点包括这个结点的左右子树以及与父亲的连接原有的字符用空格替换空格为ASCII 32若输出ASCII 0会被算作错误答案。输入格式第1 11行包含2 22个正整数m mm和n nn为需要绘制的二叉树层数和需要删除的结点数。接下来n nn行每行两个正整数表示删除第i ii层的第j jj个结点。输出格式按照题目要求绘制的二叉树。输入输出样例 #1输入 #12 0输出 #1o / \ o o输入输出样例 #2输入 #24 0输出 #2o / \ / \ / \ / \ / \ o o / \ / \ / \ / \ o o o o / \ / \ / \ / \ o o o o o o o o输入输出样例 #3输入 #34 3 3 2 4 1 3 4输出 #3o / \ / \ / \ / \ / \ o o / / / / o o \ / \ o o o说明/提示30 % 30\%30%的数据满足n 0 n0n050 % 50\%50%的数据满足2 ≤ m ≤ 5 2\le m\le 52≤m≤5100 % 100\%100%的数据满足2 ≤ m ≤ 10 , 0 ≤ n ≤ 10 , 1 i ≤ M , j ≤ 2 i − 1 2\le m\le10,0\le n\le 10,1i\le M,j\le 2^{i-1}2≤m≤10,0≤n≤10,1i≤M,j≤2i−1。解题思路本题是图形绘制 递归模拟问题。需要根据给定的满二叉树层数m mm和要删除的节点列表绘制出对应的字符画。满二叉树的节点用o表示连接线用/和\表示删除的节点及其子树用空格替代。由于二叉树层数m ≤ 10 m \le 10m≤10画布尺寸最大约为12 × 23 12 \times 2312×23规模很小可以采用递归方式逐行逐列绘制。1. 问题等价转化满二叉树共有m mm层第i ii层有2 i − 1 2^{i-1}2i−1个节点。整个图形呈对称的三角形结构。画布行数n和列数m的计算当m 1 m1m1时只有根节点画布为1 × 1 1 \times 11×1。当m ≥ 2 m \ge 2m≥2时行数n 3 * 2^{m-2}列数m 6 * 2^{m-2} - 1。节点和连接线的位置关系根节点位于第1 11行中间列。对于某个节点其左子节点在下一行的左侧右子节点在下一行的右侧。节点与子节点之间用斜线连接斜线是阶梯状延伸每行移动一列。删除节点若某节点被标记删除则不再绘制该节点及其所有后代对应的位置保持空格。2. 算法实现递归绘制代码采用递归函数dfs1(x, y, a, b, k, xx, yy)完成绘制参数含义x, y当前要绘制的字符在画布中的行、列坐标。a, b用于控制斜线绘制的进度。a表示当前斜线已绘制的行数b表示到达子节点所需的总行数。k当前绘制状态。1表示绘制节点o2表示绘制左斜线/3表示绘制右斜线\。xx, yy当前节点在二叉树中的层号和该层的序号用于查询是否被删除。递归逻辑状态 1节点在(x, y)处写入o。计算左子节点的位置层号xx1序号(yy-1)*21行坐标x1列坐标y-1。计算右子节点的位置层号xx1序号yy*2行坐标x1列坐标y1。检查子节点是否被删除通过f[层][序号]标记。若未删除则递归调用状态转为对应的斜线左斜线k2右斜线k3并重置斜线进度a1, bnn为总行数。状态 2左斜线/在(x, y)处写入/。判断是否到达子节点若a*2 b说明斜线结束下一步应绘制节点递归调用状态k1否则继续绘制斜线行坐标x1列坐标y-1进度a1。状态 3右斜线\在(x, y)处写入\。类似地若a*2 b转为节点状态否则继续斜线行坐标x1列坐标y1进度a1。删除标记使用二维布尔数组f[层][序号]记录被删除的节点。在主函数中读入删除信息并置为true。递归时在计算子节点位置后先检查f[子层][子序号]是否为true。若是则跳过该子树的绘制这样该位置保持初始的空格。画布初始化创建二维字符数组c[800][1600]全部初始化为空格 。根据层数m计算画布实际行数n和列数m注意变量名冲突代码中m先被用作层数后被用作列数但逻辑正确。调用dfs1(1, 列数/21, 1, 行数, 1, 1, 1)开始绘制。特殊处理当层数m 1时画布为1 × 1 1 \times 11×1直接输出o。3. 复杂度分析时间复杂度每个未删除的节点和斜线都会被绘制一次。满二叉树的节点总数为2 m − 1 2^m - 12m−1斜线数量与节点数同阶。m ≤ 10 m \le 10m≤10总节点数最多1023 10231023绘制操作约几千次非常快。空间复杂度画布大小最大为12 × 23 12 \times 2312×23当m 10 m10m10时行数3 × 2 8 768 3 \times 2^8 7683×28768实际计算m 10 m10m10时n 3 × 2 8 768 n 3 \times 2^8 768n3×28768列数m 6 × 2 8 − 1 1535 m 6 \times 2^8 - 1 1535m6×28−11535。代码中数组c[800][1600]足够容纳。空间复杂度O ( n × m ) O(n \times m)O(n×m)约1.2 × 10 6 1.2 \times 10^61.2×106字符完全可接受。总结通过递归模拟二叉树的绘制过程利用状态区分节点和两种斜线并通过进度参数a, b控制斜线的长度。删除节点时在递归前检查标记直接跳过整个子树的绘制从而用空格替代。画布尺寸和起始位置根据层数精确计算保证输出格式与题目要求完全一致。该方法直观且易于实现适合本题的小规模数据。代码简要说明全局数组c[800][1600]存储画布字符f[800][1600]标记被删除的节点按层号和序号。dfs1函数核心递归绘制函数参数包括坐标、斜线进度、状态和节点在树中的位置。根据状态分别绘制o、/、\并递归处理子节点。make(k)函数根据层数k计算画布行数n和列数m初始化画布为空格然后从根节点开始调用dfs1。主函数读入层数k和删除数量p标记删除节点。若k1直接输出o否则调用make(k)。最后逐行输出画布。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;ll k,n,m,p,x,y;charc[800][1600];boolf[800][1600];voiddfs1(ll x,ll y,ll a,ll b,ll k,ll xx,ll yy){if(xn){c[x][y]o;return;}if(k1){c[x][y]o;ll Xxx1,Y(yy-1)*21;if(!f[X][Y])dfs1(x1,y-1,a1,b,2,X,Y);Xxx1,Yyy*2;if(!f[X][Y])dfs1(x1,y1,a1,b,3,X,Y);}elseif(k2){c[x][y]/;if(a*2b)dfs1(x1,y-1,1,a,1,xx,yy);elsedfs1(x1,y-1,a1,b,2,xx,yy);}elseif(k3){c[x][y]92;if(a*2b)dfs1(x1,y1,1,a,1,xx,yy);elsedfs1(x1,y1,a1,b,3,xx,yy);}}voidmake(ll k){n3;for(ll i3;ik;i)n*2;m6*(1(k-2))-1;for(ll i1;in;i)for(ll j1;jm;j)c[i][j] ;dfs1(1,m/21,1,n,1,1,1);}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);scanf(%lld%lld,k,p);while(p--){scanf(%lld%lld,x,y);f[x][y]1;}if(k1)nm1,c[1][1]o;elsemake(k);for(ll i1;in;i){for(ll j1;jm;j)coutc[i][j];coutendl;}return0;}