当前位置： 首页 > news >正文

解密阿里大神写的天书般的Tree工具类，轻松搞定树结构！

news 来源：原创 2024/9/23 19:28:45

首发公众号：赵侠客

一、引言

最近公司新进了不少新人，包括一些来自阿里、网易等大型企业的资深工程师。我们组的一位新同事是阿里来的专家，我在CR（Code Review, 简称CR）时看到了他编写的一个关于树操作的工具类，对其设计和实现深感佩服。为了进一步理解和学习，我对这个工具类进行了深入分析和整理，现在在本文中与大家分享。

二、树形结构介绍

2.1 简单的二叉树

首页简单简介一下树形数据结构，树形数据结构是一种层级化的数据组织方式，广泛用于表示具有层次关系的数据。由于其层级化组织特点，树形数据结构能够高效支持多种查找、插入和删除操作，因此在计算机科学和实际应用中得到了广泛应用。下面是一个简单的二叉树示例：

二叉树及遍历算法

▲二叉树及遍历算法

2.2 树的应用场景

树形数据结构的应用场景是通过ID关联上下级关系的对象，然后将这些对象组织成一棵树。主要有以下常用应用场景：

  1. 部门通讯录：通讯录中可以通过树形结构展示不同部门及其上下级关系，便于用户快速找到联系人
  2. 系统菜单： 系统中的菜单通常是分层的，通过树形结构可以方便地展示和管理各级菜单项
  3. 地址选择器：地理地址通常有多级关系，如省、市、县，通过树形结构可以方便用户选择具体的地址
  4. 文件夹目录： 文件系统中的文件夹和文件可以通过树形结构来组织和展示，便于用户进行文件操作
  5. 产品多级分类: 通过树形结构可以直观地展示和管理各级分类
  6. 评论回复: 通过树形结构可以展示帖子的回复关系，便于查看讨论的脉络

树形数据结构的应用场景通常是分层的，通过树形结构可以展示和管理各级流程节点及其关系。 这些场景中，树形结构的应用可以显著提升数据的组织和展示效率，帮助用户更直观地理解和操作系统。

树形结构在电商分类中的应用

▲：树形结构在电商分类中的应用

三、JAVA中的树形数据结构

3.1 JAVA树形结构对象定义

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

@Data
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合成树的代码原理，先直接看如何使用:

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(JsonUtils.toJson(tree));

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

  1. 第1个参数List list，为我们需要合成树的List，如上面Demo中的menuList
  2. 第2个参数Predicate rootCheck，判断为根节点的条件，如上面Demo中pId==-1就是根节点
  3. 第3个参数parentCheck 判断为父节点条件，如上面Demo中 id==pId
  4. 第4个参数setSubChildren，设置下级数据方法，如上面Demo中： Menu::setSubMenus

有了上面这4个参数，只要是合成树场景，这个TreeUtil.makeTree()都可以适用，比如我们要合成一个部门树：

@Data
public class GroupVO {private String groupId;private String parentGroupId;private String groupName;private List<GroupVO> subGroups=new ArrayList<>();
}

groupId是部门ID， 根部门的条件是parentGroupId=null, 那么调用合成树的方法为:

List<GroupVO> groupTree=TreeUtil.makeTree(groupList, x->x.getParentGroupId==null,(x, y)->x.getGroupId().equals(y.getParentGroupId), GroupVO::setSubGroups);

是不是很优雅？很通用？完全不需要实现什么接口、定义什么TreeNode、增加什么TreeConfig，静态方法直接调用就搞定。 一个字：绝！

五、神方法拆解

5.1 去掉泛型和函数接口

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

    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;}

调用方法：

       List<MenuVo> tree2 = parseTree(menuList,-1L);

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

  1. 找到所有根节点
  2. 遍历所有根节点设置子节点
  3. 遍历allDate查询子节点

5.2 使用函数优化

看懂上面的代码后，我们再给加上函数式接口：

    public static List<MenuVo> makeTree(List<MenuVo> allDate, Predicate<MenuVo> rootCheck, BiFunction<MenuVo, MenuVo, Boolean> parentCheck, BiConsumer<MenuVo, List<MenuVo>> setSubChildren) {// 1、获取所有根节点List<MenuVo> roots = allDate.stream().filter(x->rootCheck.test(x)).collect(Collectors.toList());;// 2、所有根节点设置子节点roots.stream().forEach(x->makeChildren(x,allDate,parentCheck,setSubChildren));return roots;}public static MenuVo makeChildren(MenuVo root, List<MenuVo> allDate,BiFunction<MenuVo, MenuVo, Boolean> parentCheck, BiConsumer<MenuVo, List<MenuVo>> setSubChildren) {//遍历所有数据，获取当前节点的子节点allDate.stream().filter(x->parentCheck.apply(root,x)).forEach(x->{makeChildren(x, allDate,parentCheck,setSubChildren);//将是当前节点的子节点添加到当前节点的subMenus中setSubChildren.accept(x,allDate);});return root;}

结合前面的方式再来看这个函数式接口是不是简单多了，只是写法上函数化了而已。使用函数优化的整体结构和最终的方法有点像了，最后再使用泛型优化就成了最终版本。从这个例子来看代码还是要不断优化的，大神可以直接写出神一样的代码，小弟一步步优化，一点点进步也是能写出大神一样的代码的。

六、其它操作Tree方法

6.1 遍历Tree

学习过二叉树都知道遍历二叉树有先序、中序、后序、层序，如果这些不清楚的可以先去学习一下,针对Tree的遍历这里提供了三个方法： 先序forPreOrder()，后序forPostOrder(),层序forLevelOrder()：


public static <E> void forPreOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> getSubChildren) {for (E l : tree) {consumer.accept(l);List<E> es = getSubChildren.apply(l);if (es != null && es.size() > 0) {forPreOrder(es, consumer, getSubChildren);}}
}public static <E> void forLevelOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> getSubChildren) {Queue<E> queue = new LinkedList<>(tree);while (!queue.isEmpty()) {E item = queue.poll();consumer.accept(item);List<E> childList = getSubChildren.apply(item);if (childList != null && !childList.isEmpty()) {queue.addAll(childList);}}
}public static <E> void forPostOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> getSubChildren) {for (E item : tree) {List<E> childList = getSubChildren.apply(item);if (childList != null && !childList.isEmpty()) {forPostOrder(childList, consumer, getSubChildren);}consumer.accept(item);}
}

我们看测试方法：

//先序
StringBuffer preStr=new StringBuffer();
TreeUtil.forPreOrder(tree,x-> preStr.append(x.getId().toString()),Menu::getSubMenus);
Assert.assertEquals("0137849256",preStr.toString());//层序
StringBuffer levelStr=new StringBuffer();
TreeUtil.forLevelOrder(tree,x-> levelStr.append(x.getId().toString()),Menu::getSubMenus);
Assert.assertEquals("0123456789",levelStr.toString());//后序
StringBuffer postOrder=new StringBuffer();
TreeUtil.forPostOrder(tree,x-> postOrder.append(x.getId().toString()),Menu::getSubMenus);
Assert.assertEquals("7839415620",postOrder.toString());

通过这个Demo我们解释一下遍历中的几个参数：

  1. tree 需要遍历的树，就是makeTree()合成的对象
  2. Consumer consumer 遍历后对单个元素的处理方法，如：x-> System.out.println(x)、 postOrder.append(x.getId().toString())
  3. Function<E, List> getSubChildren,获取下级数据方法，如Menu::getSubMenus

有了这三个方法遍历Tree是不是和遍历List一样简单方便了？二个字：绝了！！

6.2 flat打平树

我们可以将一个List使用markTree()构建成树，就可以使用flat()将树还原成List

    public static <E> List<E> flat(List<E> tree, Function<E, List<E>> getSubChildren, Consumer<E> setSubChildren) {List<E> res = new ArrayList<>();forPostOrder(tree, item -> {setSubChildren.accept(item);res.add(item);}, getSubChildren);return res;}

使用方法：

    List<Menu> flat = TreeUtil.flat(tree, Menu::getSubMenus,x->x.setSubMenus(null));Assert.assertEquals(flat.size(),menuList.size());flat.forEach(x->{Assert.assertTrue(x.getSubMenus()==null);});

flat()参数解释：

  1. tree 需要打平的树,就是makeTree()合成的对象
  2. Function<E, List> getSubChildren,获取下级数据方法，如Menu::getSubMenus
  3. Consumer setSubChildren,设置下级数据方法，如： x->x.setSubMenus(null)

6.3 sort()排查

我们知道针对List，可以使用list.sort()直接排序，那么针对树，就可以调用sort()方法直接对树中所有子节点直接排序：

    public static <E> List<E> sort(List<E> tree, Comparator<? super E> comparator, Function<E, List<E>> getChildren) {for (E item : tree) {List<E> childList = getChildren.apply(item);if (childList != null && !childList.isEmpty()) {sort(childList,comparator,getChildren);}}tree.sort(comparator);return tree;}

比如MenuVo有一个rank值，表明排序权重

        MenuVo menu0 = new MenuVo(0L, -1L);MenuVo menu1 = new MenuVo(1L, 0L);menu1.setRank(100);MenuVo menu2 = new MenuVo(2L, 0L);menu2.setRank(1);MenuVo menu3 = new MenuVo(3L, 1L);MenuVo menu4 = new MenuVo(4L, 1L);MenuVo menu5 = new MenuVo(5L, 2L);menu5.setRank(5);MenuVo menu6 = new MenuVo(6L, 2L);MenuVo menu7 = new MenuVo(7L, 3L);menu7.setRank(5);MenuVo menu8 = new MenuVo(8L, 3L);menu8.setRank(1);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(JsonUtils.toJson(tree));

如查我们想按rank正序：

List<MenuVo> sortTree= TreeUtil.sort(tree, Comparator.comparing(MenuVo::getRank), MenuVo::getSubMenus);

如果我们想按rank倒序：

List<MenuVo> sortTree= TreeUtil.sort(tree, (x,y)->y.getRank().compareTo(x.getRank()), MenuVo::getSubMenus);

sort参数解释：

  1. tree 需要排序的树,就是makeTree()合成的对象
  2. Comparator<? super E> comparator 排序规则Comparator，如：Comparator.comparing(MenuVo::getRank)按Rank正序 ,(x,y)->y.getRank().compareTo(x.getRank())，按Rank倒序
  3. Function<E, List> getChildren 获取下级数据方法，如：MenuVo::getSubMenus

这个给树排序是不是和对List排序一样的简单：三个字：太绝了！！！

七、总结

看完这位大神编写的TreeUtil工具类后，我深感佩服，其设计与实现真是令人叹为观止。该工具类不仅优雅且高效，使得以往需要递归处理的树形结构操作变得更加简洁和便捷。未来处理树形数据时，只需直接使用该工具类即可，无需再编写复杂的递归代码。

最后附完成代码方便CV工程师，还不赶快点赞、关注、收藏


/*** @Description: 树操作方法工具类* @Author: 公众号：赵侠客* @Copyright: Copyright (c) 赵侠客* @Date: 2024-07-22 10:42* @Version: 1.0*/
public class TreeUtil {/*** 将list合成树** @param list 需要合成树的List* @param rootCheck 判断E中为根节点的条件，如：x->x.getPId()==-1L , x->x.getParentId()==null,x->x.getParentMenuId()==0* @param parentCheck 判断E中为父节点条件，如：(x,y)->x.getId().equals(y.getPId())* @param setSubChildren   E中设置下级数据方法，如： Menu::setSubMenus* @param <E>  泛型实体对象* @return   合成好的树*/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());}/***  将树打平成tree* @param tree  需要打平的树* @param getSubChildren  设置下级数据方法，如： Menu::getSubMenus,x->x.setSubMenus(null)* @param setSubChildren 将下级数据置空方法，如： x->x.setSubMenus(null)* @return  打平后的数据* @param <E> 泛型实体对象*/public static <E> List<E> flat(List<E> tree, Function<E, List<E>> getSubChildren, Consumer<E> setSubChildren) {List<E> res = new ArrayList<>();forPostOrder(tree, item -> {setSubChildren.accept(item);res.add(item);}, getSubChildren);return res;}/*** 前序遍历** @param tree 需要遍历的树* @param consumer  遍历后对单个元素的处理方法，如：x-> System.out.println(x)、 System.out::println打印元素* @param setSubChildren  设置下级数据方法，如： Menu::getSubMenus,x->x.setSubMenus(null)* @param <E> 泛型实体对象*/public static <E> void forPreOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> setSubChildren) {for (E l : tree) {consumer.accept(l);List<E> es = setSubChildren.apply(l);if (es != null && es.size() > 0) {forPreOrder(es, consumer, setSubChildren);}}}/*** 层序遍历** @param tree 需要遍历的树* @param consumer 遍历后对单个元素的处理方法，如：x-> System.out.println(x)、 System.out::println打印元素* @param setSubChildren 设置下级数据方法，如： Menu::getSubMenus,x->x.setSubMenus(null)* @param <E> 泛型实体对象*/public static <E> void forLevelOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> setSubChildren) {Queue<E> queue = new LinkedList<>(tree);while (!queue.isEmpty()) {E item = queue.poll();consumer.accept(item);List<E> childList = setSubChildren.apply(item);if (childList != null && !childList.isEmpty()) {queue.addAll(childList);}}}/*** 后序遍历** @param tree 需要遍历的树* @param consumer 遍历后对单个元素的处理方法，如：x-> System.out.println(x)、 System.out::println打印元素* @param setSubChildren 设置下级数据方法，如： Menu::getSubMenus,x->x.setSubMenus(null)* @param <E> 泛型实体对象*/public static <E> void forPostOrder(List<E> tree, Consumer<E> consumer, Function<E, List<E>> setSubChildren) {for (E item : tree) {List<E> childList = setSubChildren.apply(item);if (childList != null && !childList.isEmpty()) {forPostOrder(childList, consumer, setSubChildren);}consumer.accept(item);}}/*** 对树所有子节点按comparator排序** @param tree 需要排序的树* @param comparator  排序规则Comparator，如：Comparator.comparing(MenuVo::getRank)按Rank正序 ,(x,y)->y.getRank().compareTo(x.getRank())，按Rank倒序* @param getChildren 获取下级数据方法，如：MenuVo::getSubMenus* @return 排序好的树* @param <E> 泛型实体对象*/public static <E> List<E> sort(List<E> tree, Comparator<? super E> comparator, Function<E, List<E>> getChildren) {for (E item : tree) {List<E> childList = getChildren.apply(item);if (childList != null && !childList.isEmpty()) {sort(childList,comparator,getChildren);}}tree.sort(comparator);return tree;}private static <E> List<E> makeChildren(E parent, List<E> allData, BiFunction<E, E, Boolean> parentCheck, BiConsumer<E, List<E>> children) {return allData.stream().filter(x -> parentCheck.apply(parent, x)).peek(x -> children.accept(x, makeChildren(x, allData, parentCheck, children))).collect(Collectors.toList());}
}

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【总结】前端JQuery获取Java后端文件流实现常规附件预览功能
  • Qt基础 | QSqlQueryModel 的使用 | QSqlQuery的使用
  • 深入理解计算机系统 CSAPP 家庭作业11.7
  • SMA 内孔 弯头——KH-SMA-K513-G
  • SQL进阶：解锁高级特性，深化数据洞察
  • MySQL零散拾遗（七）--- 突发奇想的一些疑虑
  • 力扣SQL50 上级经理已离职的公司员工 一题双解
  • Python | Leetcode Python题解之第283题移动零
  • 按图搜索新体验：阿里巴巴拍立淘API返回值详解
  • 代码实践思考：ROS1和ROS2
  • 反转链表 - 力扣（LeetCode）C语言
  • 成为git砖家(2): gitk 介绍
  • 模拟实现c++中的string
  • C# 知识点总结
  • 前端了解到框架-网络复习
  • JavaScript设计模式与开发实践系列之策略模式
  • leetcode-27. Remove Element
  • Markdown 语法简单说明
  • 从零开始在ubuntu上搭建node开发环境
  • 动手做个聊天室，前端工程师百无聊赖的人生
  • 前端性能优化——回流与重绘
  • 入门级的git使用指北
  • 正则表达式
  • Prometheus VS InfluxDB
  • 关于Kubernetes Dashboard漏洞CVE-2018-18264的修复公告
  • 树莓派用上kodexplorer也能玩成私有网盘
  • #162 (Div. 2)
  • #git 撤消对文件的更改
  • $分析了六十多年间100万字的政府工作报告，我看到了这样的变迁
  • （C语言）球球大作战
  • （react踩过的坑）Antd Select（设置了labelInValue）在FormItem中initialValue的问题
  • （react踩过的坑）antd 如何同时获取一个select 的value和 label值
  • (webRTC、RecordRTC):navigator.mediaDevices undefined
  • （苍穹外卖）day03菜品管理
  • (二)测试工具
  • （二开）Flink 修改源码拓展 SQL 语法
  • （附源码）spring boot球鞋文化交流论坛 毕业设计 141436
  • （规划）24届春招和25届暑假实习路线准备规划
  • （精确度，召回率，真阳性，假阳性）ACC、敏感性、特异性等 ROC指标
  • （论文阅读11/100）Fast R-CNN
  • .net redis定时_一场由fork引发的超时，让我们重新探讨了Redis的抖动问题
  • .netcore如何运行环境安装到Linux服务器
  • .pyc文件还原.py文件_Python什么情况下会生成pyc文件？
  • @Controller和@RestController的区别？
  • @RestController注解的使用
  • @SpringBootApplication 注解
  • [ vulhub漏洞复现篇 ] Celery ＜4.0 Redis未授权访问+Pickle反序列化利用
  • [ vulhub漏洞复现篇 ] Hadoop-yarn-RPC 未授权访问漏洞复现
  • [20190401]关于semtimedop函数调用.txt
  • [AHK V2]鼠标悬停展开窗口，鼠标离开折叠窗口
  • [BIZ] - 1.金融交易系统特点
  • [bzoj1901]: Zju2112 Dynamic Rankings
  • [C#]winform基于opencvsharp结合Diffusion-Low-Light算法实现低光图像增强黑暗图片变亮变清晰
  • [CC2642r1] ble5 stacks 蓝牙协议栈 介绍和理解
  • [HTML]Web前端开发技术7（HTML5、CSS3、JavaScript ）CSS的定位机制——喵喵画网页