主题：帮我解题！《FBI树》
michaellyz
[专家分：270] 发布于 2005-11-27 18:15:00
FBI树
(fbi.pas/dpr/c/cpp)
【问题描述】
我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
FBI树是一种二叉树 ，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
1) T的根结点为R，其类型与串S的类型相同；
2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历 序列。
【输入文件】
输入文件fbi.in的第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。
【输出文件】
输出文件fbi.out包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。
【样例输入】
3
10001011
【样例输出】
IBFBBBFIBFIIIFF
【数据规模】
对于40%的数据，N <= 2；
对于全部的数据，N <= 10。
二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。
后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。
回复列表 （共6个回复）
沙发
michaellyz [专家分：270] 发布于 2005-11-27 18:23:00
这是第十届上海“上中杯”noip复赛普及组试题。
板凳
梦幻神兵 [专家分：600] 发布于 2005-11-28 16:34:00
方法：递归即可，按后序遍历直接边生成边打印。
程序：
program fbi; {writen by lxq 2004.11.20}
var f:array[1..1024] of char;
i,k,n:integer;
c:char;
function lastorder(i,j,n:integer):char;
var lc,rc:char;
begin
if n=0 then lastorder:=f[ i ]
else begin
lc:=lastorder(i,(i+j) div 2,n-1);
write(lc);
rc:=lastorder((i+j) div 2+1,j,n-1);
write(rc);
if lc=rc then lastorder:=lc else lastorder:='F';
end;
end;
begin
assign(input,'fbi.in');
reset(input);
readln(n);
k:=1;
for i:=1 to n do k:=k*2;
for i:=1 to k do
begin
read(c);
if c='0' then f[ i ]:='B' else f[ i ]:='I'
end;
readln;
close(input);
assign(output,'fbi.out');
rewrite(output);
writeln(lastorder(1,k,n));
close(output);
end.
3 楼
封天怒龙 [专家分：160] 发布于 2005-11-30 21:33:00
var f:array[1..1024] of char;
i,k,n:integer;
c:char;
function lastorder(i,j,n:integer):char;
var lc,rc:char;
begin
if n=0 then lastorder:=f[ i ]
else begin
lc:=lastorder(i,(i+j) div 2,n-1);
write(lc);
rc:=lastorder((i+j) div 2+1,j,n-1);
write(rc);
if lc=rc then lastorder:=lc else lastorder:='F';
end;
end;
begin
assign(input,'fbi.in');
reset(input);
readln(n);
k:=1;
for i:=1 to n do k:=k*2;
for i:=1 to k do
begin
read(c);
if c='0' then f[ i ]:='B' else f[ i ]:='I'
end;
readln;
close(input);
assign(output,'fbi.out');
rewrite(output);
writeln(lastorder(1,k,n));
close(output);
end.
4 楼
qiuzhi2008 [专家分：0] 发布于 2006-09-21 18:35:00
program fbi(input,output);
var
a:array[1..10000] of char;
i,n,ln:integer;
st:string;
procedure backorder(tt:integer);
begin
if a[tt]<>#0 then
begin
backorder(tt*2);
backorder(tt*2+1);
write(a[tt]);
end;
end;
begin
assign(input,'fbi.in');
assign(output,'fbi.out');
reset(input);
rewrite(output);
readln(n);
read(st);
ln:=1;
for i:=1 to n do ln:=ln*2;
for i:=ln to ln+ln-1 do
if st[i-ln+1]='0' then a[i]:='B' else a[i]:='I';
ln:=ln div 2;
while ln>=1 do
begin
for i:=ln to ln+ln-1 do
if (a[i*2]='F') or (a[i*2+1]='F') then a[i]:='F'
else
if a[i*2]<>a[i*2+1] then a[i]:='F'
else if a[i*2]='I' then a[i]:='I' else a[i]:='B';
ln:=ln div 2;
end;
backorder(1);
close(input);
close(output);
end.
5 楼
qiuzhi2008 [专家分：0] 发布于 2006-09-21 18:36:00
program fbi;
var f:array[1..1024] of char;
i,k,n:integer;
c:char;
function lastorder(i,j,n:integer):char;
var lc,rc:char;
begin
if n=0 then lastorder:=f[ i ]
else begin
lc:=lastorder(i,(i+j) div 2,n-1);
write(lc);
rc:=lastorder((i+j) div 2+1,j,n-1);
write(rc);
if lc=rc then lastorder:=lc else lastorder:='F';
end;
end;
begin
assign(input,'fbi.in');
reset(input);
assign(output,'fbi.out');
rewrite(output);
readln(n);
k:=1;
for i:=1 to n do k:=k*2;
for i:=1 to k do
begin
read(c);
if c='0' then f[ i ]:='B' else f[ i ]:='I'
end;
readln;
writeln(lastorder(1,k,n));
close(input);close(output);
end.
6 楼
waglongjuanfeng [专家分：90] 发布于 2006-10-05 02:49:00
readln(n);
if n:=0 then begin
read(ch);
if ch='i'
then writeln('i')
else writeln('B');
halt
end;
m:=1;
for i:=1 to n do m:=m*2;
for i:=1 to 2m-1 do
begin
read(ch);
if ch='i'
then tree[i]:=i
else tree[i]:=b;
treel[i]:=0;treer[i]:=0;
end;
for i:=m-1 downto 1 do
begin
tree[i]:=i*2,^……………………………………………………
procedure print(s:integer); {后序遍历}
begin
if s=0 then exit;
print(treel[s]);print(treer[s]);
write(tree[s])
end;
我来回复
您所在位置：