1、前言
在开发的过程中很多业务场景需要一个树形结构的结果集进行前端展示，也可以理解为是一个无限父子结构。而实现方式也是有很多种，我这里提供递归和非递归两种实现方法吧。依赖引入了lombok
2、递归构建树结构
树结构基类，有需要构建树结构的类就继承
publicclassTreeNode { /*** 节点id*/privateIntegerid; /*** 节点名称*/privateStringname; /*** 父节点id*/privateIntegerparentId; /*** 子节点*/privateList<TreeNode>childList; publicTreeNode() { } publicTreeNode(Integerid, Stringname, IntegerparentId) { this.id=id; this.name=name; this.parentId=parentId; } }
工具类：搭配注释很容易看懂
importcom.example.tree.entity.TreeNode; importorg.springframework.util.CollectionUtils; importjava.util.*; /*** @description:* @author: LoneWalker* @create: 2022-11-28**/publicclassTreeUtil { /*** 获取所有的根节点*/publicstatic<TextendsTreeNode>List<T>getRootNode(List<T>treeNodeList,Set<Integer>nodeIdSet){ List<T>rootNodeList=newArrayList<>(); for (TtreeNode : treeNodeList) { if (0==treeNode.getParentId() ||null==treeNode.getParentId()){ rootNodeList.add(treeNode); nodeIdSet.add(treeNode.getId()); } } returnrootNodeList; } /*** 构建树*/publicstatic<TextendsTreeNode>TbuildChildTree(TrootNode,List<T>treeNodeList,Set<Integer>nodeIdSet){ List<T>childNodeList=newArrayList<>(); for (TtreeNode : treeNodeList) { if (!nodeIdSet.contains(treeNode.getId()) &&treeNode.getParentId().equals(rootNode.getId())){ nodeIdSet.add(treeNode.getId()); //这里相当于把当前节点又作为父节点 递归查询子节点childNodeList.add(buildChildTree(treeNode,treeNodeList,nodeIdSet)); } } rootNode.setChildList((List<TreeNode>) childNodeList); returnrootNode; } publicstatic<TextendsTreeNode>List<T>buildTree(List<T>treeNodeList){ if (CollectionUtils.isEmpty(treeNodeList)){ returnCollections.emptyList(); } //用来保存每一棵完整的树List<T>treeNodes=newArrayList<T>(); //用来保存已装填过的树节点ID 防止重复遍历Set<Integer>nodeIdSet=newHashSet<>(); for (Troot : getRootNode(treeNodeList,nodeIdSet)) { TtreeNode=buildChildTree(root, treeNodeList,nodeIdSet); treeNodes.add(treeNode); } returntreeNodes; } }
测试
publicclassTreeController { ("/listTree") publicList<TreeNode>listTree(){ //模拟数据List<TreeNode>treeNodeList=newArrayList<>(); treeNodeList.add(newTreeNode(1,"顶级节点A",0)); treeNodeList.add(newTreeNode(2,"顶级节点B",0)); treeNodeList.add(newTreeNode(3,"二级节点A1",1)); treeNodeList.add(newTreeNode(4,"二级结点B1",2)); treeNodeList.add(newTreeNode(5,"二级节点B2",2)); treeNodeList.add(newTreeNode(6,"三级节点A1-1",3)); treeNodeList.add(newTreeNode(7,"三级节点A1-2",3)); treeNodeList.add(newTreeNode(8,"四级节点A1-1-1",6)); treeNodeList.add(newTreeNode(9,"四级节点A1-1-2",6)); treeNodeList.add(newTreeNode(10,"五级节点A1-1-1-1",8)); longstart=System.currentTimeMillis(); List<TreeNode>treeNodes=TreeUtil.buildTree(treeNodeList); System.out.println("耗时："+(System.currentTimeMillis() -start)); returntreeNodes; } }
3、非递归构建树
publicstatic<TextendsTreeNode>List<T>buildTree(List<T>treeNodeList){ List<T>rootNodeList=newArrayList<>(); //移除根数据rootNodeList=treeNodeList.stream().filter(d->d.getParentId() ==null||d.getParentId() ==0).collect(Collectors.toList()); treeNodeList.removeAll(rootNodeList); //根据父节点分组Map<Integer, List<T>>childMap=treeNodeList.stream().collect(Collectors.groupingBy(T::getParentId)); //设置子节点[这里不包括根节点]treeNodeList.forEach(treeNode->treeNode.setChildList(castList(childMap.get(treeNode.getId()),TreeNode.class))); //将上面已经构建的子树拼到对应的根节点上returnrootNodeList.stream().peek(root->root.setChildList(castList(childMap.get(root.getId()),TreeNode.class))).collect(Collectors.toList()); } /*** 这部分不是必要的，childMap.get(treeNode.getId())强转也行*/publicstatic<T>List<T>castList(Objectobj, Class<T>clazz) { List<T>result=newArrayList<T>(); if(objinstanceofList<?>) { for (Objecto : (List<?>) obj) { result.add(clazz.cast(o)); } returnresult; } returnnull; }
4、扩展
4.1递归为什么效率低
递归的实现是通过调用函数本身，函数调用的时候，每次调用时要做地址保存，参数传递等，这是通过一个递归工作栈实现的。具体是每次调用函数本身要保存的内容包括：局部变量、形参、调用函数地址、返回值。那么，如果递归调用N次，就要分配N局部变量、N形参、N调用函数地址、N返回值，这势必是影响效率的，同时，这也是内存溢出的原因，因为积累了大量的中间变量无法释放。
4.2 Stream效率问题
在少低数据量的处理场景中（size<=1000），stream 的处理效率是不如传统的 iterator 外部迭代器处理速度快的，但是实际上这些处理任务本身运行时间都低于毫秒，这点效率的差距对普通业务几乎没有影响，反而 stream 可以使得代码更加简洁。
4.3 removeIf和迭代器 remove效率对比
测试1000000份数据，删除一半数据
removeIf() 22ms
iterator.remove 39962ms
