洛谷：P1087 FBI树 P1030 求先序排列 P1305 新二叉树

至于为啥把这三个题放到一起，大概是因为洛谷的试炼场吧，三道树的水题，首先要理解

先序中序后序遍历方法。

fbi树由于数量小，在递归每个区间时，暴力跑一遍区间里的数，看看是否有0和1。至于递归的方法，二分递归就行。

新二叉树就是现根据题意建树，然后求先序遍历时看一下子节点不是‘*’不是才继续向下走

求先序遍历就是用地贵的方式实现，从后序遍历我们可以找出根节点，从中序遍历我们可以找到左右子树。

/*FBI树*/

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define maxn 56281

using namespace std;

int n;

char nam[maxn];

int qq[maxn];

void build(int l,int r)

{

     int  mid=(l+r)/;

     if(l!=r)

     {

         build(l,mid);

         build(mid+,r);

     }

     int n0=,n1=;

     for(int i=l;i<=r;i++)

     {

         if(qq[i]==)n1++;

         if(qq[i]==)n0++;

         if(n1&&n0)

         {

             printf("F");

             return;

        }

     }

     printf(n1==?"B":"I");

}

int main()

{

    scanf("%d",&n);

    scanf("%s",nam);

    int len=strlen(nam);

    for(int i=;i<=len;i++)

    {

        qq[i]=nam[i-]-'';

    }

    build(,len);

    return ;

}

/*新二叉树*/

#include<cstdio>

#include<iostream>

#include<algorithm>

using namespace std;

struct root

{

    char father;

    char rc;

    char lc;

    root()

    {

        father='?';

        lc='?';

        rc='?';

    }

}tree[];

void dfs(char x)

{

    printf("%c",x);

    if(tree[x].lc!='*')dfs(tree[x].lc);

    if(tree[x].rc!='*')dfs(tree[x].rc);

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        char a,b,c;

        cin>>a>>b>>c;

        tree[a].lc=b;

        tree[a].rc=c;

        tree[b].father=a;

        tree[c].father=a;

    }

    for(int i=;i<=;i++)

    {

        if(tree[i].father=='?'&&tree[i].lc!='?'&&tree[i].rc!='?')

        {

            dfs(i);

            break;

        }

    }

    return ;

} 

/*求先序遍历*/

#include<cstdio>

#include<iostream>

#include<string>

using namespace std;

string a,b;

void qla(int ln,int rn,int l,int r)

{

    int place=a.find(b[r]);

    cout<<b[r];

    if(place>ln)qla(ln,place-,l,place-ln+l-);//两棵子树

    if(place<rn)qla(place+,rn,place-ln+l,r-);

}

int main()

{

    cin>>a>>b;

    int len=a.size();

    qla(,len-,,len-);

    return ;

}

/*

BADC

BDCA

*/