在实际开发中,我们总会遇见树性结构,比如菜单、组织机构等信息。
最近刚好有对
树形结构
操作的需求,特此记录一下通用设计。
首先的话,就是设计一个树形的通用结构,特此设计了一个接口(面向接口编程,好处你懂得)
主要就是这几个树形,
id parentId children
import java.util.List;
/**
* @Description: 树节点父类,形成树形结构等操作的节点都需要实现该接口
* @param <T> 节点id类型
* @Author: fantasy
* @Date: 2021/6/7 14:34
*/
public interface TreeNode<T> {
/**
* 获取节点id
*
* @return 树节点id
*/
T id();
/**
* 获取该节点的父节点id
*
* @return 父节点id
*/
T parentId();
/**
* 是否是根节点
*
* @return true:根节点
*/
boolean root();
/**
* 设置节点的子节点列表
*
* @param children 子节点
*/
void setChildren(List<? extends TreeNode<T>> children);
/**
* 获取所有子节点
*
* @return 子节点列表
*/
List<? extends TreeNode<T>> getChildren();
}
然后编写具体的树形节点 来实现该接口
对于root() 方法 判断是否是父节点可以有自己的逻辑
比如 parentId 是否为 null, 或者是否等于 0
import lombok.Data;
import java.util.List;
import java.util.Objects;
/**
* @Description:
* @Author: fantasy
* @Date: 2021/6/7 14:34
*/
@Data
public class Resource implements TreeNode<String> {
private String id;
private String pid;
private Integer type;
private String name;
private String icon;
private boolean selected;
private List<Resource> children;
@Override
public String id() {
return this.id;
}
@Override
public String parentId() {
return this.pid;
}
@Override
public boolean root() {
return Objects.equals(this.pid, 0L);
}
@Override
public void setChildren(List children) {
this.children = children;
}
}
然后就是就是递归构建获得树形结构的数据了
实现原理
就是:
1. 遍历一遍数据集合, 找到所有的root节点(可能存在多个)
2. 然后遍历这些root节点, 把这些节点当成父节点, 递归查询其子节点。
这里做的优化就是:
每当找到了某个节点所属的父级节点,就把该节点从数据集合中删掉,避免了后续的重复遍历
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;
/**
* 树形结构工具类
*
* @author fantasy
* @date 2021/6/7 14:34
*/
public class TreeUtils {
/**
* 根据所有树节点列表,生成含有所有树形结构的列表
*
* @param nodes 树形节点列表
* @param <T> 节点类型
* @return 树形结构列表
*/
public static <T extends TreeNode> List<T> generateTrees(List<T> nodes) {
List<T> roots = new ArrayList<>();
for (Iterator<T> ite = nodes.iterator(); ite.hasNext(); ) {
T node = ite.next();
if (node.root()) {
roots.add(node);
// 从所有节点列表中删除该节点,以免后续重复遍历该节点
ite.remove();
}
}
roots.forEach(r -> {
setChildren(r, nodes);
});
return roots;
}
/**
* 从所有节点列表中查找并设置parent的所有子节点
*
* @param parent 父节点
* @param nodes 所有树节点列表
*/
@SuppressWarnings("all")
public static <T extends TreeNode> void setChildren(T parent, List<T> nodes) {
List<T> children = new ArrayList<>();
Object parentId = parent.id();
for (Iterator<T> ite = nodes.iterator(); ite.hasNext(); ) {
T node = ite.next();
if (Objects.equals(node.parentId(), parentId)) {
children.add(node);
// 从所有节点列表中删除该节点,以免后续重复遍历该节点
ite.remove();
}
}
// 如果孩子为空,则直接返回,否则继续递归设置孩子的孩子
if (children.isEmpty()) {
return;
}
parent.setChildren(children);
children.forEach(m -> {
// 递归设置子节点
setChildren(m, nodes);
});
}
/**
* 获取指定树节点下的所有叶子节点
*
* @param parent 父节点
* @param <T> 实际节点类型
* @return 叶子节点
*/
public static <T extends TreeNode<?>> List<T> getLeafs(T parent) {
List<T> leafs = new ArrayList<>();
fillLeaf(parent, leafs);
return leafs;
}
/**
* 将parent的所有叶子节点填充至leafs列表中
*
* @param parent 父节点
* @param leafs 叶子节点列表
* @param <T> 实际节点类型
*/
@SuppressWarnings("all")
public static <T extends TreeNode> void fillLeaf(T parent, List<T> leafs) {
List<T> children = parent.getChildren();
// 如果节点没有子节点则说明为叶子节点
if (children.isEmpty()) {
leafs.add(parent);
return;
}
// 递归调用子节点,查找叶子节点
for (T child : children) {
fillLeaf(child, leafs);
}
}
}
版权声明:本文为EDG_win原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。