3023: 【普及+/提高】【P1185】绘制二叉树

内存限制:128 MB 时间限制:1.000 S
评测方式:文本比较 命题人:
提交:0 解决:0

题目描述

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

当一颗二叉树高度为lns="http://www.w3.org/1998/Math/MathML">1时,则共有lns="http://www.w3.org/1998/Math/MathML">层。除lns="http://www.w3.org/1998/Math/MathML">层外,其他各层的结点数都达到最大,且结点节点都在第lns="http://www.w3.org/1998/Math/MathML">层时,这就是一个满二叉树。

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

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

2、定义lns="http://www.w3.org/1998/Math/MathML">[,]为位于第lns="http://www.w3.org/1998/Math/MathML">行第lns="http://www.w3.org/1998/Math/MathML">列的某个字符。若lns="http://www.w3.org/1998/Math/MathML">[,]为“/”,那么lns="http://www.w3.org/1998/Math/MathML">[1,+1]lns="http://www.w3.org/1998/Math/MathML">[+1,1]要么为“o”,要么为“/”。若lns="http://www.w3.org/1998/Math/MathML">[,]为“\”,那么lns="http://www.w3.org/1998/Math/MathML">[1,1]lns="http://www.w3.org/1998/Math/MathML">[+1,+1]要么为“o”,要么为“\”。同样,若lns="http://www.w3.org/1998/Math/MathML">[,]为第lns="http://www.w3.org/1998/Math/MathML">1层的某个节点(即“o”),那么lns="http://www.w3.org/1998/Math/MathML">[+1,1]为“/”,lns="http://www.w3.org/1998/Math/MathML">[+1,+1]为“\”。

3、对于第lns="http://www.w3.org/1998/Math/MathML">层节点也就是叶子结点,若两个属于同一个父亲,那么它们之间lns="http://www.w3.org/1998/Math/MathML">3个空格隔开,若两个结点相邻但不属于同一个父亲,那么它们之间由lns="http://www.w3.org/1998/Math/MathML">1个空格隔开。第lns="http://www.w3.org/1998/Math/MathML">层左数第lns="http://www.w3.org/1998/Math/MathML">1个节点之前没有空格。

最后需要在一颗绘制好的满二叉树上删除lns="http://www.w3.org/1998/Math/MathML">个结点(包括它的左右子树,以及与父亲的连接),原有的字符用空格替换(ASCII 32,请注意空格与ASCII 0的区别(若用记事本打开看起来是一样的,但是评测时会被算作错误答案!))。

输入

lns="http://www.w3.org/1998/Math/MathML">1行包含lns="http://www.w3.org/1998/Math/MathML">2个正整数lns="http://www.w3.org/1998/Math/MathML">lns="http://www.w3.org/1998/Math/MathML">,为需要绘制的二叉树层数已经从lns="http://www.w3.org/1998/Math/MathML">层满二叉树中删除的结点数。

接下来lns="http://www.w3.org/1998/Math/MathML">行,每行两个正整数,表示第lns="http://www.w3.org/1998/Math/MathML">层第lns="http://www.w3.org/1998/Math/MathML">个结点需要被删除(lns="http://www.w3.org/1998/Math/MathML">1<,21)。

输出

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

样例输入 复制

2 0

样例输出 复制

  o  
 / \ 
o   o

提示

的数据满足:lns="http://www.w3.org/1998/Math/MathML">=0

lns="http://www.w3.org/1998/Math/MathML">50%的数据满足:lns="http://www.w3.org/1998/Math/MathML">25

lns="http://www.w3.org/1998/Math/MathML">100%的数据满足:lns="http://www.w3.org/1998/Math/MathML">210,010