一个好用的JAVA工具类 - 扁平数据转树结构

在实际开发中，经常会遇到数据转为树结构的情况。由于经常使用，所以自然而然把它封装成一个工具类，这样使用起来方便，那么如何实现呢？实现后的性能又是怎样呢？这里就引入一个概念-算法（Algorithm），对于同一个问题，使用不同的算法，也许最终结果是一样的，但在这个过程中消耗的资源和时间却会有很大的区别。那么如何去衡量不同算法之间的优劣呢？这里引入了时间复杂度和空间复杂度去度量一个算法的优劣，以大O符号表示法。详细可以去网上查找相关资料，这里就不多赘述。回归主题，通常，我们会用递归、嵌套循环、以及引用传递方法。接下来我将使用引用传递的方法，使得算法的时间复杂度和空间复杂度都达到O(n)，实现转树的过程。

形如

{
    "扁平结构":[
        {
            "id":1,
            "parentId":0
        },
        {
            "id":3,
            "parentId":1
        },
        {
            "id":2,
            "parentId":3
        }
    ],
    "树结构":[
        {
            "id":1,
            "parentId":0,
            "children":[
                {
                    "id":3,
                    "parentId":1,
                    "children":[
                        {
                            "id":2,
                            "parentId":3,
                            "children":[]
                        }
                    ]
                }
            ]
        }
    ]
}

1、先声明一个树节点类 TreeNode.java，存放三个属性，可以根据实际情况自由拓展，这里主要以简洁为主。

/** 编号*/
private Long id;

/**上级编号*/
private Long parentId;

/** 下级节点列表*/
private List<TreeNode> children = new ArrayList<>();

2、创建工具类 Trees.java

/**
 * 扁平数据转树结构
 *
 * @param nodes
 * @param <T>
 * @return
 */
public static <T extends TreeNode> List<T> convert(List<T> nodes) {
    if (Collections.isEmpty(nodes)) {
        return Lists.newArrayList();
    }

    List<T> nodeTree = new ArrayList<>();
    Map<Long, T> nodeMap = new HashMap<>(nodes.size());         // (1)
    Class<T> clazz = (Class<T>) nodes.get(0).getClass();        // (2)
    for (T t : nodes) {
        t.getChildren().addAll(nodeMap.containsKey(t.getId()) ? nodeMap.get(t.getId()).getChildren() : new ArrayList<>());// (3)
        nodeMap.put(t.getId(), t);  // (4)

        if (null == t.getParentId() || Constant.LONG_ZERO.equals(t.getParentId())) {    // (5)
            nodeTree.add(t);
        } else {
            if (!nodeMap.containsKey(t.getParentId())) {  // (6)
                T instance = null;
                try {
                    instance = clazz.newInstance();
                } catch (Exception e) {
                    log.error(e.getMessage(),e);
                }
                nodeMap.put(t.getParentId(), instance);
            }
            nodeMap.get(t.getParentId()).getChildren().add(t);
        }
    }
    return nodeTree;
}

解析：
（1）存放已遍历节点和其父级子树，用于子级节点的合并
（2）存放节点类型，用于创建节点实例
（3）此处只能获取到nodeMap中的子节点，因为它本身未加入，所以下一行代码不能更换顺序,此处是(5)变化的根源
（4）存放当前遍历节点
（5）顶级节点直接添加，后续节点状态的变化通过修改堆中对象，从而栈中list引用堆对象也自然跟着变化
（6）存放子级节点，不存在则通过节点类型先实例化后放入，而后将当前遍历对象直接添加至子级节点

整体：
通过单层for循环遍历每个节点，每次循环节点之前合并Map中的子节点而后存入Map容器中，当节点满足顶级节点条件时，存入返回集合，不满足（说明为非顶级节点）将其父节点入Map进行下一次循环。

使用：
只需一行代码即可完成转换：Trees.convert(list)，是不是很简单，好了这个工具类就说到这里。

一直在追求思路的传递而非代码的COPY