Tree

refer to : https://mp.weixin.qq.com/s/LsgDnr43hVH0dAjF1WHPkw

JAVA中树形结构

3.1 JAVA中树形对象的定义

在JAVA中树形结构是通过对象嵌套方式来定义的，如MenuVo对象中有一个子对象subMenus：

public class MenuVo {
    private Long id;
    private Long pId;
    private String name;
    private Integer rank=0;
    private List<MenuVo> subMenus=new ArrayList<>();
}

3.2 JSON数据格式中的树形结构

JSON数据天然就是树形结果，如以下展示一个简单的JSON树形结构：

[
    {
        "id": 0,
        "subMenus": [
            {
                "id": 2,
                "subMenus": [
                    {
                        "id": 5,
                        "pid": 2
                    }
                ],
                "pid": 0
            }
        ],
        "pid": -1
    }
]

3.3 树形数据结构的储存

像文档型数据库MongDB、ElasticSearch可以直接存储JSON这种树形数据，

而像Mysql这种关系型数据库不太适合直接存储具有上下级关系的树形数据，大都是按行存储然后通过id、pid之间关联上下级关系，这就导致我们需要经常将Mysql中的关系型数据转成JSON这种数据结构，

因而TreeUtil这类数据转换工具类就起诞生了。

TreeUtil代码分析

4.1 makeTree()构建树

直接看这神一样的方法makeTree()：

public class TreeUtil {
    
    public static <E> List<E> makeTree(List<E> list, Predicate<E> rootCheck,
                                       BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> setSubChildren) {
        return list.stream().filter(rootCheck)
                .peek(x -> setSubChildren.accept(x, makeChildren(x, list, parentCheck, setSubChildren)))
                .collect(Collectors.toList());
    }
    
    private static <E> List<E> makeChildren(E parent, List<E> allData, 
                                            BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> setSubChildren) {
        return allData.stream().filter(x -> parentCheck.apply(parent, x))
                .peek(x -> setSubChildren.accept(x, makeChildren(x, allData, parentCheck, setSubChildren)))
                .collect(Collectors.toList());
    }
}

是不是完全看不懂？像看天书一样？makeTree方法为了通用使用了泛型+函数式编程+递归，正常人一眼根本看不这是在干什么的，我们先不用管这个makeTree合成树的代码原理，先直接看如何使用:

 public static void main(String[] args) {
        MenuVo menu0 = new MenuVo(0L, -1L);
        MenuVo menu1 = new MenuVo(1L, 0L);
        MenuVo menu2 = new MenuVo(2L, 0L);
        MenuVo menu3 = new MenuVo(3L, 1L);
        MenuVo menu4 = new MenuVo(4L, 1L);
        MenuVo menu5 = new MenuVo(5L, 2L);
        MenuVo menu6 = new MenuVo(6L, 2L);
        MenuVo menu7 = new MenuVo(7L, 3L);
        MenuVo menu8 = new MenuVo(8L, 3L);
        MenuVo menu9 = new MenuVo(9L, 4L);
        //基本数据
        List<MenuVo> menuList = Arrays.asList(menu0,menu1, menu2,menu3,menu4,menu5,menu6,menu7,menu8,menu9);
        //合成树
        List<MenuVo> tree= TreeUtil.makeTree(menuList, x->x.getpId()==-1L,
                (x, y)->x.getId().equals(y.getpId()), MenuVo::setSubMenus);
        System.out.println(JSON.toJSONString(tree));


    }

我们结合这个简单的合成菜单树看一下这个makeTree()方法参数是如何使用的：

• 第1个参数List list，为我们需要合成树的List，

  如上面Demo中的menuList

• 第2个参数Predicate rootCheck，判断为根节点的条件，

  如上面Demo中pId==-1就是根节点

• 第3个参数parentCheck 判断为父节点条件，

  如上面Demo中 id==pId

• 第4个参数setSubChildren，设置下级数据方法

  如上面Demo中：Menu::setSubMenus

天书方法拆解

去掉泛型和函数接口

第一步我们可以把泛型和函数接口去掉，再看一下一个如何使用递归合成树：

public static List<MenuVo> makeTree(List<MenuVo> allDate, Long rootParentId) {
        List<MenuVo> roots = new ArrayList<>();
        // 1、获取所有根节点
        for (MenuVo menu : allDate) {
            if (Objects.equals(rootParentId, menu.getpId())) {
                roots.add(menu);
            }
        }
        // 2、所有根节点设置子节点
        for (MenuVo root : roots) {
            makeChildren(root, allDate);
        }
        return roots;
    }
    public static MenuVo makeChildren(MenuVo root, List<MenuVo> allDate) {
        //遍历所有数据，获取当前节点的子节点
        for (MenuVo menu : allDate) {
            if (Objects.equals(root.getId(), menu.getpId())) {
                makeChildren(menu, allDate);
                //将是当前节点的子节点添加到当前节点的subMenus中
                root.getSubMenus().add(menu);
            }
        }
        return root;
    }

通过上面的两个方法可以合成树的基本逻辑，主要分为三步：

找到所有根节点

遍历所有根节点设置子节点

遍历allDate查询子节点

使用函数优化

看懂上面的代码后，我们再看原先的代码，就比较好理解了

public static <E> List<E> makeTree(List<E> list, Predicate<E> rootCheck,
                                       BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> setSubChildren) {
                // 找到所有的根节点
        return list.stream().filter(rootCheck)
                // 给根节点，设置子节点  这里的x就是根节点
                .peek(x -> setSubChildren.accept(x, makeChildren(x, list, parentCheck, setSubChildren)))
                // 返回根节点的集合
                .collect(Collectors.toList());
    }
    private static <E> List<E> makeChildren(E parent, List<E> allData,
                                            BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> setSubChildren) {
        // 找到根节点下的子节点
        return allData.stream().filter(x -> parentCheck.apply(parent, x))
                // 给子节点设置 孙子节点  这里的x，就是子节点
                .peek(x -> setSubChildren.accept(x, makeChildren(x, allData, parentCheck, setSubChildren)))
                // 返回子节点的集合
                .collect(Collectors.toList());
    }