java 将集合转换为树结构

菜单或着组织机构列表等转换为树结构，前提是有定位当前节点和父节点的信息（id 等）

public static <T> List<Node<T>> buildTree(Collection<Node<T>> nodes) { List<Node<T>> tree = new ArrayList<>(); for (Node<T> node : nodes) { if (node.getParent() == null || "0".equals(node.getParent())) { tree.add(node); continue; } for (Node<T> parent : nodes) { if (null != node.getParent() && StringUtils.equals(node.getParent(), parent.getValue())) { if (null == parent.getChildren()) { parent.setChildren(new ArrayList<>()); } parent.getChildren().add(node); break; } } } return tree; }

开始

节点对象

value 和 parent 用于定位当前节点和父节点，label 和 value 便于页面组件操作：

@Data @ApiModel(value = "Node", description = "节点内容") @JsonInclude(JsonInclude.Include.NON_DEFAULT) public class Node<T> { @ApiModelProperty("标签内容") private String label; @ApiModelProperty("标签取值") private String value; @JSONField(serialize = false) private String parent; @ApiModelProperty("节点全部信息") private T entity; @ApiModelProperty("子节点") private List<Node<T>> children; }

1. 递归方式

总体思路就是拿到所有顶级节点，向下递归遍历子节点：

public static <T> List<Node<T>> buildTree(Collection<Node<T>> nodes) { List<Node<T>> tree = new ArrayList<>(); // TODO 找到所有顶级节点 // TODO 递归构建子节点 return tree; } /** * 递归构建子节点，并返回当前节点以便添加到父节点 */ private static <T> Node<T> buildChildren(Node<T> current, Collection<Node<T>> nodes) { // TODO 添加子节点 // TODO 子节点递归调用 return current; }

扩充代码：

public static <T> List<Node<T>> buildTree(Collection<Node<T>> nodes) { List<Node<T>> tree = new ArrayList<>(); for (Node<T> node : nodes) { // 找到所有顶级节点 if (node.getParent() == null || "0".equals(node.getParent())) { // 添加二级节点 tree.add(buildChildren(node, nodes)); } } return tree; } /** * 递归构建子节点 * * @param current 当前节点 * @param nodes 所有节点 * @return 当前节点及子节点信息 */ private static <T> Node<T> buildChildren(Node<T> current, Collection<Node<T>> nodes) { for (Node<T> node : nodes) { if (StringUtils.equals(current.getValue(), node.getParent())) { if (null == current.getChildren()) { current.setChildren(new ArrayList<>()); } current.getChildren().add(buildChildren(node, nodes)); } } return current; }

从 buildChildren() 方法可以看出每个节点都会遍历一遍 nodes 来获取所有子节点，节点被遍历总次数 nodes.length * nodes.length

2. 嵌套循环方式

java 集合存放数据是存放数据的引用地址，因此可以为每个节点配置好子节点，保存顶级节点信息，获取树结构时即可从顶级节点顺着引用地址得到整个树结构。

public static <T> List<Node<T>> buildTree(Collection<Node<T>> nodes) { List<Node<T>> tree = new ArrayList<>(); for (Node<T> node : nodes) { // 顶级节点 if (node.getParent() == null || "0".equals(node.getParent())) { tree.add(node); } // 绑定子元素 for (Node<T> child : nodes) { if (null != child.getParent() && StringUtils.equals(child.getParent(), node.getValue())) { if (null == node.getChildren()) { node.setChildren(new ArrayList<>()); } node.getChildren().add(child); } } } return tree; }

这种方式对 nodes 做两次 for 循环, 节点被遍历总次数 nodes.length * nodes.length

嵌套循环方式优化

从节点信息中无法获知是否为末尾节点，但可知是否为顶级节点；递归方式需要从顶级节点向下获取，但 for 循环方式只需要建立父子关联即可；父查子时事先无法获知子节点数量，必须全部遍历；子查父时获取到父节点即可停止后面的循环；顶级节点无需遍历获取父节点。

针对上述可以更改为：

public static <T> List<Node<T>> buildTree(Collection<Node<T>> nodes) { List<Node<T>> tree = new ArrayList<>(); for (Node<T> node : nodes) { // 顶级节点 if (node.getParent() == null || "0".equals(node.getParent())) { tree.add(node); // 顶级节点无需遍历获取父节点, 跳过此次外层循环 continue; } // 绑定父元素 for (Node<T> parent : nodes) { if (null != node.getParent() && StringUtils.equals(node.getParent(), parent.getValue())) { if (null == parent.getChildren()) { parent.setChildren(new ArrayList<>()); } parent.getChildren().add(node); // 子查父时获取到即可停止后面的循环, 跳出内层循环 break; } } } return tree; }

节点被遍历总次数 (nodes.length - 顶级节点个数) * nodes.length - break掉的循环； 按概率来讲一般情况下内循环减少一半的遍历量，加上跳过的顶级节点，效率提高一倍以上。