logo AlgoBeat OnlineJudge
登录 注册

#200184. 绘制二叉树

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:VJudge(洛谷) 评测方式:VJudge
上传者: 匿名

题目描述

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

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

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

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

  2. 定义 为位于第 行第 列的某个字符。若 / ,那么 要么为 o ,要么为 /。若 \ ,那么 要么为 o,要么为 \ 。同样,若 为第 层的某个结点 o ,那么 /\

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

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

输入格式

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

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

输出格式

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

样例

样例输入 1

2 0

样例输出 1

  o  
 / \ 
o   o

样例输入 2

4 0

样例输出 2

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

样例输入 3

4 3
3 2
4 1
3 4

样例输出 3

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

数据范围与提示

的数据满足:

的数据满足:

的数据满足: