绘制二叉树

GitHub 跳转原题关系图返回列表

按层数公式计算满二叉树画布坐标，递归绘制节点和斜边，并跳过被删除的整棵子树。

OJ: luogu

题目 ID: P1185

难度:普及+/提高

标签:二叉树递归模拟python

日期: 2026-07-16 18:17

题意

按固定 ASCII 规则绘制 m 层满二叉树，并删除指定节点、它的所有后代以及与父节点的连线。

思路

画布高度和宽度为：

height=3\times2^{m-2},\qquad width=2\times height-1

根位于 (0,width//2)。除叶层外，第 level 层节点行号为 height-3*2^(m-level-1)，叶层在最后一行。父子节点横向偏移恰好等于纵向行差，因此连线上的每一步同时改变一行一列。

用满二叉树堆编号表示节点：第 level 层第 index 个节点编号是 2^(level-1)+index-1。先递归把删除节点的整个子树加入集合；绘制时若孩子已删除，就连线和子树都跳过。

Python 知识

二维画布必须写成 [[" "]*width for _ in range(height)]，保证各行独立。
deleted 集合保存堆编号，判断某棵子树是否绘制。
三元组 (child,direction,slash) 把左右孩子的对称绘制合并成同一循环。
最后按固定宽度 "".join(row) 输出，保留题目要求的行尾空格。
/home/rainboy/mycode/hugo-blog/content/program_language/python/cpp_to_python_pitfalls.md：二维列表独立行。
/home/rainboy/mycode/hugo-blog/content/program_language/python/brute_force_validation.md：递归树状态。

代码

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45m, removal_count = map(int, input().split())
height = 3 * (1 << (m - 2))
width = 2 * height - 1
node_row = [0] * (m + 1)
for level in range(1, m):
    node_row[level] = height - 3 * (1 << (m - level - 1))
node_row[m] = height - 1

deleted = set()


def remove_subtree(node):
    if node >= 1 << m:
        return
    deleted.add(node)
    remove_subtree(node * 2)
    remove_subtree(node * 2 + 1)


for _ in range(removal_count):
    level, index = map(int, input().split())
    remove_subtree((1 << (level - 1)) + index - 1)

canvas = [[" "] * width for _ in range(height)]


def draw(node, level, row, column):
    if node in deleted:
        return
    canvas[row][column] = "o"
    if level == m:
        return

    child_row = node_row[level + 1]
    gap = child_row - row
    for child, direction, slash in ((node * 2, -1, "/"), (node * 2 + 1, 1, "\\")):
        if child in deleted:
            continue
        for step in range(1, gap):
            canvas[row + step][column + direction * step] = slash
        draw(child, level + 1, child_row, column + direction * gap)


draw(1, 1, 0, width // 2)
print("\n".join("".join(row) for row in canvas))

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79/**
 * P1185 绘制二叉树
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-27 00:00
 * update_at: 2026-07-27 00:00
 */

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

const int MAXM = 11;

int m, k;
bool del[1 << MAXM]; // 标记被删除的结点（按完全二叉树编号）
char canvas[800][1600]; // 画布（宽 = 2*高-1）
int height, width;
int node_row[MAXM]; // 每层结点的行号

// 递归删除子树
void remove_sub(int u) {
    if (u >= (1 << m)) return;
    del[u] = true;
    remove_sub(u * 2);
    remove_sub(u * 2 + 1);
}

// 递归绘制
void draw(int u, int level, int row, int col) {
    if (del[u]) return;
    canvas[row][col] = 'o';
    if (level == m) return;
    int child_row = node_row[level + 1];
    int gap = child_row - row;
    // 左孩子
    if (!del[u * 2]) {
        for (int step = 1; step < gap; ++step)
            canvas[row + step][col - step] = '/';
        draw(u * 2, level + 1, child_row, col - gap);
    }
    // 右孩子
    if (!del[u * 2 + 1]) {
        for (int step = 1; step < gap; ++step)
            canvas[row + step][col + step] = '\\';
        draw(u * 2 + 1, level + 1, child_row, col + gap);
    }
}

int main() {
    scanf("%d%d", &m, &k);
    // 计算画布尺寸
    height = 3 * (1 << (m - 2));
    if (m == 1) height = 1;
    width = 2 * height - 1;
    // 计算每层结点的行号
    for (int i = 1; i < m; ++i)
        node_row[i] = height - 3 * (1 << (m - i - 1));
    node_row[m] = height - 1;
    // 读入并标记删除的结点
    for (int i = 1; i <= k; ++i) {
        int level, idx;
        scanf("%d%d", &level, &idx);
        int u = (1 << (level - 1)) + idx - 1;
        remove_sub(u);
    }
    // 初始化画布为空格
    for (int i = 0; i < height; ++i)
        for (int j = 0; j < width; ++j)
            canvas[i][j] = ' ';
    // 绘制
    draw(1, 1, 0, width / 2);
    // 输出
    for (int i = 0; i < height; ++i) {
        canvas[i][width] = '\0';
        printf("%s\n", canvas[i]);
    }
    return 0;
}

复杂度

画布大小为 $O(4^m)$ 个字符，绘制和输出均与画布大小同阶；递归深度 $O(m)$ 。

总结

ASCII 绘树的难点是先推导稳定坐标。用堆编号管理删除、用行差同时决定横向偏移后，左右子树可以统一递归绘制。

P1185 绘制二叉树

题目描述

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

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

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

结点用小写字母 o 表示，对于一个父亲结点，用 / 连接左子树，用 \ 连接右子树。
定义 $[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\sim m-1$ 层的某个结点 o ，那么 $[i+1,j-1]$ 为 /， $[i+1,j+1]$ 为 \。
对于第 $m$ 层结点也就是叶子结点，若两个属于同一个父亲，那么它们之间由 $3$ 个空格隔开；若两个结点相邻但不属于同一个父亲，那么它们之间由 $1$ 个空格隔开。第 $m$ 层左数第 $1$ 个结点之前没有空格。

最后需要在一棵绘制好的满二叉树上删除 $n$ 个结点（包括这个结点的左右子树，以及与父亲的连接），原有的字符用空格替换（空格为 ASCII 32，若输出 ASCII 0 会被算作错误答案）。

输入格式

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

接下来 $n$ 行，每行两个正整数，表示删除第 $i$ 层的第 $j$ 个结点。

输出格式

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

输入输出样例 #1

输入 #1

text

12 0

输出 #1

text

1
2
3  o  
 / \ 
o   o

输入输出样例 #2

输入 #2

text

14 0

输出 #2

text

1
2
3
4
5
6
7
8
9
10
11
12           o           
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     o           o     
    / \         / \    
   /   \       /   \   
  o     o     o     o  
 / \   / \   / \   / \ 
o   o o   o o   o o   o

输入输出样例 #3

输入 #3

text

输出 #3

text

1
2
3
4
5
6
7
8
9
10
11
12           o           
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     o           o     
    /           /      
   /           /       
  o           o        
   \         / \       
    o       o   o

说明/提示

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

$50\%$ 的数据满足： $2\le m\le 5$ ；

$100\%$ 的数据满足： $2\le m\le10,0\le n\le 10,1<i\le M,j\le 2^{i-1}$ 。

绘制二叉树

目录

题意

思路

Python 知识

代码

复杂度

总结