NOIP 2004 普及組 複賽 FBI樹

NOIP 2004 普及組 複賽 FBI樹

1.閱讀題目，還有些不知所雲。

2.對樣例進行手動模拟，弄明白題意了。

10001011

 FBI樹如下圖所示

F

F     F

F  B  F  I

I B B B I B I I

1) T的根結點為R，其類型與串S的類型相同；此句是核心中的核心，也即F B I三種根節點。

3.接下來程式設計實作是重點。先建樹，子弟相信行一層一層建樹，用一維數組存儲，第1号(第0号不使用)元素開始使用數組。父k,左子2*k,右子2*k+1。再進行周遊，後序周遊，采用遞歸的方式。

4.建樹函數，周遊函數編寫。

5.代碼編寫完成，送出AC，遞歸函數寫法，記得先寫終結條件。

6.此文寫得不錯，讀者也可以借鑒。http://blog.csdn.net/dogeding/article/details/52727239

7.此題，可以借鑒的是：二叉樹的存儲，二叉樹的周遊。

附上AC代碼，編譯環境Dev-C++4.9.9.2

#include <stdio.h>

int n;

char a[1024+10];

char b[2048+10];

void build(char *s,int n){//建樹代碼

    //底層構造

    int i,j=0;

    for(i=(1<<n);i<=(1<<(n+1))-1;i++){

        b[i]=a[j++]=='0'?'B':'I';

    }

    //自底向上構造

    for(i=n-1;i>=0;i--)

        for(j=(1<<i);j<=(1<<(i+1))-1;j++)

            if(b[2*j]=='B'&&b[2*j+1]=='B')

                b[j]='B';

            else if(b[2*j]=='I'&&b[2*j+1]=='I')

                b[j]='I';

            else

                b[j]='F';

}

void visit(int node){//後序周遊代碼

    if(node>(1<<(n+1))-1)

        return;

    visit(node*2);//左子樹

    visit(node*2+1);//右子樹

    printf("%c",b[node]);//根

}

int main(){

    scanf("%d",&n);

    scanf("%s",a);

    build(a,n);

    visit(1);

    printf("\n");

    return 0;

}