今天早上碰到一个树结构生成的问题。迭代的的逻辑的确相对比较绕。特地write down下来。

【业务背景】：

有一批组对象，有表对象。表在组内，组可能嵌套组，但是组与表不能同时存在于一个组下。

【数据】：

1. List<ProductGroupModel> tableList; // 表对应的List
2. List<ProductGroupModel> groupList; //组对应的List
 

树结构如下：

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()