Java实现列表转树形结构的两种方式list转tree

正常项目开发中很多地方都需要用到树形结构，如分类，用户，权限等。而在数据库中，通常是使用一个parent_id这样一个字段来记录当前数据的父节点id。那么我们直接从数据库中查出来的是个list，就需要使用代码手动将list转成tree的结构了。我这里提供2种方法实现列表到树形结构的转换。

举一个用户的例子，用户实体User结构如下：

@Data
@ToString
public class User {

    /**
     * 用户id
     */
    private Long id;

    /**
     * 用户名
     */
    private String name;

    /**
     * 父id，即上级id
     */
    private Long parentId;

    /**
     * 子节点列表，即直系下级列表
     */
    private List<User> children;

    /**
     * 构造函数
     * @param id
     * @param name
     * @param parentId
     */
    public User(Long id, String name, Long parentId) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
    }
}

接下来我们需要造一些模拟数据，这里展示下用户间的层级结构，造数据的代码就不展示了：

我们使用2种办法实现列表转树形结构，这里对树的根节点的判断是通过parentId是否为null或者0来判断，且允许有多个根节点，即多棵树。

第一种：使用2次for循环遍历list数据

public List<User> listToTree1() {
    List<User> list = list();
    List<User> tree = new ArrayList<>();
    for (User user : list) {
        //找到根节点
        if (user.getParentId() == null || user.getParentId().equals(0L)) {
            tree.add(user);
        }
        List<User> children = new ArrayList<>();
        //再次遍历list，找到user的子节点
        for (User node : list) {
            if (node.getParentId().equals(user.getId())) {
                children.add(node);
            }
        }
        user.setChildren(children);
    }
    return tree;
}

原理：通过for循环是遍历所有数据，将根节点的数据加到树列表中，接着通过第二次for循环寻找所有元素的子节点

第二种：使用递归

public List<User> listToTree2() {
    List<User> list = list();
    List<User> tree = new ArrayList<>();
    for (User user : list) {
        //找到根节点
        if (user.getParentId() == null || user.getParentId().equals(0L)) {
            tree.add(findChildren(user, list));
        }
    }
    return tree;
}

/**
    * 查找user的子节点
    * @param user
    * @param list
    * @return
    */
private User findChildren(User user, List<User> list) {
    List<User> children = new ArrayList<>();
    for (User node : list) {
        if (node.getParentId().equals(user.getId())) {
            //递归调用
            children.add(findChildren(node, list));
        }
    }
    user.setChildren(children);
    return user;
}

原理：递归使用了2个函数，第一个listToTree2函数作用仅仅只是为了找到根节点，递归的函数是findChildren，这个函数会从list中查找属于user的子节点列表并设置到user中

我这里使用web请求来获取转换的结果：

[
  {
    "id": 1,
    "name": "董事长",
    "parentId": 0,
    "children": [
      {
        "id": 2,
        "name": "赵经理",
        "parentId": 1,
        "children": [
          {
            "id": 4,
            "name": "孙组长",
            "parentId": 2,
            "children": [
              {
                "id": 7,
                "name": "小吴",
                "parentId": 4,
                "children": []
              }
            ]
          },
          {
            "id": 5,
            "name": "李组长",
            "parentId": 2,
            "children": [
              {
                "id": 8,
                "name": "小郑",
                "parentId": 5,
                "children": []
              }
            ]
          }
        ]
      },
      {
        "id": 3,
        "name": "钱经理",
        "parentId": 1,
        "children": [
          {
            "id": 6,
            "name": "周组长",
            "parentId": 3,
            "children": []
          }
        ]
      }
    ]
  }
]

完整代码参考：https://gitee.com/lqccan/blog-demo demo12