java 递归实现树形结构的两种实现方式

1.情景展示

树形结构，和我们平常所触及到的无限级菜单，是同一个道理。

所谓树形结构，我们可以将其理解为：树根或者树冠，都可以无限分叉下去。

现有一张表，需要对表中数据进行分级查询（按照上下级关系进行排列），我们常用的数据库有：oracle和mysql；

如果使用oracle的话，使用connect by，很容易就能做到；

但是，mysql没有现成的递归函数，需要我们自己封装，而且，就算封装好了递归函数，mysql在执行的时候，查询速度会很慢。

如何解决这个问题呢？

既然数据库不给力，我们只能交由程序来处理了，以减轻mysql数据库的压力。

2.模拟数据

java实体类

/**
 * 菜单类
 * @description:
 * @author: Marydon
 * @date: 2022-05-17 15:47
 * @version: 1.0
 * @email: marydon20170307@163.com
 */
@Getter// 生成成员变量的get方法
@Setter// 生成成员变量的set方法
@NoArgsConstructor// 生成类的无参构造方法
public class Menu {
    // id
    public Integer id;
    // 名称
    public String name;
    // ?id ，根节点为0
    public Integer parentId;
    // ?节点信息
    public List childList;
    // 当实体类声明有参构造方法时，无参构造方法会自动消失，如果用得到，需要重新生成
    public Menu(Integer id, String name, Integer parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

模拟已从数据库查询到数据

public static void main(String[] args) {
    //模拟从数据库查询出来
    List menus = Arrays.asList(
            new Menu(1, "根节点", 0),
            new Menu(2, "一级节点1", 1),
            new Menu(3, "二级节点1.1", 2),
            new Menu(4, "二级节点1.2", 2),
            new Menu(5, "二级节点1.3", 2),
            new Menu(6, "一级节点2", 1),
            new Menu(7, "二级节点2.1", 6),
            new Menu(8, "二级节点2.2", 6),
            new Menu(9, "三级节点2.1.1", 7),
            new Menu(10, "三节点2.1.2", 7),
            new Menu(11, "一级节点3", 1),
            new Menu(12, "二级节点3.1", 11),
            new Menu(13, "三级节点3.1.1", 12),
            new Menu(14, "四级节点3.1.1.1", 13),
            new Menu(15, "五级节点3.1.1.1.1", 14)
    );
}

由于我不喜欢使用实体类，而且实体类并不具体普适性，所以，将实体类转成Map；

// 实体类转Map（自己封装的方法）
List> maps = ListUtils.toMaps(menus);
System.out.println(maps);
[{name=根节点, childList=null, id=1, parentId=0}, {name=一级节点1, childList=null, id=2, parentId=1}, {name=二级节点1.1, childList=null, id=3, parentId=2}, {name=二级节点1.2, childList=null, id=4, parentId=2}, {name=二级节点1.3, childList=null, id=5, parentId=2}, {name=一级节点2, childList=null, id=6, parentId=1}, {name=二级节点2.1, childList=null, id=7, parentId=6}, {name=二级节点2.2, childList=null, id=8, parentId=6}, {name=三级节点2.1.1, childList=null, id=9, parentId=7}, {name=三节点2.1.2, childList=null, id=10, parentId=7}, {name=一级节点3, childList=null, id=11, parentId=1}, {name=二级节点3.1, childList=null, id=12, parentId=11}, {name=三级节点3.1.1, childList=null, id=13, parentId=12}, {name=四级节点3.1.1.1, childList=null, id=14, parentId=13}, {name=五级节点3.1.1.1.1, childList=null, id=15, parentId=14}]

现在，我们该如何将这些数据库拿到的数据，逐级进行嵌套管理呢？ 

3.解决方案

通过递归实现（所谓递归，就是自己调用自己的意思）。

方式一：java8

第一步：递归函数实现；

/*
 * 递归查询子节点
 * @description:
 * @param: root 根节点（指定节点）
 * @param: all 所有节点
 * @return: java.util.List>
 * 获取指定节点下属的所有子节点
 */
private static List> getChildrens(Map root, List> all) {
    // filter()返回子节点
    // peek()往子节点当中塞它下属的节点，通过自己调自己的方式完成递归调用，直至没有下级为止
    return all.stream().filter(m -> Objects.equals(m.get("parentId"), root.get("id"))).peek(
            (m) -> m.put("childList", (getChildrens(m, all)))
    ).collect(Collectors.toList());
}

第二步：确定根节点并调用。

// filter()拿到根节点
// peek()获取根节点下属的子节点
List> collect = maps.stream().filter(m -> m.get("parentId").equals("0")).peek(
    (m) -> m.put("childList", getChildrens(m, maps))
).collect(Collectors.toList());
System.out.println(collect);
[{name=根节点, childList=[{name=一级节点1, childList=[{name=二级节点1.1, childList=[], id=3, parentId=2}, {name=二级节点1.2, childList=[], id=4, parentId=2}, {name=二级节点1.3, childList=[], id=5, parentId=2}], id=2, parentId=1}, {name=一级节点2, childList=[{name=二级节点2.1, childList=[{name=三级节点2.1.1, childList=[], id=9, parentId=7}, {name=三节点2.1.2, childList=[], id=10, parentId=7}], id=7, parentId=6}, {name=二级节点2.2, childList=[], id=8, parentId=6}], id=6, parentId=1}, {name=一级节点3, childList=[{name=二级节点3.1, childList=[{name=三级节点3.1.1, childList=[{name=四级节点3.1.1.1, childList=[{name=五级节点3.1.1.1.1, childList=[], id=15, parentId=14}], id=14, parentId=13}], id=13, parentId=12}], id=12, parentId=11}], id=11, parentId=1}], id=1, parentId=0}]

方式二：java7及以下

第一步：递归函数实现；

/*
 * 树形嵌套结构
 * @description:
 * @param: disorder 未排序的数据
 * @param: pId 父级ID
 * @param: idName id字段名
 * @param: pidName 父级id字段名
 * @return: java.util.List>
 * 排序后的树形结构
 */
public static List> treeSort(@NotNull List> disorder, Long pId, String idName, String pidName) {
    List> children = new ArrayList<>();
    // 获取直系子类
    // java8一行搞定
    // List> children = disorder.stream().filter(m -> Long.parseLong((String) m.get(pidName)) == pId).collect(Collectors.toList());
    for (Map map : disorder) {
        if (Long.parseLong((String) map.get(pidName)) == pId) {
            children.add(map);
        }
    }
    
    // 没有子节点的话，返回[]
    if(children.isEmpty()) return children;

    // 对子类进行Map排序
    // java8一行搞定冒泡排序
    // children.sort(Comparator.comparing(m -> (Long.parseLong((String) m.get(idName)))));
    boolean flag;
    // 冒泡排序（小数在前，大数在后）
    for (int i = 0; i < children.size() - 1; i++) {// 冒泡趟数，i-1趟
        flag = false;
        for (int j = 1; j < children.size() - i; j++) {
            Map temp;
            // 当小的在后面时，二者换位
            if (Long.parseLong((String) children.get(j - 1).get(idName)) > Long.parseLong((String) children.get(j).get(idName))) {
                temp = children.get(j - 1);
                children.set(j - 1, children.get(j));
                children.set(j, temp);
                flag = true;
            }
        }

        if (!flag) {// 如果没有发生交换，则退出循环
            break;
        }
    }

    //获取非子类
    // java8一行搞定
    // List> successor = disorder.stream().filter(x -> Long.parseLong((String) x.get(pidName)) != pId).collect(Collectors.toList());
    List> successor = new ArrayList<>();
    // 获取直系子类
    for (Map map : disorder) {
        if (Long.parseLong((String) map.get(pidName)) != pId) {
            successor.add(map);
        }
    }

    // 按照上下级排好序
    // 迭代直系子类
    for (Map m : children) {
        // 获取子类的子类（自己调自己）
        List> subList = treeSort(successor, Long.parseLong((String) m.get(idName)), idName, pidName);
        m.put("childList", subList);
    }

    return children;
}

第二步：确定根节点并调用。

// 根节点为0
List> mapList = treeSort(maps, 0L, "id", "parentId");
System.out.println(mapList);
[{name=根节点, childList=[{name=一级节点1, childList=[{name=二级节点1.1, childList=[], id=3, parentId=2}, {name=二级节点1.2, childList=[], id=4, parentId=2}, {name=二级节点1.3, childList=[], id=5, parentId=2}], id=2, parentId=1}, {name=一级节点2, childList=[{name=二级节点2.1, childList=[{name=三级节点2.1.1, childList=[], id=9, parentId=7}, {name=三节点2.1.2, childList=[], id=10, parentId=7}], id=7, parentId=6}, {name=二级节点2.2, childList=[], id=8, parentId=6}], id=6, parentId=1}, {name=一级节点3, childList=[{name=二级节点3.1, childList=[{name=三级节点3.1.1, childList=[{name=四级节点3.1.1.1, childList=[{name=五级节点3.1.1.1.1, childList=[], id=15, parentId=14}], id=14, parentId=13}], id=13, parentId=12}], id=12, parentId=11}], id=11, parentId=1}], id=1, parentId=0}]

4.效果展示

为了方便查看，对其进行格式化。

查看代码 
[{
		name = 根节点,
		childList = [{
				name = 一级节点1,
				childList = [{
						name = 二级节点1.1,
						childList = [],
						id = 3,
						parentId = 2
					}, {
						name = 二级节点1.2,
						childList = [],
						id = 4,
						parentId = 2
					}, {
						name = 二级节点1.3,
						childList = [],
						id = 5,
						parentId = 2
					}
				],
				id = 2,
				parentId = 1
			}, {
				name = 一级节点2,
				childList = [{
						name = 二级节点2.1,
						childList = [{
								name = 三级节点2.1.1,
								childList = [],
								id = 9,
								parentId = 7
							}, {
								name = 三节点2.1.2,
								childList = [],
								id = 10,
								parentId = 7
							}
						],
						id = 7,
						parentId = 6
					}, {
						name = 二级节点2.2,
						childList = [],
						id = 8,
						parentId = 6
					}
				],
				id = 6,
				parentId = 1
			}, {
				name = 一级节点3,
				childList = [{
						name = 二级节点3.1,
						childList = [{
								name = 三级节点3.1.1,
								childList = [{
										name = 四级节点3.1.1.1,
										childList = [{
												name = 五级节点3.1.1.1.1,
												childList = [],
												id = 15,
												parentId = 14
											}
										],
										id = 14,
										parentId = 13
									}
								],
								id = 13,
								parentId = 12
							}
						],
						id = 12,
						parentId = 11
					}
				],
				id = 11,
				parentId = 1
			}
		],
		id = 1,
		parentId = 0
	}
]

如果有必要，可以对其进行进一步处理。

// 转json
System.out.println(JSON.toJSON(collect));
[{"name":"根节点","childList":[{"name":"一级节点1","childList":[{"name":"二级节点1.1","childList":[],"id":"3","parentId":"2"},{"name":"二级节点1.2","childList":[],"id":"4","parentId":"2"},{"name":"二级节点1.3","childList":[],"id":"5","parentId":"2"}],"id":"2","parentId":"1"},{"name":"一级节点2","childList":[{"name":"二级节点2.1","childList":[{"name":"三级节点2.1.1","childList":[],"id":"9","parentId":"7"},{"name":"三节点2.1.2","childList":[],"id":"10","parentId":"7"}],"id":"7","parentId":"6"},{"name":"二级节点2.2","childList":[],"id":"8","parentId":"6"}],"id":"6","parentId":"1"},{"name":"一级节点3","childList":[{"name":"二级节点3.1","childList":[{"name":"三级节点3.1.1","childList":[{"name":"四级节点3.1.1.1","childList":[{"name":"五级节点3.1.1.1.1","childList":[],"id":"15","parentId":"14"}],"id":"14","parentId":"13"}],"id":"13","parentId":"12"}],"id":"12","parentId":"11"}],"id":"11","parentId":"1"}],"id":"1","parentId":"0"}]

格式化

查看代码 
[{
	"name": "根节点",
	"childList": [{
		"name": "一级节点1",
		"childList": [{
			"name": "二级节点1.1",
			"childList": [],
			"id": "3",
			"parentId": "2"
		},
		{
			"name": "二级节点1.2",
			"childList": [],
			"id": "4",
			"parentId": "2"
		},
		{
			"name": "二级节点1.3",
			"childList": [],
			"id": "5",
			"parentId": "2"
		}],
		"id": "2",
		"parentId": "1"
	},
	{
		"name": "一级节点2",
		"childList": [{
			"name": "二级节点2.1",
			"childList": [{
				"name": "三级节点2.1.1",
				"childList": [],
				"id": "9",
				"parentId": "7"
			},
			{
				"name": "三节点2.1.2",
				"childList": [],
				"id": "10",
				"parentId": "7"
			}],
			"id": "7",
			"parentId": "6"
		},
		{
			"name": "二级节点2.2",
			"childList": [],
			"id": "8",
			"parentId": "6"
		}],
		"id": "6",
		"parentId": "1"
	},
	{
		"name": "一级节点3",
		"childList": [{
			"name": "二级节点3.1",
			"childList": [{
				"name": "三级节点3.1.1",
				"childList": [{
					"name": "四级节点3.1.1.1",
					"childList": [{
						"name": "五级节点3.1.1.1.1",
						"childList": [],
						"id": "15",
						"parentId": "14"
					}],
					"id": "14",
					"parentId": "13"
				}],
				"id": "13",
				"parentId": "12"
			}],
			"id": "12",
			"parentId": "11"
		}],
		"id": "11",
		"parentId": "1"
	}],
	"id": "1",
	"parentId": "0"
}]

我们可以看到：树形结构已经实现。

如果前端需要的是这种嵌套数据，直接返回即可；

如果需要只是按照层级关系排好序的数据，我们还需要在此基础上，对树形结构做进一步处理，具体实现，见文末推荐。

写在最后

　　哪位大佬如若发现文章存在纰漏之处或需要补充更多内容，欢迎留言！！！

 相关推荐：

  • 个人主页
 
java

相关

JavaWeb的三大作用域

java中常用数组copy方法

6.Java方法

Java web开发：从零到 Run 一个现有的 Spring Boot 前后端分离项目（前端Vue）

javascript基础知识(29) 实现继承的方式

java 正则表达式

JAVA List<Object[]>取值问题

初次接触Java感受

99乘法表 java for循环

基于java.net.socket包的对象传递

Idea Java项目文件夹后面提示百分数怎么去掉

Java8新特性

标签