[NOIP2004 普及組] FBI 樹(shù)

題目描述:

我們可以把由 0 和 1 組成的字符串分為三類(lèi)：全 0 串稱(chēng)為 B 串，全 1 串稱(chēng)為 I 串，既含 0 又含 1 的串則稱(chēng)為 F 串。

FBI 樹(shù)是一種二叉樹(shù)，它的結(jié)點(diǎn)類(lèi)型也包括 F 結(jié)點(diǎn)，B 結(jié)點(diǎn)和 I 結(jié)點(diǎn)三種。由一個(gè)長(zhǎng)度為 $2^N$ 的 01 串 S 可以構(gòu)造出一棵 FBI 樹(shù) T，遞歸的構(gòu)造方法如下：

1. T?的根結(jié)點(diǎn)為 R，其類(lèi)型與串 S?的類(lèi)型相同；
2. 若串 S?的長(zhǎng)度大于 1，將串 S 從中間分開(kāi)，分為等長(zhǎng)的左右子串 S1?和 S2；由左子串 S1?構(gòu)造 R 的左子樹(shù) T1，由右子串 S2?構(gòu)造 R?的右子樹(shù) T2。

現(xiàn)在給定一個(gè)長(zhǎng)度為 2^N?的 01 串，請(qǐng)用上述構(gòu)造方法構(gòu)造出一棵 FBI 樹(shù)，并輸出它的后序遍歷序列。

輸入格式

第一行是一個(gè)整數(shù)?N(0≤N≤10)，

第二行是一個(gè)長(zhǎng)度為?2^N 的 01 串。

輸出格式

一個(gè)字符串，即 FBI 樹(shù)的后序遍歷序列。

輸入輸出樣例

輸入 #1:

3
10001011

輸出 #1:

IBFBBBFIBFIIIFF

說(shuō)明/提示

對(duì)于?%40%?的數(shù)據(jù),N≤2；

對(duì)于全部的數(shù)據(jù)，N≤10。

noip2004普及組第3題。

題目大意：

???題目大意就是給定一個(gè)序列，就比如10001011，我們將這個(gè)序列一直從中間分開(kāi)，左邊為左子樹(shù)，右邊為右子樹(shù)，根據(jù)每一段全0全1還是10都有得到值F、B、I，構(gòu)建成一棵二叉樹(shù)，并且倒序輸出。

遞歸解法：

? 這個(gè)解法比隊(duì)列解法要簡(jiǎn)單許多。

[NOIP2004 普及組] FBI 樹(shù) 遞歸解法http://t.csdn.cn/YK8MW

隊(duì)列解法：

如何得到一個(gè)二叉樹(shù)的后序輸出？

我們只需要得到這顆二叉樹(shù)的層次遍歷放在一個(gè)數(shù)組中即可，后序遍歷代碼如下
（大致思路就是先判斷左子樹(shù)是否存在，如果存在就遍歷，然后遍歷右子樹(shù)，最后輸出根節(jié)點(diǎn)）

void print(ll h) {
    ll l=h*2,r=h*2+1;
    if(l<=size) 
	  print(l);
    if(r<=size) 
	  print(r);
    cout<<S[h];
}

現(xiàn)在我們只需要得到這個(gè)二叉樹(shù)的層次遍歷數(shù)組即可

對(duì)于一開(kāi)始這個(gè)序列，我們從中間分開(kāi)，也就是分成1000 和 1011兩部分，最開(kāi)始這個(gè)既有0又有1，所以根節(jié)點(diǎn)是F，F(xiàn)的左子樹(shù)是1000也就是F，右子樹(shù)1011也是F，我們將這三個(gè)值依次存到層次遍歷數(shù)組中。

接下來(lái)我們要遍歷左子樹(shù)分開(kāi)兩部分的值，注意如果是層次遍歷的話，我們不能簡(jiǎn)單的用遞歸來(lái)解決，如果用遞歸的話，我們會(huì)一直遞歸到最深的那個(gè)葉節(jié)點(diǎn)之后再開(kāi)始向右。

如下圖，我們需要依次將10 00 10 11的值放入層次遍歷數(shù)組，但是如果我們使用遞歸來(lái)解決兩個(gè)范圍的話，類(lèi)似如下圖中的代碼，我們會(huì)先解決左邊部分再解決右邊部分。第一次分成10和00，然后進(jìn)入10分成1 和 0存進(jìn)數(shù)組之后出來(lái)進(jìn)入右邊的00，然后再進(jìn)去存放兩個(gè)0。

然而我們的需求是先把1000分開(kāi)成兩個(gè)值存入數(shù)組之后直接遍歷1011，而不是繼續(xù)遍歷1000的子樹(shù)，子樹(shù)部分我們應(yīng)該放在下一個(gè)范圍解決

那么該怎么解決這個(gè)問(wèn)題呢
我們分成1000和1011之后，不是要將這兩個(gè)范圍繼續(xù)分小，然后存入層次遍歷數(shù)組嗎？那么我們可以將沒(méi)有處理的存到一個(gè)數(shù)據(jù)結(jié)構(gòu)中，1000分成10和00之后，我們暫時(shí)不處理這兩個(gè)范圍，將他們存入數(shù)據(jù)結(jié)構(gòu)留到后面處理。
那么哪種數(shù)據(jù)結(jié)構(gòu)適合存放數(shù)據(jù)呢，我們來(lái)思考一下存放的特點(diǎn)，先存進(jìn)去的先處理，后存進(jìn)去的后處理，而這剛好符合一種數(shù)據(jù)結(jié)構(gòu)——隊(duì)列，對(duì)于1000和1011，我們先處理1000，分成兩部分10和00之后，我們暫時(shí)不處理這兩個(gè)范圍，將他們存入隊(duì)列，之后再處理1011，分成10和11之后同理也是存入隊(duì)列，這時(shí)隊(duì)列的結(jié)構(gòu)是這樣的

分別將這四個(gè)對(duì)應(yīng)的字母10(F) 00(B) 10(F) 11(I)存入層次遍歷數(shù)組之后，我們從隊(duì)首取得10，然后做進(jìn)一步的處理，將處理之后的值繼續(xù)存入隊(duì)列表明下一層要處理的范圍。

就這樣直到隊(duì)列中沒(méi)有一個(gè)元素表明這顆FBI樹(shù)已經(jīng)全部構(gòu)造完成，那么相應(yīng)的層次遍歷數(shù)組也得到了，我們?cè)儆蒙厦娴拇a輸出這棵樹(shù)的后序即可

分析代碼

對(duì)于隊(duì)列，你可以使用stl庫(kù)中的隊(duì)列，在這里我自己用數(shù)組模擬了一個(gè)隊(duì)列，當(dāng)然你也可以手寫(xiě)一個(gè)隊(duì)列
我們將最開(kāi)始的范圍也就是從1到2^N存入隊(duì)列，這也是我們要處理的第一個(gè)元素

head指向我們當(dāng)前隊(duì)列的頭部，tail是我們隊(duì)列的尾部，也就是目前最后要處理的一個(gè)數(shù)據(jù)，隊(duì)列從0開(kāi)始計(jì)數(shù)，tail的位置沒(méi)有數(shù)據(jù)，對(duì)于每一個(gè)范圍有一個(gè)左邊界一個(gè)有邊界，所以我們定義一個(gè)結(jié)構(gòu)體，每次把這個(gè)結(jié)構(gòu)體存入隊(duì)列

struct Node{
    ll l,r;
}Q[10020];

    ll h=-1,d=1,p,q;
    Q[++h].l=l;
    Q[h].r=r;

只要當(dāng)前隊(duì)列有元素我們就需要處理，所以循環(huán)的退出條件為head==tail(表明隊(duì)列頭已經(jīng)到隊(duì)列尾空的地方)

每次用head取到當(dāng)前隊(duì)列的頭部，zero和one用來(lái)判斷這個(gè)范圍是全1還是全0（如果中間有一個(gè)1，那么全0 zero就為假，如果中間有一個(gè)0，那么全1 one就為假，最后如果兩個(gè)都為假說(shuō)明兩個(gè)都有即為F，I和B依次類(lèi)推）

處理完這個(gè)范圍之后，我們將這個(gè)數(shù)據(jù)排出隊(duì)列，然后插入層次遍歷數(shù)組（cnt表示當(dāng)前遍歷數(shù)組的個(gè)數(shù)，初始為0），也就是head++，如果這個(gè)范圍下面有子范圍，那么我們將子范圍分成兩個(gè)部分繼續(xù)插入隊(duì)列尾部

    bool f1,f2;
    while(h<d){
        p=Q[h].l;
        q=Q[h].r;
        f1=f2=true;
        for(ll i=p;i<=q;i++){
            if(T[i]=='1') 
			  f1=false;
            else if(T[i]=='0') 
			  f2=false;
        }
        if(!f1&&!f2)
          S[++size]='F';
        else if(f2&&!f1)
          S[++size]='I';
        else if(f1&&!f2)
          S[++size]='B';
        h++;
        if(p<q){
            Q[d].l=p;
            Q[d++].r=(p+q)/2;
            Q[d].l=(p+q)/2+1;
            Q[d++].r=q;
        }
    }

得到層次遍歷數(shù)組之后我們直接后序遍歷即可

完整代碼如下:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,size;
char S[10020];
char T[1050];
struct Node{
    ll l,r;
}Q[10020];
inline ll read(){
    ll x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')
          f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=(x<<1)+(x<<3)+(c^48);
        c=getchar();
    }
    return x*f;
}
void print(ll h) {
    ll l=h*2,r=h*2+1;
    if(l<=size) 
	  print(l);
    if(r<=size) 
	  print(r);
    cout<<S[h];
}
void FBI(ll l,ll r){
    ll h=-1,d=1,p,q;
    Q[++h].l=l;
    Q[h].r=r;
    bool f1,f2;
    while(h<d){
        p=Q[h].l;
        q=Q[h].r;
        f1=f2=true;
        for(ll i=p;i<=q;i++){
            if(T[i]=='1') 
			  f1=false;
            else if(T[i]=='0') 
			  f2=false;
        }
        if(!f1&&!f2)
          S[++size]='F';
        else if(f2&&!f1)
          S[++size]='I';
        else if(f1&&!f2)
          S[++size]='B';
        h++;
        if(p<q){
            Q[d].l=p;
            Q[d++].r=(p+q)/2;
            Q[d].l=(p+q)/2+1;
            Q[d++].r=q;
        }
    }
}
int main(){
    n=read();
    for(ll i=1;i<=pow(2,n);i++)
      cin>>T[i];
    FBI(1,pow(2,n));
    print(1);
    return 0;
}

?總結(jié)：

? 此題較為簡(jiǎn)單，還有一種直接遞歸的方式可以實(shí)現(xiàn)。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-472143.html

題目鏈接：[NOIP2004 普及組] FBI 樹(shù) - 洛谷https://www.luogu.com.cn/problem/P1087

到了這里，關(guān)于[NOIP2004 普及組] FBI 樹(shù) 隊(duì)列解法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！