|Tyvj|NOIP2004|二叉树|P1440 FBI树

时间:2022-04-28 20:49:28

http://tyvj.cn/p/1440

递归建立即可,这里把树给建立出来了

不知道为什么后序遍历那里用root!=NULL不管用。。

一直RE,因为是满二叉树,所以我就用层数判定了

#include<cstdio>
#include<cstring>
using namespace std;
typedef struct node;
typedef node* tree;
struct node {
tree l,r;
char data;
};
int buildTree(tree &root, char *s, int l)
{
if (l==1)
{
root = new node;
if (s[0]=='1')
root->data = 'I';
else root->data = 'B';
}
else
{
root = new node;
buildTree(root->l, s, l / 2);
buildTree(root->r, s + l/2, l / 2);
if (root->l->data=='I' && root->r->data=='I')
root->data = 'I';
else if (root->l->data=='F' && root->r->data=='F')
root->data = 'F';
else if (root->l->data=='B' && root->r->data=='B')
root->data = 'B';
else root->data = 'F';
}
}
int n;
int postOrder(tree root, int d)
{
if (d<=n)
{
postOrder(root->l,d+1);
postOrder(root->r,d+1);
putchar(root->data);
}
}
tree r;
int main ()
{
char s[1050];
scanf("%d%*c", &n);
scanf("%s", s);
buildTree(r, s, (1<<n));
postOrder(r, 0);
return 0;
}