- FBI树
- 2015-09-12 17:06:37 @
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _tree
{
struct _tree *rchild;
struct _tree *lchild;
char c;
}Tree;
char Type01(char *sz01,int L)
{// 判断是什么串
char c;
c = sz01[0];
for (int i=1;i<L;i++)
if (sz01[i]!=c)
return 'F';
return sz01[0]=='0'?'B':'I';
}
void rebuild(char *s,int L,Tree ** Root)
{
Tree * newnode;
newnode = new Tree;
newnode->lchild=newnode->rchild=NULL;
newnode->c=Type01(s,L);
if (*Root==NULL)
*Root = newnode;
if (L==1)
return ;
int sub_len;
sub_len = L/2;
if (sub_len>0) // 左边树
{
rebuild(s,sub_len,&newnode->lchild);
rebuild(&s[sub_len],sub_len,&newnode->rchild);
}
}
void printTree(Tree * root)
{
if (!root)
return ;
printTree(root->lchild);
printTree(root->rchild);
printf("%c",root->c);
}
int main()
{
int n;
int s;
char *buffer;
Tree *root = NULL;
scanf("%d",&n);
s=2<<n-1;
buffer = new char[s+1];
scanf("%s",buffer);
rebuild(buffer,s,&root);
printTree(root);
}
//2^n == 2<<n-1