P1440 FBI树

2024-01-21 10:58

文章标签 fbi p1440

本文主要是介绍P1440 FBI树，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述 Description

我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。
    FBI树是一种二叉树1，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2^N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下：
    1) T的根结点为R，其类型与串S的类型相同；
    2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。
    现在给定一个长度为2^N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历2序列。

输入格式 InputFormat

输入的第一行是一个整数N(0<=N<=10)，第二行是一个长度为2^N的“01”串。

输出格式 OutputFormat

输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。

解题思路：

　　先模拟建立二叉树，之后后序遍历。

代码：

#include <stdio.h>
#include <string.h>
#define N 1050
char str[N];
typedef struct LNode
{
char f;
LNode *l,*r;
}LNode,*LinkList;
LinkList root;
int Pan(int start,int end)
{
int flag1=1,flag2=1,flag3=1;
for(int i=start;i<end;i++)
{
if(str[i]!='0') flag1=0;
if(str[i]!='1') flag2=0;        
}
if(flag1) return 1;
else if(flag2) return 2;
else return 3;
}
void Search(int start,int end,int flag,LinkList &L)
{
//建立二叉树；
if(start==end) L=NULL;
else
{    
L=new LNode;/*char m=str[end];str[end]='\0';
strcpy(L->f,&str[start]);str[end]=m;*/
int p=Pan(start,end);
if(p==1) L->f='B';
else if(p==2) L->f='I';
else L->f='F';
/*int q=end;*/
/*end=end-(end-start+1)/2;*/
int len=end-start;
Search(start,end-(len+1)/2,1,L->l);//建立左边的；
/*start=end+1;end=q;*/
Search(start+(len+1)/2,end,2,L->r);//建立右边的；
    }
}
void Hou(LinkList L)
{
if(L)
{
Hou(L->l);
Hou(L->r);
printf("%c",L->f);
}
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
scanf("%s",str);int len=strlen(str);
Search(0,len,0,root);
Hou(root);
printf("\n");
}
return 0;
}