java中把一个list转tree的方法

环境

我们有个需求，数据库要存一个无限级联的tree，比如菜单，目录，或者地区等数据，现有两个问题：

1. 问如何设计表。
2. 怎么返回给前端一个无线级联的json数据。

思考

第一个问题

在设计表的时候，我们保证每一条数据都有一个code，和parent表示code即可，就可以连成树tree。表设计如下：

CREATE TABLE `city_info`  (`code` varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '行政区划代码',`name` varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '名称',`type` char(1) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '类型:1-省;2-市;3-县/区',`short_name` varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '简称',`parent` varchar(20) CHARACTER SET utf8 COLLATE utf8_general_ci NOT NULL COMMENT '所属行政区划',`parents` varchar(200) CHARACTER SET utf8 COLLATE utf8_general_ci DEFAULT NULL COMMENT '所属行政区划分级'
) ENGINE = InnoDB CHARACTER SET = utf8 COLLATE = utf8_general_ci COMMENT = '中国省市区县行政区域表' ROW_FORMAT = Dynamic;

第二个问题

我的想法是通过一个sql查询查出来所有数据，得到一个 list集合，然后就回到了主题，如何用java把list转tree。

准备环境

创建一个城市信息类

/*** 中国省市区县行政区域表* @TableName tbl_city_info*/
@TableName(value ="tbl_city_info")
@Data
public class CityInfo implements Serializable {/*** 主键id*/@TableId(value = "id", type = IdType.AUTO)private Long id;/*** 行政区划代码*/@TableField(value = "code")private String code;/*** 名称*/@TableField(value = "name")private String name;/*** 类型:1-省;2-市;3-县/区*/@TableField(value = "type")private String type;/*** 简称*/@TableField(value = "short_name")private String shortName;/*** 所属行政区划*/@TableField(value = "parent")private String parent;/*** 所属行政区划分级*/@TableField(value = "parents")private String parents;/*** 所属行政区划分级* Mybatis-plus 映射字段时忽略字段*/@TableField(exist = false)private List<CityInfo> childCityInfo;@TableField(exist = false)private static final long serialVersionUID = 1L;
}

创建一个list转成tree的工具类：

public class TreeUtils{public static List<CityInfo> buildTree1(List<CityInfo> cityInfos) {// TODO : 第一种解法return null;}public static List<CityInfo> buildTree2(List<CityInfo> cityInfos) {// TODO : 第二种解法return null;}public static List<CityInfo> buildTree3(List<CityInfo> cityInfos) {// TODO : 第三种解法return null;}
}

第一种方法：递归

/*** 使用递归的方式* @param cityInfos 所有的数据* @return*/public List<CityInfo> buildTree1(List<CityInfo> cityInfos) {List<CityInfo> cityInfoList = new ArrayList<>(16);for (CityInfo cityInfo : cityInfos) {//找到根集合if (cityInfo.getParent().equals("0")) {cityInfoList.add(cityInfo);//添加子setChildren(cityInfos,cityInfo);}}return cityInfoList;}/*** 在所有集合数据中，找到所有的子结果* @param cityInfos 所以的数据* @param parent    需要找的这个城市的所有的子数据*/public void setChildren(List<CityInfo> cityInfos, CityInfo parent) {for (CityInfo cityInfo : cityInfos) {List<CityInfo> childCityInfo = parent.getChildCityInfo();//如果数据和要找的数据code和parent相等，说明找到了if (cityInfo.getParent().equals(parent.getCode())) {//如果是第一次，子结果是null，需要赋值一个空数组if (CollectionUtils.isEmpty(childCityInfo)) {childCityInfo = new ArrayList<>(16);}childCityInfo.add(cityInfo);parent.setChildCityInfo(childCityInfo);}}//如果上面遍历完了，而且子数据还是空，说明没有子数据，直接返回if (CollectionUtils.isEmpty(parent.getChildCityInfo())) {return;}//如果有子数据，需要找子数据，是否有子数据（就是找儿子的儿子）一直递归下去就行了for (CityInfo cityInfo : parent.getChildCityInfo()) {setChildren(cityInfos,cityInfo);}}

第二种方法：两层循环

 /*** 第二种方法：两层循环*      第一层遍历，是为找所有的根节点，*      第二层遍历，是为了找所有节点的，子节点*      *      这里只是返回所有的根节点，因为所有的节点的子节点都找到了，所以只要返回根节点，子节点自己就带上了* @param cityInfos 所有的数据* @return*/public List<CityInfo> buildTree2(List<CityInfo> cityInfos) {List<CityInfo> cityInfoList = new ArrayList<>(16);for (CityInfo cityInfo : cityInfos) {//找到根集合if (cityInfo.getParent().equals("0")) {cityInfoList.add(cityInfo);}//找到本次遍历的节点的，所有子节点（这里子节点就是一层）for (CityInfo child : cityInfos) {if (cityInfo.getCode().equals(child.getParent())) {List<CityInfo> childCityInfo = cityInfo.getChildCityInfo();if (CollectionUtils.isEmpty(childCityInfo)) {childCityInfo = new ArrayList<>(16);cityInfo.setChildCityInfo(childCityInfo);}childCityInfo.add(child);}}}return cityInfoList;}

第三种方法：两次遍历

/*** 第三种方法：两层循环*      第一层遍历，是为了找到所有父code下面的所有的子节点*      第二层遍历，是为了给所有的节点，设置子节点，并且找到所有根节点* @param cityInfos 所有的数据* @return*/public List<CityInfo> buildTree3(List<CityInfo> cityInfos) {Map<String, List<CityInfo>> cityInfoParentMap = new HashMap<>(16);//本次循环，是为了找到所有父code下面的所有的子节点for (CityInfo cityInfo : cityInfos) {String parent = cityInfo.getParent();List<CityInfo> children = cityInfoParentMap.getOrDefault(parent, new ArrayList<>());children.add(cityInfo);cityInfoParentMap.put(parent, children);}List<CityInfo> result = new ArrayList<>(16);//在次循环，是为了给所有的节点，设置子节点
//        for (CityInfo cityInfo : cityInfos) {
//            cityInfo.setChildCityInfo(cityInfoParentMap.get(cityInfo.getCode()));
//        }
//        //最好一次循环，是为了找到所有的根节点
//        for (CityInfo cityInfo : cityInfos) {
//            if (cityInfo.getParent().equals("0")) {
//                result.add(cityInfo);
//            }
//        }//第二次和第三次，可以合成一次循环for (CityInfo cityInfo : cityInfos) {cityInfo.setChildCityInfo(cityInfoParentMap.get(cityInfo.getCode()));if (cityInfo.getParent().equals("0")) {result.add(cityInfo);}}return result;}

第三种方法：两次遍历（使用Java8stream流）

  /*** 第三种方法：两层循环*      第一层遍历，是为了找到所有父code下面的所有的子节点*      第二层遍历，是为了给所有的节点，设置子节点，并且找到所有根节点* @param cityInfos 所有的数据* @return*/public List<CityInfo> buildTree3_stream(List<CityInfo> cityInfos) {//本次循环，是为了找到所有父code下面的所有的子节点Map<String, List<CityInfo>> cityInfoParenMap = cityInfos.stream().collect(Collectors.groupingBy(CityInfo::getParent));//本次循环，是为了给所有的节点，设置子节点cityInfos.forEach(cityInfo -> cityInfo.setChildCityInfo(cityInfoParenMap.get(cityInfo.getCode())));//是为了找到所有的根节点return cityInfos.stream().filter(cityInfo -> cityInfo.getParent().equals("0")).collect(Collectors.toList());}

注意：Collectors.groupingBy()方法使用。查看此链接：https://blog.csdn.net/qq_2662385590/article/details/132385605?spm=1001.2014.3001.5502

三种方法对比

前两种方法的时间复杂度都和叶子节点的个数相关，我们假设叶子节点个数为m

• 方法一: 用递归的方法，时间复杂度等于：O(n +（n-m）*
  n)，根据初始算法那篇文章的计算时间复杂度的方法，可以得到最终时间复杂度是O(n2)
• 方法二: 用两层嵌套循环的方法，时间复杂度等于：O(n +（n-m）* n)，和方法一的时间复杂度是一样的，最终时间复杂度是O(n2)
• 方法三:用两次遍历的方法，时间复杂度等于：O(3n)，根据初始算法那篇文章的计算时间复杂度的方法，可以得到最终时间复杂度是O(n)，但它的空间复杂度比前两种方法稍微大了一点，但是也是线性阶的，所以影响不是特别大。
• 所以第三种方法是个人觉得比较优的一种方法

方法	代码执行次数	时间复杂度	代码复杂程度
方法1	O(n +（n-m）* n)	平方阶,O(n2)	一般
方法2	O(n +（n-m）* n)	平方阶,O(n2)	良好
方法3	O(3n)	线性阶,O(n)	复杂