华师一附中OI组

标题: P1185 绘制二叉树 [打印本页]

作者: admin 时间: 2018-5-26 21:00
标题: P1185 绘制二叉树
https://www.luogu.org/problemnew/show/P1185

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

当一颗二叉树高度为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的区别(若用记事本打开看起来是一样的，但是评测时会被算作错误答案！)）。

输入输出格式
输入格式：
输入文件binary.in的第1行包含2个正整数m和n，为需要绘制的二叉树层数已经从m层满二叉树中删除的结点数。

接下来n行，每行两个正整数，表示第i层第j个结点需要被删除（1<i<=M，j<=2i-1）。

输出格式：
输出文件binary.out为按照题目要求绘制的二叉树。

输入输出样例
输入样例#1：
样例1
2 0
样例2
4 0
样例3
4 3
3 2
4 1
3 4
输出样例#1：
样例1
  o
/ \
o o
样例2
         o
      / \
      / \
      /    \
   /    \
   /       \
   o          o
/ \       / \
/ \    / \
  o    o    o    o
/ \ / \ / \ / \
o o o o o o o o
样例3
         o
      / \
      / \
      /    \
   /    \
   /       \
   o          o
/          /
/          /
  o          o
\       / \
o    o o
说明
30%的数据满足：n=0；

50%的数据满足：2<=m<=5；

100%的数据满足：2<=m<=10，0<=n<=10。

欢迎光临华师一附中OI组 (http://hsyit.cn/)