基于深度优先的层次排序

末蓝、 2023-06-01 06:24 28阅读 0赞

有一种数据，例如组织结构，在批量添加到系统中时，需要先从根节点开始添加，然后是第二层组织、第三层组织…而批量添加的数据有时并不是有序的，这就需要对数据做一个排序的预处理，这样的排序我把它称为按层次排序。

1.  **背景**  
    有一些组织的数据，可能是从csv等文本中导入的，也可能是从第三方系统中同步的，且数据量可能会很大，我们需要对这样的数据做层次排序后批量插入到我方的数据库中。还有一种特殊情况，就是可能数据已经同步过一次了，到第二次同步时已经不再是一个完整的组织了。
2.  **解决思路**  
    （1）原始数据中将父节点相同的放在一起  
    （2）按照深度优先的原则，从第一个父节点开始构造组织树，找以它的子节点为父节点的数据，直到将第一个父节点下所有的子孙节点都找到为止，已经遍历过的数据做删除标记，下次不再处理  
    （3）从第二个父节点开始，重复步骤（2），考虑结果是多颗子树的情况  
    （4）使用队列对结果做树的层次遍历，目的就是将结果再转换回一条一条的组织数据，而不是树，方便做批量插入。
3.  **实现**  
    （1）原始数据中将父节点相同的放在一起

/** * 将原始数据中pid相同的放在一起 * * @param originalData * @return */
        public List<OrgOriginalDto> orgDataDeal(List<OrgOriginalDto> originalData){ 
            List<OrgTreeNode> nodesList = parseNode(originalData);
            if(ObjectUtils.isEmpty(nodesList)){ 
                return null;
            }
            Map<String, MidDataDto> map = new HashMap<>(16);
            nodesList.forEach(item->{ 
                if(map.containsKey(item.getPid())){ 
                    map.get(item.getPid()).getData().add(item);
                }else{ 
                    MidDataDto midDataDto = new MidDataDto();
    
                    List<OrgTreeNode> children = new ArrayList<>();
                    children.add(item);
                    midDataDto.setData(children);
                    map.put(item.getPid(), midDataDto);
                }
            });
            buildTree(map);
    
            List<OrgOriginalDto> result = getLevelList(map);
    
            return result;
        }

（2）按深度优先构造组织树

private void buildTree(Map<String, MidDataDto> data){ 
            if(!ObjectUtils.isEmpty(data)){ 
                data.forEach((k,v)->{ 
                    if(!v.isDelete()){ 
                        findChildrenByRecursion(v, data);
                    }
                });
            }
        }
    
        private void findChildrenByRecursion(MidDataDto source, Map<String, MidDataDto> data){ 
            if(!source.isDelete() && !ObjectUtils.isEmpty(source.getData())){ 
                source.getData().forEach(item->{ 
                    String nextLevelPid = item.getId();
                    if (data.containsKey(nextLevelPid)) { 
                        MidDataDto midDataDto = data.get(nextLevelPid);
                        item.setChildren(midDataDto.getData());
                        if(!midDataDto.isDelete()){ 
                            findChildrenByRecursion(midDataDto, data);
                        }
                        midDataDto.setDelete(true);
                    }
                });
            }
        }

（3）层次遍历法再将树平铺成list

/** * 将树再平铺成list，使用树的层次遍历法 * * @param data * @return */
        private List<OrgOriginalDto> getLevelList(Map<String, MidDataDto> data){ 
            List<OrgOriginalDto> result = new ArrayList<>();
            Queue<OrgTreeNode> queue = new LinkedList<>();
            data.forEach((k,v)->{ 
                if(!v.isDelete()){ 
                    v.getData().forEach(item->{ 
                        result.add(parseOrgDto(item));
                        queue.offer(item);
                    });
                    treeTraverseByLevel(result, queue);
                }
            });
            return result;
        }
    
        private void treeTraverseByLevel(List<OrgOriginalDto> list, Queue<OrgTreeNode> queue){ 
            while(!queue.isEmpty()){ 
                OrgTreeNode orgTreeNode = queue.poll();
                if(!ObjectUtils.isEmpty(orgTreeNode.getChildren())){ 
                    orgTreeNode.getChildren().forEach(item->{ 
                        list.add(parseOrgDto(item));
                        queue.offer(item);
                    });
                }
            }
        }

最后，模拟数据测试

@Component
    public class TestInit implements CommandLineRunner { 
    
        @Autowired
        private OriginalDataHandler originalDataHandler;
    
        @Override
        public void run(String... strings) throws Exception { 
            List<OrgOriginalDto> data = new ArrayList<>();
    
            OrgOriginalDto o11 = new OrgOriginalDto();
            o11.setId("4");
            o11.setPid("2");
            o11.setOrgName("org11");
            data.add(o11);
    
            OrgOriginalDto o1 = new OrgOriginalDto();
            o1.setId("2");
            o1.setPid("1");
            o1.setOrgName("org1");
            data.add(o1);
    
            OrgOriginalDto o2 = new OrgOriginalDto();
            o2.setId("3");
            o2.setPid("1");
            o2.setOrgName("org2");
            data.add(o2);
            
            OrgOriginalDto o0 = new OrgOriginalDto();
            o0.setId("1");
            o0.setPid("-1");
            o0.setOrgName("root");
            data.add(o0);
    
            //对原始数据进行重新排序
            List<OrgOriginalDto> orgList =  originalDataHandler.orgDataDeal(data);
            soutList(orgList);
            //批量插入
        }
    
        private void soutList(List<OrgOriginalDto> list){ 
            if(!ObjectUtils.isEmpty(list)){ 
                list.forEach(item->{ 
                    System.out.println(item);
                });
            }
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNjE0MjA0Mg_size_16_color_FFFFFF_t_70]: /images/20230601/12db1f5042fe44c282c67bbaf366430d.png