Problem description 我们可以把由“0”和“1”组成的字符串分为三类：全“0”串称为B串，全“1”串称为I串，既含“0”又含“1”的串则称为F串。 FBI树是一种二叉树 ，它的结点类型也包括F结点，B结点和I结点三种。由一个长度为2N的“01”串S可以构造出一棵FBI树T，递归的构造方法如下： 1) T的根结点为R，其类型与串S的类型相同；2) 若串S的长度大于1，将串S从中间分开，分为等长的左右子串S1和S2；由左子串S1构造R的左子树T1，由右子串S2构造R的右子树T2。 现在给定一个长度为2N的“01”串，请用上述构造方法构造出一棵FBI树，并输出它的后序遍历序列。  Input 输入第一行是一个整数N(0 <= N <= 10)，第二行是一个长度为2N的“01”串。  Output 输出包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。  Sample Input 310001011 Sample Output IBFBBBFIBFIIIFF Judge Tips 1.二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。 2.后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。  Problem Source NOIP2004 /* 编译环境 VC ++ */ #include <stdio.h>#include <string.h>#include <malloc.h> typedef struct Tree  /* 以二叉树结构存储结果 */{ char  data;  int  flag;  struct Tree *lchild;  struct Tree *rchild;}TREE; struct Stack{ TREE  *tree;  struct Stack *next;}; void get(char *str,int len,TREE *node){ char  *sub1,*sub2;  int i,j;    if( len == 1 && str[0] == '1') { node -> data = 'I';   node -> lchild = NULL;   node -> rchild = NULL;   return ; }  else if( len == 1 && str[0] == '0' ) { node -> data = 'B';   node -> lchild = NULL;   node -> rchild = NULL;   return ; }  else if( !strchr(str,'1') )  node -> data = 'B';  else if( !strchr(str,'0') )  node -> data = 'I';  else    node -> data = 'F';   sub1 = (char*)malloc(len/2 + 2); /* 递归测试 str的前半部分 */  sub2 = (char*)malloc(len/2 + 2); /* 递归测试 str的后半部分 */  for(i = 0,len = len >> 1,j = len; i < len; i ++,j ++)      {  sub1[i] = str[i];  sub2[i] = str[j];      }  sub1[i] = 0;  sub2[i] = 0;  node -> lchild = (TREE*)malloc(sizeof(TREE));  node -> lchild -> flag = 0;  node -> rchild = (TREE*)malloc(sizeof(TREE));  node -> rchild -> flag = 0;  get(sub1,len,node -> lchild);  free( sub1 );  get(sub2,len,node -> rchild);  free( sub2 );} void out(TREE *root)  /* 堆栈方式输出结果 */{ struct Stack *top = NULL,*stemp;  TREE  *temp;  if( !root -> lchild && !root -> rchild ) { printf("%c",root -> data);   return; }  top = (struct Stack*)malloc(sizeof(struct Stack));  top -> next = NULL;  top -> tree = root;  while( top )    { if( (!top -> tree -> lchild && !top -> tree -> rchild) ||    (top -> tree -> lchild -> flag && top -> tree -> rchild -> flag) )   { stemp = top;     printf("%c",top -> tree -> data);     top -> tree -> flag = 1;     top = top -> next;     free(stemp);   }      else{ temp = top -> tree;     if( !temp -> lchild -> flag && temp -> lchild )       {  stemp = (struct Stack*)malloc(sizeof(struct Stack));   stemp -> next = top;   stemp -> tree = temp -> lchild;   top = stemp;       }     else if( temp -> rchild )       {  stemp = (struct Stack*)malloc(sizeof(struct Stack));   stemp -> next = top;   stemp -> tree = temp -> rchild;   top = stemp;       }    else { printf("%c",temp -> data);    temp -> flag = 1;    stemp = top;    top = top -> next;    free( stemp );   } }   }} void free_mem(TREE *root) /* 递归方式释放二叉树 */{ if( !root -> lchild && !root -> rchild ) { free( root );   return ; }  else if( root -> lchild )  free_mem( root -> lchild );   else   free_mem( root -> rchild );} int main(){ char  str[1100];  int len;  TREE  *root = NULL;    scanf("%d",&len);  while(scanf("%s",str) != EOF) /* 输入 ctrl + z 退出测试*/ { root = (TREE*)malloc(sizeof(TREE));   root -> flag = 0;   len = strlen(str);   get(str,len,root);   out( root );   free_mem(root); }  return 0;}

评论