2528 - 绘制二叉树

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

当一颗二叉树高度为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<=M,j<=2_{i-1})。

输出

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

样例

输入

2 0

输出

  o  
 / \ 
o   o

输入

4 3
3 2
4 1
3 4

输出

           o
          / \          
         /   \         
        /     \        
       /       \       
      /         \      
     o           o     
    /           /      
   /           /       
  o           o        
   \         / \       
    o       o   o
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题