#NOIPJ2004C. FBI 树
FBI 树
题目描述
我们可以把由 “ ”和“ ”组成的字符串分为三类:全“ ”串称为 串,全“ ”串称为 串,既含“ ”又含“ ”的串则称为 串。 树是一种二叉树。
( 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。)
它的结点类型也包括 结点, 结点和 结点三种。由一个长度为 的“ ”串 可以构造出一棵 树 ,递归的构造方法如下: 的根结点为 ,其类型与串 的类型相同; 若串 的长度大于 ,将串 从中间分开,分为等长的左右子串 和 ;由左子串 构造 的左子树 ,由右子串 构造 的右子树 。 现在给定一个长度为 的“ ”串,请用上述构造方法构造出一棵 树,并输出它的后序遍历序列。
(后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历左子树,再后序遍历右子树,最后访问根。)
输入格式
输入文件的第一行是一个整数 ,第二行是一个长度为 的“ ”串。
输出格式
输出文件包括一行,这一行只包含一个字符串,即 树的后序遍历序列。
3
10001011
IBFBBBFIBFIIIFF
数据范围与提示
对于 %的数据,;
对于全部的数据, 。
相关
在以下作业中: