无限树型菜单分类

2019/02/15

无限树型菜单分类

有这么样一个需求:将以下二维记录转成一个树型菜单


很明显,结果将是森林。

那么这里提供一个通用算法,来实现菜单的转换。

首先,将所有记录读入:

List<Department> departments = departmentMapper.selectAllDepartment();

其次,使用一个哈希表,将各部门id与部门实例进行映射:

Map<Integer,Department> departmentMap = new HashMap<>();

<predejavu sans="" mono="" for="" powerline="" ';font-size:9.0pt;"="">Map<Integer,DepartmentTreeDto> departmentTreeDtoMap= new HashMap<>();

for (var i : departments){
DepartmentTreeDto dto = new DepartmentTreeDto();
dto.setDepartmentName(i.getDepartmentName());
dto.setSubDepartment(new ArrayList<>());
departmentTreeDtoMap.put(i.getDepartmentId(),dto);
}</predejavu>

因为我们需要对结果进行展示,所以需要这么样的一个数据传输对象:

public class DepartmentTreeDto extends Department {

private Integer departmentId;

private String departmentName;

private Integer departmentPriority;

private String departmentRemark;

private List<DepartmentTreeDto> subDepartment;
}

最终结果都这么显示。

接下来,我们遍历departments,如果父部门不为空,那就从哈希表中找到其对应的父部门,并加入到其父部门的子部门列表中,反之如果该部门为顶级部门,那么久加入到一个存放最终结果的列表中:

List<DepartmentTreeDto> ret = new ArrayList<>();
for (var i : departments){
if (i.getParentDepartment() != null){
DepartmentTreeDto parent = departmentTreeDtoMap.get(i.getParentDepartment());
parent.getSubDepartment().add(departmentTreeDtoMap.get(i.getDepartmentId()));
}else{
ret.add(departmentTreeDtoMap.get(i.getDepartmentId()));
}
}

经过目测,结果正确:


该算法的时间复杂度为O(N);

完整代码:

List<Department> departments = departmentMapper.selectAllDepartment();

Map<Integer,DepartmentTreeDto> departmentTreeDtoMap= new HashMap<>();

for (var i : departments){
DepartmentTreeDto dto = new DepartmentTreeDto();
dto.setDepartmentName(i.getDepartmentName());
dto.setSubDepartment(new ArrayList<>());
departmentTreeDtoMap.put(i.getDepartmentId(),dto);
}


List<DepartmentTreeDto> ret = new ArrayList<>();
for (var i : departments){
if (i.getParentDepartment() != null){
DepartmentTreeDto parent = departmentTreeDtoMap.get(i.getParentDepartment());
parent.getSubDepartment().add(departmentTreeDtoMap.get(i.getDepartmentId()));
}else{
ret.add(departmentTreeDtoMap.get(i.getDepartmentId()));
}
}


Post Directory