至于为啥把这三个题放到一起，大概是因为洛谷的试炼场吧，三道树的水题，首先要理解
先序中序后序遍历方法。
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)/2; if(l!=r) { build(l,mid); build(mid+1,r); } int n0=0,n1=0; for(int i=l;i<=r;i++) { if(qq[i]==1)n1++; if(qq[i]==0)n0++; if(n1&&n0) { printf("F"); return; } } printf(n1==0?"B":"I"); } int main() { scanf("%d",&n); scanf("%s",nam); int len=strlen(nam); for(int i=1;i<=len;i++) { qq[i]=nam[i-1]-'0'; } build(1,len); return 0; }
/*新二叉树*/ #include<cstdio> #include<iostream> #include<algorithm> using namespace std; struct root { char father; char rc; char lc; root() { father='?'; lc='?'; rc='?'; } }tree[2001]; 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=1;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=1;i<=2000;i++) { if(tree[i].father=='?'&&tree[i].lc!='?'&&tree[i].rc!='?') { dfs(i); break; } } return 0; }
/*求先序遍历*/ #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-1,l,place-ln+l-1);//两棵子树 if(place<rn)qla(place+1,rn,place-ln+l,r-1); } int main() { cin>>a>>b; int len=a.size(); qla(0,len-1,0,len-1); return 0; } /* BADC BDCA */