问题 5097. -- FBI树-NOIP2004PJT3

5097: FBI树-NOIP2004PJT3

时间限制: 1 Sec  内存限制: 128 MB
献花: 16  解决: 12
[献花][花圈]

题目描述

FBI树

(fbi.pas/c/cpp)

题目描述

  我们可以把由“0”和“1”组成的字符串分为三类:全“0”串称为B串,全“1”串称为I串,既含“0”又含“1”的串则称为F串。

FBI树是一种二叉树[1],它的结点类型也包括F结点,B结点和I结点三种。由一个长度为2N的“01”S可以构造出一棵FBIT,递归的构造方法如下:

1) T的根结点为R,其类型与串S的类型相同;

2) 若串S的长度大于1,将串S从中间分开,分为等长的左右子串S1S2;由左子串S1构造R的左子树T1,由右子串S2构造R的右子树T2

现在给定一个长度为2N的“01”串,请用上述构造方法构造出一棵FBI树,并输出它的后序遍历[2]序列。


[1] 二叉树:二叉树是结点的有限集合,这个集合或为空集,或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。

[2] 后序遍历:后序遍历是深度优先遍历二叉树的一种方法,它的递归定义是:先后序遍历左子树,再后序遍历右子树,最后访问根。



输入格式


输入文件fbi.in的第一行是一个整数N0 <= N <= 10),第二行是一个长度为2N的“01”串。

输出


输出文件fbi.out包括一行,这一行只包含一个字符串,即FBI树的后序遍历序列。

样例输入

3
10001011

样例输出

IBFBBBFIBFIIIFF



输入

对于40%的数据,N <= 2;

对于全部的数据,N <= 10。



















输出

//该题题解因故不能加入提示中,故初次昨天略过此处

第三题:fbi;

 
【算法分析】
    此题的后序遍历适合用递归算法完成。由题目可知,输入数据给出的字符为所要遍历的fbi树的叶结点代码,又因为字符串的长度为2的整数次幂,故此fbi树为完全二叉树。由于题中明确规定:子符串中的字符都是‘0’,为B串;都是‘1’,为I串;既有‘0’又有‘1’,为F串。即:二叉树的子结点都是B,父结点为B;子结点都是I,父结点为I;既有I又有B,父结点为F。因此,根据树的子结点可以求出父结点。我们要做的是根据子结点后序遍历二叉树。基本算法为:
procedure bianli(x,y:integer);//遍历过程;x,y:为子结点在数组a中的位置。
 begin
  if x=y then 输出叶结点         //结束递归条件,结点为一个字符。
         else begin
               求出父结点;
               遍历左子树;   
               遍历右子树;
               输出父结点;
              end;
 end;                           //递归算法,详情请参阅程序清单。
【数据结构】
var a:array[1..10000]of '0'..'1';
【程序清单】
program fbi;
var a:array[1..10000]of '0'..'1';
    n,i,l:integer;
    f1,f2:text;
    treeb,treei:boolean;
    tree:char;
procedure bianli(x,y:integer);               {递归过程,x,y为所要遍历的树的叶结点在数组a中位置}
 begin
  if x=y then case a[x] of
               '0':write(f2,'B');
               '1':write(f2,'I');
              end                                                                  {输出叶结点}
         else begin
               bianli(x,x+(y-x+1) div 2-1);                                        {遍历左子树}
               bianli(x+(y-x+1)div 2,y);                                           {遍历右子树}
               treei:=false;treeb:=false;
               for i:=x to y do if a[i]='0' then treeb:=true else treei:=true; {求出树的父结点}
               if treei and treeb then tree:='F'
                else begin
                      if treei then tree:='I';
                      if treeb then tree:='B'                                      {输出父结点}
                     end;
               write(f2,tree);
              end
 end;
begin
 assign(f1,'fbi.in'); reset(f1);                                           {输入文件名"fbi,in"}
 assign(f2,'fbi.out');rewrite(f2);                                        {输出文件名"fbi.out"}
 readln(f1,n);l:=1;
 for i:=1 to n do l:=l*2;
 for i:=1 to l do read(f1,a[i]);                                       {读入数据,l为字符串长度}
 bianli(1,l);writeln(f2);
 close(f1); close(f2)
end.

提示




来源

[献花][花圈]