前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >无限层级且乱序的树形结构数据的整理,利用HashMap降低遍历次数「建议收藏」

无限层级且乱序的树形结构数据的整理,利用HashMap降低遍历次数「建议收藏」

作者头像
全栈程序员站长
发布2022-07-07 21:12:21
3540
发布2022-07-07 21:12:21
举报

大家好,又见面了,我是全栈君。

我们在展示一个机构树的时候,经常会遇到这种一个问题,查询数据的时候,是从下往上查的,但展示数据的时候,又要从下往上展示。

这时候就要把查询到的数据进行整理从而得到我们想要的结构。

举个样例。

ID

PARENT_ID

SOME_ATTRIBUTE_ID

2001

0

6292

6120

57010

6120

6115

6121

6115

6156

6121

56874

6115

2001

这是依据需求查询出的sql数据。可是它是无序的,所以非常让人头疼,不知怎样去处理,示意图是这种。

我们先明白下数据结构吧。

每个节点我们使用一个Map存储内容,key-value映射例如以下。

key

value

ID

String

Parent_ID

String

Attribute_id

String

Children

List<Map>

children用来储存它的子节点的Map。

同一时候须要说明的是,我们的原始数据就是一个乱序的List<Map>,map中包括前三项内容。

最简单的办法就是有几层就遍历几次List。第一次遍历整个List,查找PID为0的节点,新建空的List放入Map中。这次遍历我们拿到2001这个节点,并把这个节点从List中清除。

第二次遍历,查找PID为2001的节点,这次我们查到6115这个节点。依次类推。遍历四次。我们就依照层次结构形成了须要的数据。

可是这样效率不好,有没有办法能遍历一次就完毕数据的整理工作呢?

看我把代码贴出来:

代码语言:javascript
复制
<span style="white-space:pre">		</span>List<Map> list = getList();
		Map all = new HashMap();
		for(int i = 0;i<list.size();i++){
			Map result = list.get(i);
			String parent_id = (String) result.get("PARENT_ID");
			String id = (String) result.get("ID");
			if(all.get(parent_id) == null){
				Map temp = new HashMap();
				List tempList = new ArrayList();
				if(all.get(id) != null){
					((Map)all.get(id)).putAll(result);
				}else{
					result.put("children", new ArrayList());
					all.put(id, result);
				}
				tempList.add(all.get(id));
				temp.put("children", tempList);
				all.put(parent_id, temp);				
			}else{
				if(all.get(id) == null){
					result.put("children", new ArrayList());
					all.put(id, result);
				}else{
					((Map)all.get(id)).putAll(result);
				}
				((List)((Map)all.get(parent_process)).get("children")).add(result);
			}
		}

少了遍历,就要多加入逻辑。

list是我们查询的内容,我们遍历list的时候,每拿到一条。就查看在all中。是否已经存在key为parent_id的对象,假设没有,我们再看有没有key为id的对象,假设有。它一定是作为parent_id时被建立的,所以我们把其它的内容加进去,假设没有,我们就在现有的result基础上,加入key为children的list,并把它以id为key保存在all中。同一时候。再新建一个以parent_id为key的对象,当中包括children为key的List。里边包括了key为id的对象。

假设以parent_id为key的对象在all中存在。那就简单了,仅仅须要查看all中是否有以id为key的对象,有直接将其加入至parent_id为key的对象中。没有的话。建立它,再把它放进去。

逻辑上确实比較复杂,也不是非常好理解。总之我们是在all中保存了全部以不论什么一个节点为顶节点的树,仅仅须要遍历一遍,整个all中的东西都能被整理完毕。

每次做到类似的问题的时候,都非常懊悔上大学的时候对acm嗤之以鼻。

事实上如今还是有点嗤之以鼻。。。。

我认为这根本不叫算法啊。数学模型才叫算法啊。

。。。

求醍醐灌顶!

另外本文求更优的解法。尤其是学过acm的童鞋的批评。

发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/116201.html原文链接:https://javaforall.cn

本文参与?腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2022年1月2,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客?前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与?腾讯云自媒体分享计划? ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
http://www.vxiaotou.com