一、题目解读
看题目我们可以知道要先输入一个数N，再输入2^N个数。
这就告诉我们了，这是一颗满二叉树，N的范围0到10，也就是说这颗树总共有N+1层，最多是十一层，并且由我们输入了最后一层FBI树的值，然后题目要求我们写代码根据最后一层的FBI树的值去构建整棵树，再输出FBI树的后序遍历。
全 “0” 串称为 B 串，全 “1” 串称为 I 串，既含 “0” 又含 “1” 的串则称为 F 串。
二、思路分析
因为这棵树最多十一层，所以该颗树总共有2^10=1024，1024*2-1=2047个节点，我们取整2050（并且可以从下标为1开始存放FBI树的值），因此我们创建一个大小为2050的数组，去装下整颗树，创建一个大小为1025的数组，去存放最后一层的值。
构建完整的满二叉树：我们先要判断最后一层FBI树所对应的值，再一层层向上构建树，因为最后一层没有字节点了，所以最后一层是什么那它对应的FBI树的值就是什么，为’0‘就是B串，为’1‘就是I串。
//root表示当前fbi树的根，left表示构建当前fbi树的s[]序列的左下标，right表示构建当前fbi树的s[]序列的右下标 private static void build_FBI(int root, int left, int right) { //到达叶子结点 if (right == left) { //判断当前节点的FBI属性 if (s[left] == '0') { tree[root] = 'B'; } else tree[root] = 'I'; //返回 return; } //分成两半 1 8 1-4 5-8 int mid = (left + right) / 2; //递归左子 build_FBI(2 * root, left, mid); //递归右子 build_FBI(2 * root+1, mid+1, right); //左右儿子都是B if (tree[2 * root] == 'B' && tree[2 * root+1] == 'B') { tree[root] = 'B'; //左右儿子都是I } else if (tree[2 * root] == 'I' && tree[2 * root+1] == 'I') { tree[root] = 'I'; }else tree[root]='F'; }
题目所给样例的递归过程如下：
后序遍历： 在Java中数组未被赋值，会被默认赋值为零，除了String和boolean类型的数组。因此用0来判断当前数组的值是否为该满二叉树的值，来结束后续遍历递归，然后开始输出。
//v表示后续遍历fbi树的根结点下标 private static void postorder(int v) { // 在Java中数组未被赋值，会被默认赋值为零，除了String和boolean类型的数组， //因此用0来判断当前数组的值是否为该满二叉树的值 //如果当前根结点有左子树，则后续遍历左子树 if(tree[2*v]!=0){ postorder(2 * v); } //如果当前根结点有右子树，则后续遍历右子树 if(tree[2*v+1]!=0){ postorder(2 * v+1); } //输出根信息 System.out.print(tree[v]); }
三、代码
import java.util.Scanner; public class Main{ public static String read_str; public static final int TREE_SIZE=2050; public static final int S_SIZE=1025; public static char tree[]=new char[TREE_SIZE];//2050 public static char s[]=new char[S_SIZE];//1024 public static void main(String[] arge){ Scanner sc = new Scanner(System.in); //读取n int n=sc.nextInt(); //读取序列字符串 String str=sc.next(); //将读取的序列字符串存入s数组 1 8 1-4 5-8 //0-7 0-3 4-7 for(int i=1;i<=str.length();i++){ s[i]=str.charAt(i-1); } //递归调用方法来构建fbi树 build_FBI(1,1,str.length()); //递归调用方法来后续遍历fbi树 postorder(1); } //v表示后续遍历fbi树的根结点下标 private static void postorder(int v) { // TODO Auto-generated method stub //如果当前根结点有左子树，则后续遍历左子树 if(tree[2*v]!=0){ postorder(2 * v); } //如果当前根结点有右子树，则后续遍历右子树 if(tree[2*v+1]!=0){ postorder(2 * v+1); } //输出根信息 System.out.print(tree[v]); } //root表示当前fbi树的根，left表示构建当前fbi树的s[]序列的左下标，right表示构建当前fbi树的s[]序列的右下标 private static void build_FBI(int root, int left, int right) { // TODO Auto-generated method stub //到达叶子结点 if (right == left) { //判断当前节点的FBI属性 if (s[left] == '0') { tree[root] = 'B'; } else tree[root] = 'I'; //返回 return; } //分成两半 1 8 1-4 5-8 int mid = (left + right) / 2; //递归左子 build_FBI(2 * root, left, mid); //递归右子 build_FBI(2 * root+1, mid+1, right); //左右儿子都是B if (tree[2 * root] == 'B' && tree[2 * root+1] == 'B') { tree[root] = 'B'; //左右儿子都是I } else if (tree[2 * root] == 'I' && tree[2 * root+1] == 'I') { tree[root] = 'I'; }else tree[root]='F'; } }
