广度优先算法和深度优先算法-树形结构(层级结构)-Java

程序员文章站 2022-05-22 20:28:58

...

广度优先算法和深度优先算法-树形结构(层级结构)-Java

文章目录

内容

1、前言

在日常应用中，我们经常需要封装树形结构数据，比如省市县3级数据，目录菜单按钮权限数据，分销商数据等等。虽然这些目标数据没有树形结构中的根，但是在生成的时候我们可以构建一个虚拟的*根节点，下面结合具体应用，分别使用深度优先和广度优先封装层级数据。

层级数据封装实现：

递归
栈+深度优先算法
队列+广度优先算法

下面我们以常用的权限控制系统中权限数据的封装讲解,权限控制系统相关详细内容参考我的其他博文或者自行百度。

前端效果图：
广度优先算法和深度优先算法-树形结构(层级结构)-Java

权限数据示例：

[
		{
			"id": "1346425092905299974",
			"name": "员工管理",
			"url": "/user",
			"type": 0,
			"orderNum": 1,
			"pid": "0",
			"children": [
				{
					"id": "1346425092905299975",
					"name": "列表",
					"url": "/list",
					"type": 1,
					"orderNum": 1,
					"pid": "1346425092905299974",
					"children": [
						{
							"id": "1346425092905299976",
							"name": "修改",
							"url": "",
							"type": 2,
							"orderNum": 1,
							"pid": "1346425092905299975"
						},
						{
							"id": "1346425092905299977",
							"name": "分配角色",
							"type": 2,
							"orderNum": 2,
							"pid": "1346425092905299975"
						}
					]
				}
			]
		},
		{
			"id": "1346425092905299978",
			"name": "公司设置",
			"url": "/companySetup",
			"type": 0,
			"orderNum": 2,
			"pid": "0",
			"children": [
				{
					"id": "1346425092905299979",
					"name": "列表",
					"url": "/list",
					"type": 1,
					"orderNum": 1,
					"pid": "1346425092905299978",
					"children": [
						{
							"id": "1346425092905299980",
							"name": "添加",
							"perms": "sys:companySetup:save",
							"type": 2,
							"orderNum": 1,
							"pid": "1346425092905299979"
						},
						{
							"id": "1346425092905299981",
							"name": "修改",
							"perms": "sys:companySetup:update",
							"type": 2,
							"orderNum": 2,
							"pid": "1346425092905299979"
						},
						{
							"id": "1346425092905299982",
							"name": "删除",
							"perms": "sys:companySetup:delete",
							"type": 2,
							"orderNum": 3,
							"pid": "1346425092905299979"
						},
						{
							"id": "1346425092905299983",
							"name": "分配权限",
							"perms": "sys:companySetup:assignPerms",
							"type": 2,
							"orderNum": 4,
							"pid": "1346425092905299979"
						}
					]
				}
			]
		},
		{
			"id": "1346425092905299984",
			"name": "权限设置",
			"url": "/perm",
			"type": 0,
			"orderNum": 3,
			"pid": "0"
		}
	]

具体生成代码如下：

2、递归

步骤：

查询全部权限列表
构建虚拟*根权限，id为“0”
查询子级权限，条件权限列表中权限pid为“0”的权限，同时在权限列表中移除（提高效率，做为递归结束条件)
构建子级权限列表存放步骤3 符合条件的权限
如果子级权限列表不为空，设置子级权限列表为父级权限的子权限列表children
遍历子级权限列表，重复步骤3-6
直到权限列表为空，结束递归

代码如下：

   public List<PermissionEntity> queryLevelPermsRecursive(Map<String, Object> params) {
  		Integer type = null;
  		if (params.containsKey("type")){
  			type = (Integer) params.get("type");
  		}
  		List<PermissionEntity> list = new LambdaQueryChainWrapper<>(permissionDao)
  				.le(type != null, PermissionEntity::getType, type)
  				.list();
  		if(CollectionUtils.isEmpty(list)) {
  			return null;
  		}
  		PermissionEntity permissionEntity = new PermissionEntity();
  		permissionEntity.setPid("f");
  		permissionEntity.setId("0");
  		levelPermsRecursive(permissionEntity, list);
  		return permissionEntity.getChildren();
  	}
  	private void levelPermsRecursive(PermissionEntity vo, List<PermissionEntity> districtEntityVoList) {
  		// 1、如果是指定层级或者集合为空结束递归调用
  		if ( districtEntityVoList == null || districtEntityVoList.size() == 0) {
  			return;
  		}
  		// 2、遍历查找集合中pid和目标id相同的元素
  		List<PermissionEntity> children = new LinkedList<>();
  		Iterator<PermissionEntity> iterator = districtEntityVoList.iterator();
  		while (iterator.hasNext()) {
  			PermissionEntity next = iterator.next();
  			if (StringUtils.equals(vo.getId(), next.getPid())) {
  				// 2.1、找到元素，加入子集合；同时删除在原有集合中移除
  				children.add(next);
  				iterator.remove();
  			}
  		}
  		if (children.size() > 0) {
  			// 3、子集合不为空，递归封装层级数据
  			vo.setChildren(children);
  			for (PermissionEntity child: children) {
  				levelPermsRecursive(child, districtEntityVoList);
  			}
  		}
  	}

注意事项：
- 递归一定要有结束条件，这里找到符合条件的权限对象，原权限列表中移除，最后权限列表会为空
- 想要权限列表最终为空，权限表设计一定要合理，除顶层权限pid为某个指定值(这里设置"0")外，其他权限pid一定是表中个权限的id,既权限一定要有父级权限

3、栈+深度优先算法

步骤

查询全部权限列表
构建虚拟*根权限，id为“0”
构建栈结构，这里使用Java中LinkedList的类型，把根权限放入栈
取出队列中最上面的元素（弹栈)
查询子级权限，条件权限列表中权限pid为“0”的权限，同时在权限列表中移除（提高效率，做为结束条件)
构建子级权限列表存放步骤3 符合条件的权限
如果子级权限列表不为空，设置子级权限列表为父级权限的子权限列表children
同时吧步骤7中自己权限列表压入栈中(压栈)
重复步骤4-8，直到队列为空或者权限列表为空

代码实现：

 public List<PermissionEntity> levelPermsStack(Map<String, Object> params) {
 //        long start = System.currentTimeMillis();
 		Integer type = null;
 		if (params.containsKey("type")){
 			type = (Integer) params.get("type");
 		}
 		List<PermissionEntity> list = new LambdaQueryChainWrapper<>(permissionDao)
 				.le(type != null, PermissionEntity::getType, type)
 				.list();
 		if(CollectionUtils.isEmpty(list)) {
 			return null;
 		}
 		PermissionEntity permissionEntity = new PermissionEntity();
 		permissionEntity.setPid("f");
 		permissionEntity.setId("0");
 		LinkedList<PermissionEntity> stack = new LinkedList<>();
 		stack.addLast(permissionEntity);

 		while (!stack.isEmpty() && list.size() > 0) {
 			PermissionEntity m = stack.pop();
 			List<PermissionEntity> children = new LinkedList<>();
 			Iterator<PermissionEntity> iterator = list.iterator();
 			while (iterator.hasNext()) {
 				PermissionEntity next = iterator.next();
 				if (StringUtils.equals(m.getId(), next.getPid())) {
 					// 2.1、找到元素，加入子集合；同时删除在原有集合中移除
 //                    next.setParent(m);
 					children.add(next);
 					iterator.remove();
 				}
 			}
 			if (children.size() > 0) {
 				m.setChildren(children);
 				stack.addAll(children);
 			}
 		}
 //        long end = System.currentTimeMillis();
 //        System.out.println(end - start);
 		return permissionEntity.getChildren();
 	}

知识点：
- LinedList 有pop取最上面的元素，addAll或者push 吧最新的元素压入栈（压栈)，符合先入后出（FILO)或者后入先出,可以作为栈使用
- 深度优先既先获取子级，在获取子子级，以此类推，优先深度（纵向)

4、队列+广度优先算法

步骤

查询全部权限列表
构建虚拟*根权限，id为“0”
构建队列，这里使用Java中LinkedList的类型，把根权限放入队列
取出队列中最前面的元素
查询子级权限，条件权限列表中权限pid为“0”的权限，同时在权限列表中移除（提高效率，做为递归结束条件)
构建子级权限列表存放步骤3 符合条件的权限
如果子级权限列表不为空，设置子级权限列表为父级权限的子权限列表children
同时吧步骤7中自己权限列表放入队列中
重复步骤4-8，直到队列为空或者权限列表为空

代码实现：

 public List<PermissionEntity> levelPermsQueue(Map<String, Object> params) {
 //        long start = System.currentTimeMillis();
 		Integer type = null;
 		if (params.containsKey("type")){
 			type = (Integer) params.get("type");
 		}
 		List<PermissionEntity> list = new LambdaQueryChainWrapper<>(permissionDao)
 				.le(type != null, PermissionEntity::getType, type)
 				.list();
 		if(CollectionUtils.isEmpty(list)) {
 			return null;
 		}
 		PermissionEntity pe = new PermissionEntity();
 		pe.setPid("f");
 		pe.setId("0");
 		LinkedList<PermissionEntity> queue = new LinkedList<>();
 		queue.addLast(pe);


 		while (CollectionUtils.isNotEmpty(queue) && CollectionUtils.isNotEmpty(list)) {

 			PermissionEntity p = queue.removeFirst();

 			Iterator<PermissionEntity> iterator = list.iterator();
 			LinkedList<PermissionEntity> children = new LinkedList<>();
 			while (iterator.hasNext()) {
 				PermissionEntity next = iterator.next();
 				if (StringUtils.equals(p.getId(), next.getPid())){
 					children.add(next);
 					iterator.remove();

 				}
 			}
 			if (children.size() > 0) {
 				p.setChildren(children);
 				queue.addAll(children);
 			}
 		}
 //        long end = System.currentTimeMillis();
 //        System.out.println(end - start);
 		return pe.getChildren();
 	}

知识点：
- LinedList 有removeFirst取最前面的元素，addLast 吧最新的元素放入末尾，符合先入先出（FIFO),可以作为队列使用
- 广度优先既先获取所有的子级，在获取所有的子子级，以此类推,优先广度（横向)

5、比较

递归：适合数据量少且层级不深
深度优先和广度优先看具体需求，具有相同的时间复杂度。

关于递归、树形结构、广度优先算法、深度优先算法更详细的知识，兴趣的小伙伴自行查阅相关文档。

后记：

欢迎交流，本人QQ:806797785

后端JAVA源代码地址:https://gitee.com/gaogzhen/ihrm-parent    // 后端项目
前端项目源代码地址：https://gitee.com/gaogzhen/ihrm-vue    // 前端后台管理系统

相关标签：数据结构和算法树形结构广度优先深度优先

上一篇： Maven项目转换为Gradle项目

下一篇：请求转发和重定向的区别

广度优先算法和深度优先算法-树形结构(层级结构)-Java

广度优先算法和深度优先算法-树形结构(层级结构)-Java

目录

文章目录

内容

1、前言

2、递归

3、栈+深度优先算法

4、队列+广度优先算法

5、比较

后记：

python数据结构之图深度优先和广度优先实例详解

Python数据结构与算法之图的广度优先与深度优先搜索算法示例

数据结构与算法_深度优先寻路

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

用JAVA语言实现的凝聚式层次聚类算法 ——基于数据结构中的线性结构和树形结构

数据结构与算法-----BFS与DFS（广度优先搜索与深度优先搜索）

数据结构与算法_深度优先搜索（DFS）与广度优先搜索（BFS）详解

Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现

Java数据结构与算法——深度优先搜索与广度优先搜索

数据结构与算法——广度和深度优先搜索

广度优先算法和深度优先算法-树形结构(层级结构)-Java

广度优先算法和深度优先算法-树形结构(层级结构)-Java

目录

文章目录

内容

1、前言

2、递归

3、栈+深度优先算法

4、队列+广度优先算法

5、比较

后记 ：

python数据结构之图深度优先和广度优先实例详解

Python数据结构与算法之图的广度优先与深度优先搜索算法示例

数据结构与算法_深度优先寻路

可能是目前为止最为详细的深度优先搜索DFS和广度优先搜索BFS算法分析

用JAVA语言实现的凝聚式层次聚类算法 ——基于数据结构中的线性结构和树形结构

数据结构与算法-----BFS与DFS（广度优先搜索与深度优先搜索）

数据结构与算法_深度优先搜索（DFS）与广度优先搜索（BFS）详解

Java数据结构与算法：图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现

Java数据结构与算法——深度优先搜索与广度优先搜索

数据结构与算法——广度和深度优先搜索

后记：