Java list 数据类型组成 tree

本贴最后更新于 1912 天前,其中的信息可能已经时移世改

Java list 数据类型组成 tree

项目中企业组织架构类数据通常需要返回给前端树形结构的数据

目前项目中的企业机构层级关系有 sys_tenant_org 表中的 org_num 字段确定。每个企业在创建时都会创建一个同名的根机构,org_num 分配为 00,之后再创建的子机构或部门,org_num 都会是以 00 开头。例:

根机构(00)

  • 子机构(0001)
    • 子机构(000101)
    • 子部门(000102)
      • 子部门(00010201)
  • 子部门(0002)
    • 子部门(000201)

目前设计同一上级下的同级机构/部门最多 99 个(如果是两位十进制数字,最大就是 99,如需扩展,可以选用更高的进制)

通过一个 org_num 字段,可以找到一个机构/部门的上级,算出机构/部门深度。

所以我们现在以 org_num 字段为基础,设计对象使得可以将查询出的平级数据构造成树形数据对象。业务数据可以自己定义对象并继承 OrgNodeDTO.

@Getter @Setter @Accessors(chain = true) public class OrgNodeDTO implements Serializable { private String orgNum; //机构编码 private List<? super OrgNodeDTO> children; //子机构 public OrgNodeDTO(String orgNum) { this.orgNum = orgNum; this.children = new ArrayList<>(); } }

list 转 tree 的 utils

/** * 节点转换为树形结构 * 依据对象中orgNum字段分级 * * @param parent 需要返回的父节点,通常为根节点,也可以是层级中某一层的节点 * @param treeNodes 要转换的子节点,会将属于parent下的子节点组装到parent下 * @return 返回一个包含了下属节点的节点 */ public static <T extends OrgNodeDTO> T findChildren(T parent, List<T> treeNodes) { for (T child : treeNodes) { if (parent.getOrgNum().equals(child.getOrgNum().substring(0, child.getOrgNum().length() - 2))) { if (parent.getChildren() == null) { parent.setChildren(new ArrayList<>()); } parent.getChildren().add(findChildren(child, treeNodes)); } } return parent; }

此处的转换方法用了递归,还有一种双层 for 循环的方法

public static List<TreeNode> toTree01(List<TreeNode> treeNodes) { List<TreeNode> retList = new ArrayList<>(); for (TreeNode parent : treeNodes) { if ("0".equals(parent.getParentId())) { retList.add(parent); } for (TreeNode child : treeNodes) { if (child.getParentId().equals(parent.getId())) { if (parent.getChildren() == null) { parent.setChildren(new ArrayList<>()); } parent.getChildren().add(child); } } } return retList; }

关于两种方法的效率,虽然说递归会在重复调用函数时会增加耗时和对内存的占用,但考虑到这个功能要处理的元素个数通常不会太多,这里做了 10000 个元素做测试;

测试中发现节点数相同时,最终结果的层级对耗时也是有影响的,可以看到,在数据总量不变的前提下,leaf(叶子)越多则最终层级越少,大概在四层或五层时两种方法的执行效率达到最高。而且两种方法跑起来占用的系统内存基本都在 60-80MB 之间波动(这里直接看的系统任务管理器,直接看的当前运行的程序,这里面也包含了构造数据那部分代码占用的内存,实际只处理数据也用不了这么多内存),最终项目中选用了递归的方法;

(ps 本来想做满树来测试,但是满树会因为层级的变化导致元素总数不断增加,这样变量又增多了,所以最终采用了固定元素个数的测试)

测试代码:https://github.com/mnizht/JDKTest/blob/master/src/cn/zhuht/jdk8test/util/List2Tree.java

结果对比:
折线图堆叠.png

特别感谢同事 zsp 的技术支持:https://gitee.com/fantasyzsp/AuthorityService.git

  • Java

    Java 是一种可以撰写跨平台应用软件的面向对象的程序设计语言,是由 Sun Microsystems 公司于 1995 年 5 月推出的。Java 技术具有卓越的通用性、高效性、平台移植性和安全性。

    3192 引用 • 8214 回帖 • 2 关注
  • Tree
    35 引用 • 6 回帖
  • recursion
    1 引用 • 1 回帖

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...
  • someone

    你的文章总是写的很详细。赞个~

推荐标签 标签

  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 1 关注
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖 • 5 关注
  • 运维

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    150 引用 • 257 回帖 • 3 关注
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖 • 1 关注
  • 安全

    安全永远都不是一个小问题。

    204 引用 • 816 回帖
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 75 关注
  • MyBatis

    MyBatis 本是 Apache 软件基金会 的一个开源项目 iBatis,2010 年这个项目由 Apache 软件基金会迁移到了 google code,并且改名为 MyBatis ,2013 年 11 月再次迁移到了 GitHub。

    170 引用 • 414 回帖 • 379 关注
  • 小说

    小说是以刻画人物形象为中心,通过完整的故事情节和环境描写来反映社会生活的文学体裁。

    30 引用 • 108 回帖
  • Outlook
    1 引用 • 5 回帖 • 3 关注
  • 书籍

    宋真宗赵恒曾经说过:“书中自有黄金屋,书中自有颜如玉。”

    76 引用 • 389 回帖
  • 工具

    子曰:“工欲善其事,必先利其器。”

    294 引用 • 739 回帖 • 1 关注
  • 智能合约

    智能合约(Smart contract)是一种旨在以信息化方式传播、验证或执行合同的计算机协议。智能合约允许在没有第三方的情况下进行可信交易,这些交易可追踪且不可逆转。智能合约概念于 1994 年由 Nick Szabo 首次提出。

    1 引用 • 11 回帖 • 1 关注
  • 正则表达式

    正则表达式(Regular Expression)使用单个字符串来描述、匹配一系列遵循某个句法规则的字符串。

    31 引用 • 94 回帖 • 3 关注
  • 反馈

    Communication channel for makers and users.

    124 引用 • 928 回帖 • 263 关注
  • sts
    2 引用 • 2 回帖 • 207 关注
  • 设计模式

    设计模式(Design pattern)代表了最佳的实践,通常被有经验的面向对象的软件开发人员所采用。设计模式是软件开发人员在软件开发过程中面临的一般问题的解决方案。这些解决方案是众多软件开发人员经过相当长的一段时间的试验和错误总结出来的。

    200 引用 • 120 回帖
  • 导航

    各种网址链接、内容导航。

    43 引用 • 177 回帖
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 564 关注
  • OAuth

    OAuth 协议为用户资源的授权提供了一个安全的、开放而又简易的标准。与以往的授权方式不同之处是 oAuth 的授权不会使第三方触及到用户的帐号信息(如用户名与密码),即第三方无需使用用户的用户名与密码就可以申请获得该用户资源的授权,因此 oAuth 是安全的。oAuth 是 Open Authorization 的简写。

    36 引用 • 103 回帖 • 23 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    224 引用 • 475 回帖
  • Excel
    31 引用 • 28 回帖
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 54 回帖 • 23 关注
  • MongoDB

    MongoDB(来自于英文单词“Humongous”,中文含义为“庞大”)是一个基于分布式文件存储的数据库,由 C++ 语言编写。旨在为应用提供可扩展的高性能数据存储解决方案。MongoDB 是一个介于关系数据库和非关系数据库之间的产品,是非关系数据库当中功能最丰富,最像关系数据库的。它支持的数据结构非常松散,是类似 JSON 的 BSON 格式,因此可以存储比较复杂的数据类型。

    90 引用 • 59 回帖 • 1 关注
  • SMTP

    SMTP(Simple Mail Transfer Protocol)即简单邮件传输协议,它是一组用于由源地址到目的地址传送邮件的规则,由它来控制信件的中转方式。SMTP 协议属于 TCP/IP 协议簇,它帮助每台计算机在发送或中转信件时找到下一个目的地。

    4 引用 • 18 回帖 • 635 关注
  • SOHO

    为成为自由职业者在家办公而努力吧!

    7 引用 • 55 回帖 • 1 关注
  • 创业

    你比 99% 的人都优秀么?

    82 引用 • 1395 回帖
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    75 引用 • 258 回帖 • 637 关注