java TreeUtil菜单递归工具类

菜单树（详细）

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属性