原创性声明：本文完全为笔者原创，请尊重笔者劳动力。转载务必注明原文地址。
上个礼拜碰到一个树结构生成的问题。迭代的的逻辑的确相对比较绕。特地write down下来。
【业务背景】：
有一批组对象，有表对象。表在组内，组可能嵌套组，但是组与表不能同时存在于一个组下。
【数据】：
1. List<ProductGroupModel> tableList; // 表对应的List
2. List<ProductGroupModel> groupList; //组对应的List
ps:ProductGroupModel 是对象模型，table和group对象都要转化为这个模型才方便构造树结构。
树结构如下：
Paste_Image.png
要把右边的数据转化为左边图示的结构，通过nodes属性，其数据类型为List。
只是此次的树存在一个特别的需求：就是要过滤空组，即组下没有表的组将不会出现在树里，比如上面的B，就要剔除。
思路分析：如何剔除其中的空组是比较棘手的问题，也就意味着要从表开始反向迭代，查找组，这样，没有表的组就不会被查到。如果在这个过程中同时生成树结构，操作会比较复杂容易出错。因此采取的步骤是：
1.首先根据表得到表的直接父组列表List<ProductGroupModel> parentList(也就是[D,E])。
/**
* 传入表对应的tableList，返回这些表的直接上级组对应的parentList。
* @param tableModelList, 即tableList
* @param allProductGroupModel, 即groupList对应的哈希Map形式结构
*/
private List<ProductGroupModel> getParentsOfTable(List<ProductGroupModel> tableModelList,
Map<Long, ProductGroupModel> allProductGroupMap) {
List<ProductGroupModel> parentsModelOfTableList = new ArrayList<ProductGroupModel>();
Long parentId;
for (ProductGroupModel pgmTable : tableModelList) {
parentId = pgmTable.getParentId();
ProductGroupModel parentModel = allProductGroupMap.get(parentId);
if (parentModel != null) {
parentsModelOfTableList.add(parentModel);
allProductGroupMap.remove(parentId); //避免重复
}
}
return parentsModelOfTableList;
}
因此，在调用上面方法之前，还需要将groupList转化为HashMap形式，如下：
Map<Long, ProductGroupModel> allProductGroupModel = new HashMap<Long, ProductGroupModel>(); //存放所有的ProductGroupModel
//将所有的组ProductGroupModel放到Map中，后面将从中过滤出底下有table的
for (ProductGroupModel groupModel : groupList) {
allProductGroupModel.put(groupModel.getId(), groupModel);
}
再将allProductGroupModel和tableList传入1中的方法。此时getParentOfTable()就将返回parentList ([D,E])。
2.再根据parentList过滤groupList中的空组，返回非空组列表。直接上代码：
/**
* 过滤所有的空组group，将所有存在table的group挑出来并返回，摈弃所有底下没有table的group(无论是直接还是间接下面)。
* @param parentModelList 要显示的table对应的List<ProductGroupModel>
* @param resultList 返回过滤出来的List<group>
* @param resultMap 已经过滤出来的HashMap<Long, ProductGroupModel>
* @param allProductGroupModelMap 所有的group节点
* @return 返回resultList
*/
private List<ProductGroupModel> filterParentGroupModel(List<ProductGroupModel> parentModelList,
ArrayList<ProductGroupModel> resultList, HashMap<Long, ProductGroupModel> resultMap,
Map<Long, ProductGroupModel> allProductGroupModelMap) {
if (parentModelList == null || parentModelList.size() == 0) { // 当没有父节点时，就返回结果集
return resultList;
}
// 重新创建父节点集合
List<ProductGroupModel> newParentModelList = new ArrayList<ProductGroupModel>();
// 遍历parentModelList
for (ProductGroupModel pgm : parentModelList) {
Long id = pgm.getId();
Long parent_id = pgm.getParentId();
//已经过滤出来的group节点不存在，则添加
if (!resultMap.containsKey(id)) { //只处理组
newParentModelList.add(pgm); //添加到父节点
resultMap.put(id, pgm); //添加到已被过滤的map中
allProductGroupModelMap.remove(id); // 溢出总集合中的元素
resultList.add(pgm);
}
// 找出本节点的父节点并添加到newParentModelList父节点集合中，并移除集合中相应的元素
if (parent_id != null && !"".equals(parent_id)) {
ProductGroupModel parentModel = allProductGroupModelMap.get(parent_id);
if (parentModel != null) {
newParentModelList.add(parentModel);
allProductGroupModelMap.remove(parent_id);
}
}
}
//递归调用
filterParentGroupModel(newParentModelList, resultList, resultMap, allProductGroupModelMap);
return resultList;
}
一系列反向递归后，返回的resultList就是排除空组后的groupList,即hasTableGroupList。
3.最后，再由上至下，正向迭代生成树。
/**
* 传入表对应的List<ProductGroupModel>和组对应的List<ProductGroupModel>，将其转化为树结构，并返回。其中组已经经过处理，不含有空组。
* @param groupModelList 组对应的List<ProductGroupModel>
* @param tableModelList 表对应的List<ProductGroupModel>
* @return List<ProductGroupModel>树结构，其中应当只有一个根节点
*/
private List<ProductGroupModel> buildUpToTree(List<ProductGroupModel> groupModelList, List<ProductGroupModel> tableModelList, Long tableId) {
groupModelList.addAll(tableModelList); //将表和组放到一起
List<ProductGroupModel> rootNodes = new ArrayList<ProductGroupModel>(); // 存放当前allProductGroupModelList中的根节点
List<ProductGroupModel> notRootNodes = new ArrayList<ProductGroupModel>(); //存放非根节点
// 找出根节点
if (groupModelList != null && groupModelList.size() > 0) {
for (ProductGroupModel pgm : groupModelList) {
if (pgm == null) continue;
if (!pgm.getIstable() && pgm.getId() == Long.valueOf(pgm.getCpId())) { // 判断是否为根节点
rootNodes.add(pgm);
} else {
notRootNodes.add(pgm);
}
}
}
//递归获取所有子节点
if (rootNodes.size() > 0) {
for (ProductGroupModel pgm : rootNodes) { // 遍历根节点。size应该要为1
pgm.setIstable(false);
pgm.setLevel(0);
pgm.setNodes(getChildTreeData(notRootNodes, pgm.getId(), 0, tableId));
}
}
return rootNodes;
}
上面的方法是获取了根节点,是迭代的入口，迭代的函数如下：
/**
* 迭代生成树方法。传入一个List和id，从List中找到id对应组的直接下层，并迭代调用
* @param childList
* @param id
* @return
*/
private List<ProductGroupModel> getChildTreeData(List<ProductGroupModel> childList, Long id, int level, Long tableId) {
List<ProductGroupModel> parentNodes = new ArrayList<ProductGroupModel>();
List<ProductGroupModel> childNodes = new ArrayList<ProductGroupModel>();
if (childList != null && childList.size() > 0) { //找出当前的根节点和非根节点
for (ProductGroupModel pgm : childList) {
// 找出当前childList中的根节点
if (pgm.getParentId().toString().equals(id.toString())) {
parentNodes.add(pgm);
} else {
childNodes.add(pgm);
}
}
}
// 给parentNodes赋予子节点
if (parentNodes.size() > 0) {
//排序
parentNodes.sort(modelComparator);
int levelTemp = ++level;
for (ProductGroupModel pgm : parentNodes) {
List<ProductGroupModel> nodes;
pgm.setLevel(levelTemp);
// 定位table
if (pgm.getIstable()) { //如果是表
nodes = null;
} else {
nodes = getChildTreeData(childNodes, pgm.getId(), levelTemp, tableId);
pgm.setIstable(false);
}
// 递归查询子节点
pgm.setNodes(nodes);
}
}
return parentNodes;
}
调用buildUpToTree即可得到树结构。核心的方法就是filterParentGroupModel()、buildUpToTree()和getChildTreeData()
