Problem8435--洛谷P1185 - 绘制二叉树

8435: 洛谷P1185 - 绘制二叉树

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

SubmitSolved: 0Submit Num: 0StatisticsShowOff!

Description

二叉树是一种基本的数据结构，它要么为空，要么由根节点，左子树和右子树组成，同时左子树和右子树也分别是二叉树。
当一颗二叉树高度为 $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$ 层的某个节点（即 “o”），那么 $[i+1,j-1]$ 为 “/”，$[i+1,j+1]$ 为 “\”。
3、对于第 $m$ 层节点也就是叶子结点，若两个属于同一个父亲，那么它们之间由 $3$ 个空格隔开，若两个结点相邻但不属于同一个父亲，那么它们之间由 $1$ 个空格隔开。第 $m$ 层左数第 $1$ 个节点之前没有空格。
最后需要在一颗绘制好的满二叉树上删除$n$个结点（包括它的左右子树，以及与父亲的连接），原有的字符用空格替换（`ASCII 32`，请注意空格与`ASCII 0`的区别(若用记事本打开看起来是一样的，但是评测时会被算作错误答案！)）。

Input

第$1$行包含$2$个正整数$m$和$n$，为需要绘制的二叉树层数已经从$m$层满二叉树中删除的结点数。
接下来$n$行，每行两个正整数，表示第$i$层第$j$个结点需要被删除（$1<i≤M,j≤2^{i-1}$）。

Output

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

Constraints

$30\%$的数据满足：$n=0$；
$50\%$的数据满足：$2≤m≤5$；
$100\%$的数据满足：$2≤m≤10,0≤n≤10$。

Sample 1 Input 

2 0

Sample 1 Output 

  o  
 / \ 
o   o

Sample 2 Input 

4 0

Sample 2 Output 

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

Sample 3 Input 

4 3
3 2
4 1
3 4

Sample 3 Output 

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

HINT

相同题目：洛谷 P1185。

Source/Category

 
Submit