算法刷题【洛谷P1185】绘制二叉树

信息学竞赛

2022-04-17

异想之旅：本人原创博客完全手敲，绝对非搬运，全网不可能有重复；本人无团队，仅为技术爱好者进行分享，所有内容不牵扯广告。本人所有文章仅在CSDN、掘金和个人博客（一定是异想之旅域名）发布，除此之外全部是盗文！

洛谷 P1185 绘制二叉树

题目描述

二叉树是一种基本的数据结构，它要么为空，要么由根节点，左子树和右子树组成，同时左子树和右子树也分别是二叉树。

当一颗二叉树高度为 $m-1$ 时，则共有 $m$ 层。除 $m$ 层外，其他各层的结点数都达到最大，且结点节点都在第 $m$ 层时，这就是一个满二叉树。

现在，需要你用程序来绘制一棵二叉树，它由一颗满二叉树去掉若干结点而成。对于一颗满二叉树，我们需要按照以下要求绘制：

1、结点用小写字母“o”表示，对于一个父亲结点，用“/”连接左子树，同样用“\”连接右子树。

2、定义 $[i,j]$ 为位于第 $i$ 行第 $j$ 列的某个字符。若 $[i,j]$ 为“/”，那么 $[i-1,j+1]$ 与 $[i+1,j-1]$ 要么为“o”，要么为“/”。若 $[i,j]$ 为“\”，那么 $[i-1,j-1]$ 与 $[i+1,j+1]$ 要么为“o”，要么为“\”。同样，若 $[i,j]$ 为第 $1-m$ 层的某个节点（即“o”），那么 $[i+1,j-1]$ 为“/”， $[i+1,j+1]$ 为“\”。

3、对于第 $m$ 层节点也就是叶子结点，若两个属于同一个父亲，那么它们之间由 $3$ 个空格隔开，若两个结点相邻但不属于同一个父亲，那么它们之间由 $1$ 个空格隔开。第 $m$ 层左数第 $1$ 个节点之前没有空格。

最后需要在一颗绘制好的满二叉树上删除 $n$ 个结点（包括它的左右子树，以及与父亲的连接），原有的字符用空格替换（ASCII 32，请注意空格与ASCII 0的区别(若用记事本打开看起来是一样的，但是评测时会被算作错误答案！)）。

输入格式

第 $1$ 行包含 $2$ 个正整数 $m$ 和 $n$ ，为需要绘制的二叉树层数已经从 $m$ 层满二叉树中删除的结点数。

接下来 $n$ 行，每行两个正整数，表示第 $i$ 层第 $j$ 个结点需要被删除（ $1<i\leq M,j\leq2^{i-1}$ ）。

输出格式

按照题目要求绘制的二叉树。

输入输出样例

In 1：

2 0

Out 1：

  o
 / \
o   o

In 2：

4 0

Out 2：

           o
          / \
         /   \
        /     \
       /       \
      /         \
     o           o
    / \         / \
   /   \       /   \
  o     o     o     o
 / \   / \   / \   / \
o   o o   o o   o o   o

In 3：

Out 3：

           o
          / \
         /   \
        /     \
       /       \
      /         \
     o           o
    /           /
   /           /
  o           o
   \         / \
    o       o   o

数据范围

$30\%$ 的数据满足： $n=0$ ；

$50\%$ 的数据满足： $2\leq m\leq5$ ；

$100\%$ 的数据满足： $2\leq m\leq10,0\leq n\leq10$ 。

题解

本文视频讲解：

[video(video-fV7FWluZ-1644210146842)(type-csdn)(url-https://live.csdn.net/v/embed/185376)(image-https://live-file.csdnimg.cn/release/live/file/1644160543929.png?x-oss-process=image/resize,l_300)(title-算法刷题【洛谷P1185】绘制二叉树)]

这道题我喜欢，为什么？——不需要那么多代数证明啊！

我使用的是复杂的递归控制来完成。

为了方便题解书写，我们定义树枝层为由 '/' '\\' ' ' 三个字符组成的横行，树叶层为由 'o' ' ' 两个字符组成的横行

从大方向上来分析大概分为以下几步：

找到根节点的位置，向左右两边延伸两个子树（两次递归），分别有向左和向右延伸的标记
对于递归函数，判断当前递归到的层是树枝层还是树叶层，若是树枝层则添加树枝字符后继续向同一方向延伸，树叶层则重复第 $1$ 步
递归时另加入参数标记当前节点是该层的第几个，每当到达树叶层时检测当前节点是否要删去，若要删去，则标记当前位置为空格，然后顺着树枝延伸的方向“爬回去”，依次把刚刚做好的树枝字符标记改为空格，直到碰到 'o' 字符，代表连接要被删去的这个节点的树枝删除干净了（若不删去则正常执行递归）
边界判断

但是还是有几个数据需要我们推出来：当层数为 $m$ 时，整个二维数组有效部分，即输出后可见部分的宽度 $x$ 和高度 $y$ ，以及每两个树叶层之间树枝层的数量 $ltimes[i]$ （表示倒数第 $i$ 层和倒数第 $i+1$ 层两个树叶层之间树枝层的数量）。

对于宽度 $x$ 和高度 $y$ ，我们来列表找规律：

层数 $m$	宽度 $x$	高度 $y$
1	1	1
2	5	3
3	11	6
4	23	12
5	47	24

这里猛地一看似乎有规律但是又表示不出来，没关系，我们来简化一下：把层数为 $1$ 的情况删去（代码中特判即可），请再观察，规律不难找了吧~

总结如下：

当 $m = 1$ 时， $x=y=1$
当 $m > 1$ 时， $x = 6 \times2^{m-2} - 1, y = 3 \times 2^{m-2}$

再来看 $ltimes[i]$ 的值：

位置	树枝层宽度
倒数第 $1$ 与倒数第 $2$ 层之间	1
倒数第 $2$ 与倒数第 $3$ 层之间	2
倒数第 $3$ 与倒数第 $4$ 层之间	5
倒数第 $4$ 与倒数第 $5$ 层之间	11

又找不到规律了？~~我是不会告诉你这里还需要特判第一组数据的~~

所以 $ltimes[i]$ 的规律为：当 $i=1$ 时， $ltimes[i]=1$ ；当 $i>1$ 时， $ltimes[i]=3\times2^{i-2}-1$

OK，上代码！这个主要是代码的模拟，因此我写了详细的注释供参考！

#include <bits/stdc++.h>
using namespace std;

int m, n, x, y;  // 层数，要删去的节点个数，所需的地图宽度，所需的地图高度
char mp[5000][10000];  // 存储最终打印的地图
int ltimes[100] = {0, 0, 1, 2, 5};
bool locker[100][100];  // 标记要被删去的节点，locker[i][j]=true表示第i层第j个的节点要被删去

void dfs(int p, int q, int level, int times, bool left, int num) {
    /*
        p, q: 当前节点的坐标
        level: 当前节点所在的树叶层层数（若当前为树枝层，则取上方最靠近的树叶层的值），用于确定所需的树枝层的数量
        times: 到目前level值未变动的递归层数，用于标记是否画完了当前所需的树枝层数
        left: 标记树枝层的延伸方向，值为true代表向左
        num: 在当前层当前节点的编号（表示第几个，用于确认是否要删除；仅当处于树叶层时有意义）
    */

   // 根据times判断是否到达树叶层
    if (times == 0) {
        // 是树叶层，进行相应标记
        mp[p][q] = 'o';

        // 判断当前节点是否要删除
        if (locker[level][num]) {
            // 删去节点
            mp[p][q] = ' ';

            // 判断该节点前树枝的延伸方向，原路返回删除树枝，直到到达上一个树叶层
            if (left) {
                for (int i = p - 1, j = q + 1; mp[i][j] != 'o'; i--, j++) {
                    mp[i][j] = ' ';
                }
            } else {
                for (int i = p - 1, j = q - 1; mp[i][j] != 'o'; i--, j--) {
                    mp[i][j] = ' ';
                }
            }

            // 删除完成后停止该子树的递归
            return;
        }

        // 如果当前已经到达了最底的树叶层，则停止递归
        if (level == m) return;

        // 如果当前节点无需删除且不是最底的树叶层，则继续递归，分为左右子树分别处理
        // 当前节点在当前层的编号，乘2减1得其左孩子在左孩子所在层的编号，乘2得其右孩子在右孩子所在层的编号
        dfs(p + 1, q - 1, level, times + 1, true, num * 2 - 1);
        dfs(p + 1, q + 1, level, times + 1, false, num * 2);
    } else {
        // 是树枝层，进行相应标记
        mp[p][q] = left ? '/' : '\\';

        // 判断是否是当前这一组树枝层的最后一层
        if (times == ltimes[m + 1 - level]) {
            // 是，则下一层level+1，times=0
            if (left)
                dfs(p + 1, q - 1, level + 1, 0, true, num);
            else
                dfs(p + 1, q + 1, level + 1, 0, false, num);
        } else {
            // 不是，正常递归，除坐标外仅需处理times
            if (left)
                dfs(p + 1, q - 1, level, times + 1, true, num);
            else
                dfs(p + 1, q + 1, level, times + 1, false, num);
        }
    }
}

int main() {
    memset(mp, ' ', sizeof(mp));  // 地图赋初始值为' '
    for (int i = 3; i < 100; i++) {
        ltimes[i] = 3 * pow(2, i - 3) - 1;  // 初始化树叶层之间树枝层的数量
    }

    // 数据输入，并确定地图大小（找规律，具体公式上文说了）
    cin >> m >> n;
    if (m == 1) {
        x = 1;
        y = 1;
    } else {
        x = 6 * pow(2, m - 2) - 1;
        y = 3 * pow(2, m - 2);
    }

    // 根据输入的数据，确定要删除的节点，记录在locker中
    int t1, t2;
    for (int i = 0; i < n; i++) {
        cin >> t1 >> t2;
        locker[t1][t2] = true;
    }

    // 根据地图大小确定根节点位置，调用dfs函数画出地图
    // 易知根节点处于第1行，列数为x/2+1（因为其处于第一行正中的对称轴上，x恒为奇数）
    dfs(1, x / 2 + 1, 1, 0, 0, 1);

    // 打印地图，由于x表示的是宽度，即列数，所以外层为y内层为x
    for (int i = 1; i <= y; i++) {
        for (int j = 1; j <= x; j++) {
            cout << mp[i][j];
        }
        cout << endl;
    }

    return 0;
}

版权所有

许可证：署名-非商业性-相同方式共享 4.0 国际 (CC-BY-NC-SA-4.0)