刷题之FBI树

简介: 刷题之FBI树

84a50d407ff34fd18271cc2008b909dd.png

一、题目解读

看题目我们可以知道要先输入一个数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';
    }

题目所给样例的递归过程如下:




001d94bf0b5f4debacda84c361952336.png



cada52125bd348618067cf7b374ffb8e.png

后序遍历: 在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';
    }
}


目录
相关文章
|
9月前
|
存储 缓存 算法
5.链表导论心法
5.链表导论心法
79 1
|
3月前
|
算法 安全 NoSQL
2024重生之回溯数据结构与算法系列学习之顺序表习题精讲【无论是王道考研人还真爱粉都能包会的;不然别给我家鸽鸽丢脸好嘛?】
顺序表的定义和基本操作之插入;删除;按值查找;按位查找习题精讲等具体详解步骤以及举例说明
|
9月前
【一刷《剑指Offer》】面试题 18:树的子结构
【一刷《剑指Offer》】面试题 18:树的子结构
|
9月前
|
存储 算法 关系型数据库
【面试普通人VS高手系列】b树和b+树的理解
【面试普通人VS高手系列】b树和b+树的理解
|
9月前
|
Windows
孤独的树(牛客月赛)
孤独的树(牛客月赛)
52 0
|
算法 Android开发 容器
LeetCode 周赛上分之旅 #35 两题坐牢,菜鸡现出原形
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
110 0
|
机器学习/深度学习 人工智能 算法
LeetCode 周赛 345(2023/05/14)体验一题多解的算法之美
大家好,我是小彭。这场周赛是 LeetCode 第 345 场单周赛,整体难度不高,我们使用一题多解的方式强化练习。
153 0
|
存储 移动开发
【蓝桥杯集训·每日一题】AcWing 1497. 树的遍历
文章目录 一、题目 1、原题链接 2、题目描述 二、解题报告 1、思路分析 2、时间复杂度 3、代码详解 三、知识风暴 递归
83 0