P1185 绘制二叉树 题解

题目传送门

一、绘制二叉树

1、宽度分析

（含指定m值情况下的最大宽度，与极限值情况下最大宽度）

     o
    / \
   o   o

m = 2 --->最长宽度\(=6=3*2^1\)(在最后面一个o后面再加一个空格，算入本轮的宽度)

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

m = 3 --->最长宽度\(=12=3*2^2\)

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

m=4 --->宽度\(=24=3*2^3\)

总结规律
1、指定m的情况下，宽度\(=pow(2,m-1)*3\)

2、\(m\)的极限值=10,那么极限宽度\(maxWidth=pow(2,10-1)*3=pow(2,9)*3=512*3\),如此可知数组宽度的上限为\(512*3+10\)即可。

2、递归思想

1、绘制二叉树
（1）、绘制树根
（2）、如果深度为1，表示到了叶子，不再继续，退出递归。
（3）、计算出本层到下一层的树枝个数，利用循环+动态变量变更，绘制多个树枝。
（4）、递归绘制左子树。
（5）、递归绘制右子树。

2、删除结点
（1）、设置本结点为空
（2）、判断左上角是不是 \,是的话递归删除
（3）、判断右上角是不是 /,是的话递归删除
（4）、判断左下角是不是/或者o,是的话递归删除
（5）、判断右下角是不是\或者o,是的话递归删除

3、位置映射思想

题目给出的是第几行第几个的意思，需要与真实存储的数组中数据进行位置对应。

二、C++代码

#include <bits/stdc++.h>

using namespace std;
typedef pair<int, int> PII;

const int N = 512 * 3 + 10;
char a[N][N];//疑问：第一维为什么也要开N这么大，按理说开N/2就够了
PII b[N][N];
int width;

//放过位置0，后面是10个数字
//此数组的含义：穷举出level=1，2，3，4，... ，10时(从下往上)，子树开始的位置。
const int col[11] = {0, 1, 3, 6, 12, 24, 48, 96, 192, 384, 768};

/**
 * 功能：自顶向下画二叉树
 * @param r  从哪一行开始
 * @param c  从哪一列开始
 * @param depth 深度
 */
void dfs(int r, int c, int depth) {
    //此位置放上o
    a[r][c] = 'o';

    //如果到了叶子结点，递归结束
    if (depth == 1) return;//这个depth是用来控制递归终止的，判断是不是到了叶子

    //树枝的个数,从当前结点到下一层结点间树枝的个数是多少,可以转化为求相邻结点的列差值
    int cnt = col[depth] - col[depth - 1] - 1;

    //下一步的左儿子，右儿子的位置
    int lSonRow = r + 1, lSonCol = c - 1, rSonRow = r + 1, rSonCol = c + 1;

    //执行几次，画出树干
    for (int i = 1; i <= cnt; i++) {
        a[lSonRow++][lSonCol--] = '/'; //在循环中动态修改左右儿子的位置坐标，继续填充
        a[rSonRow++][rSonCol++] = '\\';
    }

    //递归填充左子树
    dfs(lSonRow, lSonCol, depth - 1);

    //递归填充右子树
    dfs(rSonRow, rSonCol, depth - 1);
}

/**
 * 功能：输出二维数组
 */
void print() {
    //width为最长有效数据范围
    for (int i = 1; i <= width; i++) {
        for (int j = 1; j <= width; j++)
            cout << a[i][j];
        cout << endl;
    }
}

/**
 * 递归删除结点
 * @param r 行
 * @param c 列
 */
void delNode(int r, int c) {
    a[r][c] = ' ';
    if (a[r - 1][c - 1] == '\\') delNode(r - 1, c - 1);//向左上进行探索删除,向上不能删除o
    else if (a[r - 1][c + 1] == '/') delNode(r - 1, c + 1);//向右上进行探索删除,向上不能删除o
    //上面的可以使用else,因为一个位置只能向上有一条路径，不能既有左上，又有右上

    //向下就很暴力了，不管是/ \ o全部干掉
    if (a[r + 1][c - 1] == '/' || a[r + 1][c - 1] == 'o') delNode(r + 1, c - 1);
    if (a[r + 1][c + 1] == '\\' || a[r + 1][c + 1] == 'o') delNode(r + 1, c + 1);
}


//生成每一行每一列每一个o的具体位置
//因为题目给的数据是第几行第几列的相对位置，需要转换为在数组中的绝对位置
void fillReleation() {
    int row = 1;
    for (int i = 1; i <= width; i++) {
        int cnt = 0;
        bool found = false;
        for (int j = 1; j <= width; j++) {
            if (a[i][j] == 'o') {//本行中找到o, cnt记录个数
                cnt++;
                found = true;   //标识为找到，本行找到后，row++,找不到，不用++
                b[row][cnt] = {i, j};
            }
        }
        if (found) row++;
    }
}

int main() {
    int m;      //绘制的二叉树层数
    int delCnt; //要删除结点的个数
    cin >> m >> delCnt;
    //行和列都设置为空格
    memset(a, ' ', sizeof a);

    //给定m情况下的底层宽度
    width = pow(2, m - 1) * 3;

    //填充
    dfs(1, col[m], m);

    //生成具体位置对应关系表
    fillReleation();

    //删除结点
    int x, y;
    for (int i = 1; i <= delCnt; i++) {
        cin >> x >> y;
        delNode(b[x][y].first, b[x][y].second);
    }
    //打印
    print();
    return 0;
}

三、讲解视频

https://www.bilibili.com/video/BV1nq4y1j754