问题 H: 绘制二叉树

内存限制:128 MB 时间限制:1.000 S 标准输入输出
题目类型:传统 评测方式:文本比较 上传者:
提交:7 通过:6

题目描述

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

当一颗二叉树高度为 $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\sim m-1$ 层的某个结点 `o` ,那么 $[i+1,j-1]$ 为 `/`,$[i+1,j+1]$ 为 `\`。

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

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


输入格式

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

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


输出格式

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

输入样例 复制

2 0

输出样例 复制

  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}$。

分类标签