Java递归算法（树状结构）的逻辑和实例
2018-12-22 本文已影响24人
杨章隐
1、应用场景：
递归算法作为一个经常使用的算法，无论在API开发还是计算文件夹都是比较常用的，
在api开发过程中我们经常遇到需要返回树状结构的json
例如权限树和部门归属等
这个时候我们就需要编写相关的递归算法
{
"code": "200",
"data": [
{
"index": "2",
"pid": "0",
"id": "2",
"title": "课程",
"icoc": ""
},
{
"index": "dashboard",
"pid": "0",
"id": "1",
"title": "控制台",
"icoc": ""
},
{
"subs": [
{
"index": "studentList",
"pid": "4",
"id": "11",
"title": "学生列表",
"icoc": ""
},
{
"index": "studentApplyList",
"pid": "4",
"id": "12",
"title": "学生申请列表",
"icoc": ""
}
],
"index": "4",
"pid": "0",
"id": "4",
"title": "学生",
"icoc": ""
},
{
"subs": [
{
"index": "teacherApplyList",
"pid": "3",
"id": "13",
"title": "老师申请列表",
"icoc": ""
},
{
"index": "teacherList",
"pid": "3",
"id": "14",
"title": "老师列表",
"icoc": ""
}
],
"index": "3",
"pid": "0",
"id": "3",
"title": "老师",
"icoc": ""
},
{
"subs": [
{
"subs": [
{
"subs": [
{
"subs": [
{
"index": "22",
"pid": "20",
"id": "22",
"title": "增加用户一个111",
"icoc": ""
}
],
"index": "20",
"pid": "17",
"id": "20",
"title": "增加一个用户",
"icoc": ""
},
{
"index": "21",
"pid": "17",
"id": "21",
"title": "增加两个用户",
"icoc": ""
}
],
"index": "17",
"pid": "9",
"id": "17",
"title": "增加",
"icoc": ""
},
{
"index": "18",
"pid": "9",
"id": "18",
"title": "删除",
"icoc": ""
},
{
"index": "19",
"pid": "9",
"id": "19",
"title": "修改",
"icoc": ""
}
],
"index": "classList",
"pid": "5",
"id": "9",
"title": "班级列表",
"icoc": ""
},
{
"index": "finishList",
"pid": "5",
"id": "10",
"title": "完结班级",
"icoc": ""
}
],
"index": "5",
"pid": "0",
"id": "5",
"title": "班级",
"icoc": ""
},
{
"subs": [
{
"index": "collectionRecord",
"pid": "6",
"id": "7",
"title": "收款记录",
"icoc": ""
},
{
"index": "drawbackRecord",
"pid": "6",
"id": "8",
"title": "退款记录",
"icoc": ""
}
],
"index": "6",
"pid": "0",
"id": "6",
"title": "财务",
"icoc": ""
}
],
"message": "请求成功",
"success": true,
"token": null,
"encrypt": false,
"timestamp": 1545443453404
}
2、实现思路：
首先我们先找到一级集合
接下来就是循环遍历归属一级集合的子集
通过反复调用自身方法循环输出归属上级集合的下级集合
3、具体实例：
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class RightHelper{
public static void main(String[] args) {
List<Map<Object, Object>> list = new ArrayList<Map<Object, Object>>();
Map<Object, Object> map1 = new HashMap<>();
map1.put("name", "班级管理");
map1.put("pid", "0");
map1.put("id", "1");
Map<Object, Object> map2 = new HashMap<>();
map2.put("pid", "1");
map2.put("id", "2");
map2.put("name", "班级管理权限1");
Map<Object, Object> map3 = new HashMap<>();
map3.put("name", "班级管理权限2");
map3.put("pid", "1");
map3.put("id", "3");
Map<Object, Object> map4 = new HashMap<>();
map4.put("name", "班级管理权限1增加");
map4.put("pid", "2");
map4.put("id", "5");
list.add(map1);
list.add(map2);
list.add(map3);
list.add(map4);
map4 = new HashMap<>();
map4.put("name", "教师管理");
map4.put("pid", "0");
map4.put("id", "6");
list.add(map4);
System.out.println(RightHelper.test(list, 0));
}
public static List<Map<Object, Object>> test(List<Map<Object, Object>> list,int classs){
List<Map<Object, Object>> maplist1 = new ArrayList<>();
List<Map<Object, Object>> maplist2 = new ArrayList<>();
for(Map<Object, Object> map :list) {
if(map.get("pid").toString().equals(String.valueOf(classs))) {
maplist1.add(map);
}else {
maplist2.add(map);
}
}
List<Map<Object, Object>> result = new ArrayList<>();
for(Map<Object, Object> map :maplist1) {
Map<Object, Object> maps = new HashMap<>();
map.put("subs", RightHelper.test(maplist2,Integer.parseInt(map.get("id").toString())));
result.add(map);
}
return result;
}
}
优化版本
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class RightHelper{
public static void main(String[] args) {
List<Map<Object, Object>> list = new ArrayList<Map<Object, Object>>();
Map<Object, Object> map1 = new HashMap<>();
map1.put("name", "班级管理");
map1.put("pid", "0");
map1.put("id", "1");
Map<Object, Object> map2 = new HashMap<>();
map2.put("pid", "1");
map2.put("id", "2");
map2.put("name", "班级管理权限1");
Map<Object, Object> map3 = new HashMap<>();
map3.put("name", "班级管理权限2");
map3.put("pid", "1");
map3.put("id", "3");
Map<Object, Object> map4 = new HashMap<>();
map4.put("name", "班级管理权限1增加");
map4.put("pid", "2");
map4.put("id", "5");
list.add(map1);
list.add(map2);
list.add(map3);
list.add(map4);
map4 = new HashMap<>();
map4.put("name", "教师管理");
map4.put("pid", "0");
map4.put("id", "6");
list.add(map4);
System.out.println(RightHelper.test(list, 0, "pid"));
}
/**
* explain: 遍历递归优化
* <p>demand: 无
* @version: 1.0
* @author: Zing
* @date: 2018年12月01日
* @param list 遍历的集合
* @param pid 关联父集合的id(当然也按照你们公司的规定)
* @param name 关系父集合id名
* @return
*/
public static List<Map<Object, Object>> test(List<Map<Object, Object>> list,int pid,String name){
List<Map<Object, Object>> maplist1 = new ArrayList<>();
List<Map<Object, Object>> maplist2 = new ArrayList<>();
for(Map<Object, Object> map :list) {
if(map.get(name).toString().equals(String.valueOf(pid))) {
maplist1.add(map);
}else {
maplist2.add(map);
}
}
List<Map<Object, Object>> result = new ArrayList<>();
for(Map<Object, Object> map :maplist1) {
Map<Object, Object> maps = new HashMap<>();
map.put("subs", RightHelper.test(maplist2,Integer.parseInt(map.get("id").toString()),"pid"));
result.add(map);
}
return result;
}
}
