@java蓝桥杯B组习题算法训练篇（241）第27题：FBI树&二叉树

Dear 丶 2023-07-18 14:09 25阅读 0赞

## 关键字：二叉树、遍历、递归、循环 ##

## 问题描述 ##

我们可以把由“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树，并输出它的后序遍历序列。  
输入格式  
　　第一行是一个整数N（0 <= N <= 10），第二行是一个长度为2N的“01”串。  
输出格式  
　　包括一行，这一行只包含一个字符串，即FBI树的后序遍历序列。  
样例输入  
3  
10001011  
样例输出  
IBFBBBFIBFIIIFF  
数据规模和约定  
　　对于40%的数据，N <= 2；  
　　对于全部的数据，N <= 10。  
　　注：  
　　\[1\] 二叉树：二叉树是结点的有限集合，这个集合或为空集，或由一个根结点和两棵不相交的二叉树组成。这两棵不相交的二叉树分别称为这个根结点的左子树和右子树。  
　　\[2\] 后序遍历：后序遍历是深度优先遍历二叉树的一种方法，它的递归定义是：先后序遍历左子树，再后序遍历右子树，最后访问根。

## 代码部分： ##

**这道题刚开始我也不怎么懂，后来在网上找到了一份答案，哈哈，可以说是白嫖了，我在一应位置添加了一些我的理解大家来帮我看看有没有哪里不对呀，哈哈哈，多谢指正啊**！！！！！~~

public class ALGO027 {
        
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		java.util.Scanner in=new java.util.Scanner(System.in);
    		int n=in.nextInt();
    		String s=in.next();
    		post_order(0,s.length()-1,s);
    		in.close();
    	}
    	//后序遍历--->递归思想
    	private static void post_order(int l,int r,String s){
        
    		int mid=(l+r)/2;//控制分割的位置：在字符串的正中间分割开
    		//先全部分割完，然后把全部结点标记之后再输出。
    		if(l!=r){
        //分割：知道r=l=0才停止分割
    			post_order(l,mid,s);//左子树
    			post_order(mid+1,r,s);//右子树
    		}
    		//设置标记判断字符
    		int flag1=0,flag2=0;//定义判断的变量
    		for(int i=l;i<=r;i++){
        //标记判断字符（变量）并且根据01字符串（这里的字符串是已经不可再分割的字符串）给控制输出的两个变量flag1、flag2赋上对应的值
    			if(s.charAt(i)=='0') flag1=1;
    			if(s.charAt(i)=='1') flag2=1;
    		}
    		//根据判断字符变量来输出对应的字母：B、I、F
    		if(flag1==1&&flag2==0) System.out.print("B");//只有0
    		if(flag1==0&&flag2==1) System.out.print("I");//只有1
    		if(flag1==1&&flag2==1) System.out.print("F");//既有0又有1
    	}
    }