799
WIKIOI-1094 FBI樹(未完成)
1094 FBI樹
題目描述 Description
我們可以把由“0”和“1”組成的字符串分為三類：全“0”串稱為B串，全“1”串稱為I串，既含“0”又含“1”的串則稱為F串。
FBI樹是一種二叉樹[1]，它的結點類型也包括F結點，B結點和I結點三種。由一個長度為2^N的“01”串S可以構造出一棵FBI樹T，遞歸的構造方法如下：
1) T的根結點為R，其類型與串S的類型相同；
2) 若串S的長度大於1，將串S從中間分開，分為等長的左右子串S1和S2；由左子串S1構造R的左子樹T1，由右子串S2構造R的右子樹T2。
現在給定一個長度為2^N的“01”串，請用上述構造方法構造出一棵FBI樹，並輸出它的後序遍曆[2]序列。
輸入描述 Input Description
輸入的第一行是一個整數N（0 <= N <= 10），第二行是一個長度為2^N的“01”串。
輸出描述 Output Description
輸出t包括一行，這一行隻包含一個字符串，即FBI樹的後序遍曆序列。
樣例輸入 Sample Input
3
10001011
樣例輸出 Sample Output
IBFBBBFIBFIIIFF
數據範圍及提示 Data Size & Hint
對於40%的數據，N <= 2；
對於全部的數據，N <= 10。
不知道為什麼WA，所有數據都能通過.....有空回來繼續解決
思路是對的
#include<stdio.h>
#include<string.h>
#include<math.h>
char a[3000];
struct node
{
char flag;
int L;
int R;
}b[10000];
int n,m,k,x=0;
char Sure(int x,int m)//確定子串類型
{
//printf("@1\n");
int i,f1=0,f2=0;
if(x==m)
{
if(a[x]=='1')
return 'I';
else
return 'B';
}
else
{
for(i=x;i<=m;i++)
{
if(a[i]=='0') f1=1;
else
if(a[i]=='1') f2=1;
}
if(f1==1&&f2==1)
return 'F';
else if(f1==0&&f2==1)
return 'I';
else
return 'B';
}
}
void BuildTree(int k,int x,int m)//建立二叉樹
{
//printf("@2 x=%d m=%d\n",x,m);
b[k].flag=Sure(x,m);
if(m==x)
return;
else
{
b[k].L=2*k;
BuildTree(2*k,x,(m+x)/2);
b[k].R=2*k+1;
BuildTree(2*k+1,(m+x)/2+1,m);
}
}
void Ergodic(int u)//後續遍曆二叉樹
{
//printf("@3\n");
if(b[u].L!=0)
Ergodic(b[u].L);
if(b[u].R!=0)
Ergodic(b[u].R);
printf("%c",b[u].flag);
}
int main()
{
int i,v1=0,v2=0;
scanf("%d",&n);
memset(b,0,sizeof(b));//清零
m=(int)pow(2,n);
getchar();
for(i=1;i<=m;i++)
scanf("%c",&a[i]);
k=1;
BuildTree(k,1,m);
Ergodic(1);
printf("\n");
return 0;
}
最後更新：2017-04-03 12:56:00