在实际开发中，经常会遇到数据转为树结构的情况。由于经常使用，所以自然而然把它封装成一个工具类，这样使用起来方便，那么如何实现呢？实现后的性能又是怎样呢？这里就引入一个概念-算法（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
