场景：有一个无限层级的树结构，最场景的就是系统菜单，通过 pid 关联上级，如何将扁平化的数据列表构建成一个树结构？

有两种方式：

  1. 使用递归：这种较麻烦

  2. 不用递归：这种实现起来简单，两个单层 for 循环搞定

    不使用递归方式

    思路：

  3. 将扁平数据使用一个单层循环转换成 TreeNode 对象，并使用 map 结构存储

  4. 使用一个单层 for 循环遍历扁平的数据列表，配合 map TreeNode 直接构建树结构

下面是具体代码

  1. package crm.mrcode.tree;
  3. import com.alibaba.fastjson.JSON;
  5. import org.junit.jupiter.api.Test;
  7. import java.util.ArrayList;
  8. import java.util.List;
  9. import java.util.Map;
  10. import java.util.function.Function;
  11. import java.util.stream.Collectors;
  13. import cn.hutool.core.util.RandomUtil;
  15. /**
  16.  * @author mrcode
  17.  * @date 2021/11/26 20:48
  18.  */
  19. public class TreeDemo {
  20.     @Test
  21.     public void buildTreeTest() {
  22.         // 构建模拟菜单数据
  23.         List<DataItem> datas = buildDatas(5, 10);
  25.         // ========== 构建树逻辑
  26.         // 转成 树节点
  27.         final Map<Integer, TreeNode> maps = datas.stream().map(item -> new TreeNode(item.getId())).collect(Collectors.toMap(TreeNode::getId, Function.identity()));
  28.         // 循环构建树
  29.         List<TreeNode> root = new ArrayList<>();
  30.         for (DataItem data : datas) {
  31.             // 不是根节点，直接挂到父节点上面
  32.             if (data.getPid() != -1) {
  33.                 final TreeNode parentNode = maps.get(data.getPid());
  34.                 List<TreeNode> nodes = parentNode.getNodes();
  35.                 if (nodes == null) {
  36.                     nodes = new ArrayList<>();
  37.                     parentNode.setNodes(nodes);
  38.                 }
  39.                 nodes.add(maps.get(data.getId()));
  40.             } else {
  41.                 // 是根节点，不用处理，直接添加到 root 列表中
  42.                 root.add(maps.get(data.getId()));
  43.             }
  44.         }
  46.         System.out.println(JSON.toJSON(root));
  47.     }
  49.     /**
  50.      * 构建测试数据
  51.      *
  52.      * @param rootMax  构建的根节点数据
  53.      * @param levelMax 构建的树深度
  54.      * @return
  55.      */
  56.     private List<DataItem> buildDatas(int rootMax, int levelMax) {
  57.         List<DataItem> datas = new ArrayList<>();
  58.         for (int i = 0; i < rootMax; i++) {
  59.             datas.add(new DataItem(i, -1, i));
  60.             if (RandomUtil.randomBoolean()) {
  61.                 // 构建此节点深度
  62.                 int currentMax = RandomUtil.randomInt(0, levelMax);
  63.                 while (currentMax > 0) {
  64.                     currentMax--;
  65.                     for (int j = 0; j < currentMax; j++) {
  66.                         final DataItem parentItem = datas.get(RandomUtil.randomInt(0, datas.size()));
  67.                         datas.add(new DataItem(RandomUtil.randomInt(100, 9999999), parentItem.getId(), RandomUtil.randomInt(rootMax, rootMax * 2)));
  68.                     }
  69.                 }
  70.             }
  71.         }
  72.         // 返回数据前，按照 sort 排序后返回，这一步可以在数据库中做
  73.         datas.sort((o1, o2) -> o1.getSort() > o2.getSort() ? 1 : -1);
  74.         return datas;
  75.     }
  78.     /**
  79.      * 数据库数据
  80.      */
  81.     class DataItem {
  82.         private Integer id;
  83.         private Integer pid;
  84.         private Integer sort; // 数据顺序排序
  86.         public DataItem(Integer id, Integer pid, Integer sort) {
  87.             this.id = id;
  88.             this.pid = pid;
  89.             this.sort = sort;
  90.         }
  92.         public Integer getId() {
  93.             return id;
  94.         }
  96.         public void setId(Integer id) {
  97.             this.id = id;
  98.         }
  100.         public Integer getPid() {
  101.             return pid;
  102.         }
  104.         public void setPid(Integer pid) {
  105.             this.pid = pid;
  106.         }
  108.         public Integer getSort() {
  109.             return sort;
  110.         }
  112.         public void setSort(Integer sort) {
  113.             this.sort = sort;
  114.         }
  116.         @Override
  117.         public String toString() {
  118.             return "DataItem{" +
  119.                     "id=" + id +
  120.                     ", pid=" + pid +
  121.                     ", sort=" + sort +
  122.                     '}';
  123.         }
  124.     }
  126.     /**
  127.      * 树节点
  128.      */
  129.     class TreeNode {
  130.         private Integer id;
  131.         private List<TreeNode> nodes;
  133.         public TreeNode(Integer id) {
  134.             this.id = id;
  135.         }
  137.         public Integer getId() {
  138.             return id;
  139.         }
  141.         public void setId(Integer id) {
  142.             this.id = id;
  143.         }
  145.         public List<TreeNode> getNodes() {
  146.             return nodes;
  147.         }
  149.         public void setNodes(List<TreeNode> nodes) {
  150.             this.nodes = nodes;
  151.         }
  153.         @Override
  154.         public String toString() {
  155.             return "TreeNode{" +
  156.                     "id=" + id +
  157.                     ", nodes=" + nodes +
  158.                     '}';
  159.         }
  160.     }
  161. }

:::info 上面的代码其实就是一个简单的固定模板代码，如果你的代码功底好，完全可以使用泛型方式，对象都实现这个接口，然后你的这个构建树里面就面向接口编程就行了。主要的几个字段是：ID、父级 ID，就能完成这个功能了。 :::

使用第三方工具构建

  1. // 构建node列表
  2. List<TreeNode<String>> nodeList = CollUtil.newArrayList();
  4. nodeList.add(new TreeNode<>("1", "0", "系统管理", 5));
  5. nodeList.add(new TreeNode<>("11", "1", "用户管理", 222222));
  6. nodeList.add(new TreeNode<>("111", "11", "用户添加", 0));
  7. nodeList.add(new TreeNode<>("2", "0", "店铺管理", 1));
  8. nodeList.add(new TreeNode<>("21", "2", "商品管理", 44));
  9. nodeList.add(new TreeNode<>("221", "2", "商品管理2", 2));
  1. // 0表示最顶层的id是0
  2. List<Tree<String>> treeList = TreeUtil.build(nodeList, "0");

详细请参考 hutool 的 TreeUtil