java TreeUtil菜单递归工具类

喜欢ヅ旅行 2023-06-22 13:46 11阅读 0赞

[菜单树（详细）][Link 1]

package com.admin.manager.storeService.util;
    
    import com.admin.manager.storeService.entity.Menu;
    
    import java.util.ArrayList;
    import java.util.List;
    
    /** * @author m * @date 2019/12/16 */
    public class TreeUtil { 
    
        /** * 获取菜单树 * @param menus 所有菜单 * @return */
        public static List<Menu> menuTree(List<Menu> menus) { 
            //返回的菜单树
            List<Menu> rootMenus = new ArrayList<>();
            for (Menu menu : menus) { 
                //pid（上级Id）为0的是根菜单
                if ("0".equals(menu.getPid())) { 
                    rootMenus.add(menu);
                }
            }
            //遍历，找到二级菜单（根菜单的id和所有菜单中的pid比较）
            for (Menu rootMenu : rootMenus) { 
                List<Menu> child = getChild(String.valueOf(rootMenu.getId()), menus);
                rootMenu.setChildren(child);
            }
            return rootMenus;
        }
    
    
        /** * 递归获取下级菜单 * @param pid 上级Id * @param menus 所有菜单 * @return */
        public static List<Menu> getChild(String pid, List<Menu> menus) { 
            //子菜单列表
            List<Menu> childList = new ArrayList<>();
            for (Menu menu : menus) { 
                if (pid.equals(menu.getPid())) { 
                    childList.add(menu);
                }
            }
            //遍历 递归获取子菜单的子菜单
            for (Menu menu : childList) { 
                List<Menu> child = getChild(String.valueOf(menu.getId()), menus);
                menu.setChildren(child);
            }
            //递归出口 childList长度为0
            if (childList.size() == 0) { 
                return new ArrayList<>();
            }
            return childList;
        }
    }

上面这种递归，如果**遇到大数据量**，**效率是极低的**。比如前段时间刚实现了省市区镇四层的树结构，面对5万条的数据，竟然120s才递归完，这也太慢了，将来需求变成了省市区镇乡五层的结构，那不就挂了？

> 大眼一看，不是跟上面的一样嘛。仔细看 it.remove();

假设有五万的数据，根节点1万，二级节点1万，三级节点1万，4级节点2万。如果按照上面的逻辑走，`每次都要从5万中数据递归查找`；而下面的逻辑是`找到N级节点并且在总list中删除`。假设找到根节点的1万数据，并且把他们从总list中删除，总list剩4万条数据，依次这样，到了找4级节点时，总list就已经剩2万条数据了，总数据量从5万变成了2万，循环次数就少了，效率也就高了

import com.energy.service.vo.RegionTree;
    
    import java.util.ArrayList;
    import java.util.Iterator;
    import java.util.List;
    
    /** * @author m * @date 2020/4/2 */
    public class TreeUtil { 
        /** * 创建树结构 * @param regionTrees * @return */
        private List<RegionTree> tree(List<RegionTree> regionTrees) { 
            //返回的节点树
            List<RegionTree> rootNodes = new ArrayList<>();
            Iterator<RegionTree> it = regionTrees.iterator();
            while (it.hasNext()) { 
                RegionTree next = it.next();
                //parent（上级Id）为0的是根节点
                if ("0".equals(next.getParentId())) { 
                    rootNodes.add(next);
                    it.remove();
                }
            }
            //遍历，找到二级节点
            for (RegionTree regionTree : rootNodes) { 
                List<RegionTree> child = getChild(regionTrees, regionTree.getId().toString());
                regionTree.setChildren(child);
            }
            return rootNodes;
    
        }
    
        /** * 查子节点 * * @param regions * @param parentId * @return */
        private List<RegionTree> getChild(List<RegionTree> regions, String parentId) { 
    
            //子节点列表
            List<RegionTree> childList = new ArrayList<>();
            Iterator<RegionTree> it = regions.iterator();
            while (it.hasNext()) { 
                RegionTree regionTree = it.next();
                if (parentId.equals(regionTree.getParentId())) { 
                    childList.add(regionTree);
                    it.remove();
                }
            }
    
            //遍历 递归获取子节点的子节点
            for (RegionTree regionTree : childList) { 
                List<RegionTree> child = getChild(regions, regionTree.getId().toString());
                regionTree.setChildren(child);
            }
            //递归出口 childList长度为0
            if (childList.size() == 0) { 
                return new ArrayList<>();
            }
            return childList;
        }
    }

实体类：

@Data
    public class RegionTree extends TreeNodeVO<RegionTree> { 
    
        //地区名称
        private String regionName;
        //地区级别 1-省 2-市 3-区
        private String level;
        //经度
        private BigDecimal longitude;
        //纬度
        private BigDecimal latitude;
        //省市区合并
        private String mergeName;
        private String memo;
    
    
    }

public class TreeNodeVO<T> { 
        protected Object id;
        protected Object parentId;
    
        public List<T> getChildren() { 
            return children;
        }
    
        public void setChildren(List<T> children) { 
            this.children = children;
        }
    
        List<T> children = new ArrayList<T>();
    
        public Object getId() { 
            return id;
        }
    
        public void setId(Object id) { 
            this.id = id;
        }
    
        public Object getParentId() { 
            return parentId;
        }
    
        public void setParentId(Object parentId) { 
            this.parentId = parentId;
        }
    
        public void add(T node){ 
            children.add(node);
        }
    }

当然也可以直接用一个类解决。要注意实体类中必须要有`id、parentId`属性

[Link 1]: https://blog.csdn.net/weixin_42740530/article/details/103564528