项目心得：广度遍历搜索部门处理业务
部门树节点
平常在做后台管理系统的时候，多多少少都会涉及部门管理，部门有上下级，所以架构会呈现出树形，下图是一个简单的部门节点图：
这个和平时的二叉树很像，如果部门比较多的话，那么这个树就会很复杂。做到web上就会这样显示：
怎么实现的我就不详细介绍了，本文主要结合实例介绍平时项目中广度遍历搜索部门树，从上级部门往下级部门开始一级一级的遍历搜索。
假设需求
有个后台管理系统用来管理每个部门，还有每个部门的主机，现在每一个部门有一个IP段（192.168.1.1-192.168.1.100），该部门的主机注册的时候能够自动匹配段，并划分到该部门下。
分析需求
考虑到IP段重复的情况，可以采用广度遍历，就是从最上级部门开始，然后二级部门，然后三级部门....，这样的话能够节省IP匹配次数。
也是说希望最后的遍历搜索顺序是:根部门，行政，测试，管理，行政1，测试1，测试2，管理1，管理12。
如下图所示：
广度优先遍历各个节点，需要使用到队列（Queue）这种数据结构，Queue的特点是先进先出，
其实也可以使用双端队列，区别就是双端队列首位都可以插入和弹出节点。整个遍历过程如下：
1.根部门进队列，处理业务，出队列，
2.行政，测试，管理进队列，处理业务，出队列
3.行政1，测试1，测试2，管理1进队列，处理业务，出队列
4，管理12进队列，处理业务，出队列
代码实现：
（注意这里使用了部分伪代码）
1. 缓存部门与下级部门
设计部门表的时候注意留一个字段是用来记录该部门的上级部门。
新建一个类，使用Map缓存部门id和下级部门id（list的形式）
public class DeptManager{
// 缓存部门id对应的所有下属部门id
Map<Integer, List<Integer>> deptMap = new HashMap<Integer, List<Integer>>();
// 缓存部门id对应的部门IP段
Map<Integer, String> deptIpRangeMap = new HashMap<Integer, String>();
/**
* 加载 从数据库中取出所有部门信息，存储成List<Map<String, Object>>形式 加载部门id和其对应的IPRange
* 注意数据库设计部门表的时候要添加上级部门ID字段
* @throws Exception
*/
public void load() throws Exception {
// 从数据中获取所有部门信息
List<Map<String, Object>> searchIdList = Db.biz.searchAsMapList(TbOrg.TABLE,
new Field[] { TbOrg.ID, TbOrg.ORG_PARENT_ID, TbOrg.IP_RANGE });
// 遍历部门，存储成部门ID对应下级部门IDList的形式
for (Map<String, Object> searchId : searchIdList) {
// 获取上级部门节点ID
int parentId = (Integer) searchId.get(TbOrg.ORG_PARENT_ID.name);
// 获取当前部门节点ID
int id = (Integer) searchId.get(TbOrg.ID.name);
if (deptMap.containsKey(parentId)) {
deptMap.get(parentId).add(id);
} else {
List<Integer> idList = new ArrayList<Integer>();
idList.add(id);
deptMap.put(parentId, idList);
}
// 缓存部门对应的IP段
deptIpRangeMap.put(id, (String) searchId.get(TbOrg.IP_RANGE.name));
}
}这样处理部门信息，接下里的部门信息就会被存储成上级部门ID对应下级部门list的一个键值对。例： {-1=[1], 2=[4], 1=[2, 3]}存储成这样的形式是为了方便接下来更好的广度遍历。
2.广度遍历部门
将部门信息存储成从上级部门往下级部门一级，二级，三级的形式
private static DeptManager deptManager = DeptManager.getInstance();
private static List<List<Integer>> getDeptBroadList(int deptId) {
List<List<Integer>> resultList = new ArrayList<List<Integer>>();
// 队列控制广度遍历
ArrayDeque<List<Integer>> queue = new ArrayDeque<List<Integer>>();
List<Integer> subDeptList = deptManager.getSubDeptIds(deptId);
queue.add(subDeptList);
while (queue.isEmpty() == false) {
subDeptList = queue.pop();
resultList.add(subDeptList);
// 获取部门节点的子节点
List<Integer> children = getChildren(subDeptList);
if (children != null && !children.isEmpty()) {
queue.add(children);
}
}
return resultList;
}
/**
* 获取同一级所有子节点
*
* @param list
* @return
*/
private static List<Integer> getChildren(List<Integer> list) {
List<Integer> result = new ArrayList<Integer>();
for (Integer deptId : list) {
if (deptManager.getSubDeptIds(deptId) != null) {
result.addAll(deptManager.getSubDeptIds(deptId));
}
}
return result;
}/**
* 广度遍历匹配IP
* 业务处理
* @param hostIp
* @param deptId
* @return
*/
private static int getDeptIdFromIp(String hostIp, int deptId) {
// flag作为判断部门IP匹配的标志
boolean flag = false;
List<List<Integer>> deptBroadList = getDeptBroadList(deptId);
for (List<Integer> list : deptBroadList) {
for (int tempDeptId : list) {
flag = matchDeptIp(hostIp, DeptManager.getInstance().getDeptIpRange(tempDeptId));
if (flag) {
return tempDeptId;
}
}
}
// 未匹配到则返回根部门ID
return deptId;
}总结：
广度搜索在平常的项目中多多少少会使用到，本文只是作者个人经验见解，不到之处请与斧正。
代码段使用了部分伪代码希望帮助读者理解，希望本文能够给予读者在工作学习中帮助和参考。
腾讯云开发者
