家教锦囊短信如何取消:noi2004之FBI树。

1、自下而上逐层生成FBI树
在程序中，要涉及到状态的存储、转换等。选择的数据结构必须先适用于描述状态，并使对状态的各种操作能够明确地定义在数据结构上。FBI树的数据结构不仅满足存储结点类别（‘F’，‘B’，‘Z’）的需要，而且能够方便地计算出左儿子和右儿子。设
tree为FBI树，其中tree[i]为节点i的类型标志，tree[i]∈{‘F’，‘B’，‘Z’}；
treel,treer为FBI树的左儿子序列和右儿子序列，即节点i的左儿子序号为treel[i]，右儿子序号为treer[i]。
FBI树的编号规则如下：
01串对应的类型作为FBI树的叶子存储于tree[m]¨tree[2*m-1]（m=2n）。然后从最底层出发，自下而上地逐层向上计算tree[m-1]¨tree[1]，其中节点i的左儿子序号为2*i,右儿子序号为2*i+1，即treel[i]←i*2; treer[i]←i*2+1。显然，根节点的序号为1。
若节点i的左子树的类型（tree[treel[i]]）和右子树的类型（tree[treer[i]]）至少有一个为‘F’或者一个‘B’和一个‘I’，则节点i的类型为‘F’；
若全‘I’，则节点i的类型为‘I’；若全‘B’，则节点i的类型为‘B’。
readln(n);{输入2的次幂}
if n=0{若01串的长度为1，则根据该字符输出串类型}
then begin
read(ch);
if ch='1'
then writeln('I')
else writeln('B');
halt{退出程序}
end;
m:=1;{计算串长2n}
for i:=1 to n do m:=m*2;
for i:=m to 2*m-1 do{将01串转换成FBI树的叶子}
begin
read(ch);
if ch='1'
then tree[i]:='I'
else tree[i]:='B';
treel[i]:=0;treer[i]:=0
end;
for i:=m-1 downto 1 do{由下而上递推计算FBI树}
begin
treel[i]:=i*2; treer[i]:=i*2+1;{计算节点i的左右儿子}
s:=tree[i*2]+tree[i*2+1];{取左右儿子的字符，根据规则向上递推节点i的字符}
if (s[1]='F')or(s[2]='F'){ 若节点i的左子树的类型和右子树的类型至少有一个为‘F’,则节点i的类型为‘F’}
then tree[i]:='F'
else begin{在节点i的左右子树的类型非‘F’的情况下，若左右子树的类型相同，则节点i的类型取决于子节点的类型；否则节点i的类型为‘F’}
if s[1]=s[2]
then if s[1]='I'
then tree[i]:='I'
else tree[i]:='B';
if s[1]<>s[2]{若}
then tree[i]:='F'
end{else}
end;{for}
后序遍历FBI树
在FBI树中，节点1为根。我们从根出发，按照左子树、右子树、根的顺序输出FBI树的后序遍历序列：
procedure print(s:integer);{后序遍历以节点s为根的FBI树}
begin
if s=0 then exit;{从叶子开始回溯}
print(treel[s]);print(treer[s]);{分别递归左子树和右子树}
write(tree[s]){输出根}
end;{ print }
显然，在递推出FBI树后递归调用print(1)，便可得出问题的解。