有趣的树形结构之《爸爸去哪》
在日常的开发中树形结构是我们经常使用的数据结构，比如文件树，部门树，等级树等等。
这些树形结构如果返回给前端的话一般情况下有两种方式：
- 返回全部数据给前端，交给前端处理（前端也得进行处理）
- 后端组合成树形返回给前端
最常见的处理树形结构数据的方式：
- 递归算法：递归方式时间和空间复杂度都比较高
- 爸爸去哪算法：此算法时间复杂度为O1,大大加快了树形结构构建的速度。经典的空间换时间
场景准备
在常见的部门管理中，一个部门往往存在很多的子部门，子部门又存在子部门。子子孙无穷无尽。
如果我们将这些数据变为树形结构就很清晰的看出他们的结构关系
实体类
/**
* 部门对象
* @author xphu
* @date 2022/05/19
*/
@Builder
@Data
public class Department {
/**
* id
*/
private Integer id;
/**
* 名字
*/
private String name;
/**
* 描述
*/
private String description;
/**
* 父id
*/
private Integer parentId;
}
原始数据
[
{
"description": "技术部-负责公司的产品设计和开发",
"parentId": -1,
"name": "技术部",
"id": 1
},
{
"description": "技术部-负责公司的产品开发",
"parentId": 1,
"name": "开发部",
"id": 3
},
{
"description": "JAVA-开发部-负责公司的后端开发",
"parentId": 3,
"name": "JAVA-开发部",
"id": 5
},
{
"description": "前端-开发部-负责公司的前端开发",
"parentId": 3,
"name": "前端-开发部",
"id": 6
},
{
"description": "技术部-负责公司的产品设计",
"parentId": 1,
"name": "设计部",
"id": 4
},
{
"description": "人事部-负责公司的人员招聘和管理",
"parentId": -1,
"name": "人事部",
"id": 2
}
]
预期的结果
[
{
"description": "技术部-负责公司的产品设计和开发",
"parentId": -1,
"children": [
{
"description": "技术部-负责公司的产品开发",
"parentId": 1,
"children": [
{
"description": "JAVA-开发部-负责公司的后端开发",
"parentId": 3,
"children": [],
"name": "JAVA-开发部",
"id": 5
},
{
"description": "前端-开发部-负责公司的前端开发",
"parentId": 3,
"children": [],
"name": "前端-开发部",
"id": 6
}
],
"name": "开发部",
"id": 3
},
{
"description": "技术部-负责公司的产品设计",
"parentId": 1,
"children": [],
"name": "设计部",
"id": 4
}
],
"name": "技术部",
"id": 1
},
{
"description": "人事部-负责公司的人员招聘和管理",
"parentId": -1,
"children": [],
"name": "人事部",
"id": 2
}
]
我么定义一个接口类和两个处理数据的实现类分别使用递归和爸爸去哪算法进行处理
/**
* 部门服务
*
* @author xphu
* @date 2022/05/19
*/
public interface DepartmentService {
/**
* 得到部门
* 模拟从数据库中获取部门数据
* @return {@link List}<{@link Department}>
*/
default List<Department> getDepartment(){
ArrayList<Department> departments = new ArrayList<>();
Department technology = Department.builder()
.id(1)
.name("技术部")
.parentId(-1)
.description("技术部-负责公司的产品设计和开发")
.build();
departments.add(technology);
Department development = Department.builder()
.id(3)
.name("开发部")
.parentId(1)
.description("技术部-负责公司的产品开发")
.build();
departments.add(development);
Department java = Department.builder()
.id(5)
.name("JAVA-开发部")
.parentId(3)
.description("JAVA-开发部-负责公司的后端开发")
.build();
departments.add(java);
Department front = Department.builder()
.id(6)
.name("前端-开发部")
.parentId(3)
.description("前端-开发部-负责公司的前端开发")
.build();
departments.add(front);
Department design = Department.builder()
.id(4)
.name("设计部")
.parentId(1)
.description("技术部-负责公司的产品设计")
.build();
departments.add(design);
Department personnel = Department.builder()
.id(2)
.name("人事部")
.parentId(-1)
.description("人事部-负责公司的人员招聘和管理")
.build();
departments.add(personnel);
System.out.println("原始数据："+ JSONUtil.toJsonStr(departments));
return departments;
}
/**
* 获取树结构列表
*
* @return {@link List}<{@link Department}>
*/
List<Department> getListOfTreeStructure();
}
《递归算法》
package service.impl;
import pojo.Department;
import service.DepartmentService;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
/**
* 递归方式
*
* @author xphu
* @date 2022/05/19
*/
public class RecursionDepartmentService implements DepartmentService {
/**
* 获取树结构列表
*
* @return {@link List}<{@link Department}>
*/
@Override
public List<Department> getListOfTreeStructure() {
// 获得全部的部门
List<Department> departmentList = this.getDepartment();
// 找出顶级部门
List<Department> rootDepartmentList = departmentList.stream().filter(department -> department.getParentId().equals(-1)).collect(Collectors.toList());
// 循环找不每个顶级部门的子部门
rootDepartmentList.forEach(department -> {
department.setChildren(getChildNodes(departmentList, department));
});
return rootDepartmentList;
}
/**
* 递归获取子部门
*
* @param sourceDepartment 源部门
* @param pDepartment 上级部门
* @return {@link List}<{@link Department}>
*/
public List<Department> getChildNodes(List<Department> sourceDepartment,Department pDepartment) {
List<Department> childDepartments = new ArrayList<Department>();
for (Department n : sourceDepartment.stream().filter(department -> !department.getId().equals(pDepartment.getId())).collect(Collectors.toList())) {
if (pDepartment.getId().equals(n.getParentId())) {
// 递归获取子部门
n.setChildren(getChildNodes(sourceDepartment, n));
childDepartments.add(n);
}
}
return childDepartments;
}
}
《爸爸去哪算法》
爸爸去哪算法通过HashMap集合将所有的元素以 k=父子非关联id,v=元素本身的形式存储，只要保证遍历时子元素在前父元素在后就可以进行树形结构的构建
爸爸去哪算法的核心：
- map
- 顺序性
package service.impl;
import pojo.Department;
import service.DepartmentService;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;
/**
* 爸爸去哪算法
*
* @author xphu
* @date 2022/05/19
*/
public class DadComeOnDepartmentService implements DepartmentService {
/**
* 获取树结构列表
*
* @return {@link List}<{@link Department}>
*/
@Override
public List<Department> getListOfTreeStructure() {
// 获取源部门数据
List<Department> departments = this.getDepartment();
// list转为map
Map<Integer, Department> departmentMap = departments.stream().collect(Collectors.toMap(department -> department.getId(), department -> department));
// 可以按照主键或者创建时间倒叙，保证子部门在前，父部门在后。当然这种算法是有限制的，如果父子之间的顺序无法排序就不能使用
departments.sort(Comparator.comparing(Department::getId).reversed());
for (Department d : departments) {
// 排除根部门
if (d.getParentId().equals(-1)){
continue;
}
// 获得上级部门（找爹）
Integer parentId = d.getParentId();
Department pd = departmentMap.get(parentId);
// 没有上级部门的不处理
if (pd == null){
continue;
}
// 获得当前部门的上级部门的子部门。额有点绕口，就是获得当前部门的兄弟部门的集合，将自己放进去
List<Department> children = null;
if ((children = pd.getChildren()) == null){
children = new ArrayList<>();
}
// 将自己放入爹的子元素集合中
children.add(d);
pd.setChildren(children);
// 最后将上级部门（爹）塞回map中
departmentMap.put(parentId, pd);
}
// map转list并返回
return departmentMap
.values()
.stream()
.filter(department -> department.getParentId().equals(-1))
.collect(Collectors.toList());
}
}