树形结构是我们开发过程中经常遇到的一种数据结构
例如：权限树，菜单树，分类树……

数据表结构

其数据库设计大多如下：

create table sys_menu
(
    id   varchar(64) primary key not null,
    name varchar(64)             not null comment '菜单名称',
    pid  varchar(64)             not null default '0' comment '父id'
) comment '系统菜单表';

实体类

@Data
@Accessors(chain = true)
public class SysMenu {

    /**
     * id
     */
    private String id;

    /**
     * 菜单名称
     */
    private String name;

    /**
     * 父id
     */
    private String pid;

}

设计结构

根据数据库可以设计出如下的数据结构

• data: 数据库任意一行数据
• children：data节点下的所有数据集合

即：

/**
 * 树形结构模型类
 *
 * @author zukxu
 * @since 2022-1-2-18:09:32
 */
@Data
@NoArgsConstructor
@AllArgsConstructor
public class TreeNode<T> {

    /**
     * 节点根数据
     */
    private T rootNode;

    /**
     * 节点内容
     */
    private List<TreeNode<T>> childrenNode = new ArrayList<>();

工具类-ConvertTree

这是一个将其他的数据转换为Tree的工具类

public class ConvertTree<T> {}

获取数据

一次性从数据库中获取全部的数据，将取出的数据放入一个list中

每一个节点都应该有获取其子节点的方法
在树形节点类中添加一个方法获取其子节点内容
通过rootNode的id对比相同的放入子节点集合中，不相同的从数据集合中删除，只要集合为空即遍历结束

 /**
     * 获取子节点
     *
     * @param dataList 数据集合
     * @param idName   id字段名
     * @param pidName  pid字段名
     *
     * @return 子节点集合
     */
    public List<TreeNode<T>> childrenNode(List<T> dataList, String idName, String pidName) {
        ConvertTree<T> convertTree = new ConvertTree<>();
        String idValue = convertTree.getFieldValue(rootNode, idName);
        List<T> collect = dataList.stream()
                                  .filter(t -> idValue.equals(convertTree.getFieldValue(t, pidName))).toList();
        dataList.removeAll(collect);
        collect.forEach(t -> {
            TreeNode<T> treeNode = new TreeNode<>();
            treeNode.setRootNode(t);
            childrenNode.add(treeNode);
        });
        return childrenNode;
    }

由于无法知道具体的类，也就不知道构建Tree的id字段和pid字段，所以我们可以采用反射的方式获取字段的值

 /**
     * 根据反射获取字段值
     *
     * @param obj
     * @param fieldName
     *
     * @return
     */
    public String getFieldValue(T obj, String fieldName) {
        Class<?> cls = obj.getClass();
        //获取所有属性
        Field[] fields = cls.getFields();
        for(Field field : fields) {
            try {
                //打开私有访问，允许访问私有变量
                field.setAccessible(true);
                //获取属性
                if(field.getName().equals(fieldName)) {
                    Object res = field.get(obj);
                    if(ObjectUtil.isEmpty(res)) {
                        return null;
                    }
                    return res.toString();
                }
            } catch(IllegalAccessException e) {
                e.printStackTrace();
            }
        }
        throw new RuntimeException("获取属性值错误");
    }

找出根节点

找出数据中的根节点，也就是没有pid的值
判断数据集合是否为空，取出集合中的第一个元素，并递归往上找，知道找不到父节点为止
将这个根节点放入我们的树结构中，并且通过children获取子节点数据

/**
     * 获取根节点
     *
     * @param dataList
     * @param idName
     * @param pidName
     *
     * @return
     */
    public TreeNode<T> getRootNode(List<T> dataList, String idName, String pidName) {
        if(dataList.isEmpty()) {
            return null;
        }
        T node = dataList.get(0);
        T rootNode = getRootNode(dataList, idName, pidName, node);
        TreeNode<T> rootTreeNode = new TreeNode<>();
        dataList.remove(rootNode);
        rootTreeNode.setRootNode(rootNode);
        rootTreeNode.childrenNode(dataList, idName, pidName);
        return rootTreeNode;
    }
	/**
     * 递归遍历根节点
     *
     * @param dataList
     * @param idName
     * @param pidName
     * @param node
     *
     * @return
     */
    private T getRootNode(List<T> dataList, String idName, String pidName, T node) {
        T fNode = null;
        String fieldValue = getFieldValue(node, pidName);
        for(T data : dataList) {
            if(getFieldValue(data, idName).equals(fieldValue)) {
                fNode = data;
                break;
            }
        }
        if(ObjectUtil.isEmpty(fNode)) {
            return node;
        } else {
            return getRootNode(dataList, idName, pidName, fNode);
        }

    }

获取树形数据结构

根据获取到的root节点，构建成一颗树形数据

    /**
     * 生成树结构
     *
     * @param dataList
     * @param idName
     * @param pidName
     *
     * @return
     */
    public TreeNode<T> getTree(List<T> dataList, String idName, String pidName) {
        //获取树根
        TreeNode<T> rootNode = getRootNode(dataList, idName, pidName);
        //    遍历树节点
        List<TreeNode<T>> childrenNodeList = rootNode.getChildrenNode();
        forChildren(dataList, idName, pidName, childrenNodeList);
        //    返回树
        return rootNode;
    }
 	/**
     * 递归遍历子节点
     *
     * @param dataList
     * @param idName
     * @param pidName
     * @param childrenNodeList
     */
    private void forChildren(List<T> dataList, String idName, String pidName, List<TreeNode<T>> childrenNodeList) {
        //遍历集合
        List<TreeNode<T>> needForList = new ArrayList<>();
        for(TreeNode<T> tTreeNode : childrenNodeList) {
            List<TreeNode<T>> treeNodes = tTreeNode.childrenNode(dataList, idName, pidName);
            needForList.addAll(treeNodes);
        }
        if(!needForList.isEmpty()) {
            forChildren(dataList, idName, pidName, needForList);
        }
    }

生成森林

这种方法只会生成一个根节点的树，
但是我们在实际使用过程中的树结构会生成多个根节点的树，我们可以依次生成多棵树然后添加到list中返回
或者：

    /**
     * 形成森林数据结构
     *
     * @param dataList
     * @param idName
     * @param pidName
     *
     * @return
     */
    public List<TreeNode<T>> getForest(List<T> dataList, String idName, String pidName) {
        List<TreeNode<T>> forest = new ArrayList<>();
        while(!dataList.isEmpty()) {
            TreeNode<T> tree = getTree(dataList, idName, pidName);
            forest.add(tree);
        }
        return forest;
    }

工具类改进

我们之前的方法需要在代码中硬编码id对应的字段名和父id对应的字段名，这种硬编码的方式不适合我们的开发和后续的更新维护

注解方式

我们可以通过注解的方式获得对应的id字段名称和父id字段名称

 /**
     * 形成森林(使用注解)
     *
     * @param dataList
     */
    public List<TreeNode<T>> getForest(List<T> dataList) {
        //通过注解获取idName和pidName
        String idName = null;
        String pidName = null;
        if(!dataList.isEmpty()) {
            //得到class
            Class<?> cls = dataList.get(0).getClass();
            //得到所有属性
            Field[] fields = cls.getDeclaredFields();
            for(Field field : fields) {
                TreeId treeId = field.getAnnotation(TreeId.class);
                if(treeId != null) {
                    idName = field.getName();
                }
                TreePid treeFid = field.getAnnotation(TreePid.class);
                if(treeFid != null) {
                    pidName = field.getName();
                }
            }
        }

        return getForest(dataList, idName, pidName);
    }

注解-TreeId

/**
 * 标识TreeId
 *
 * @author zukxu
 * @since 2022/1/2 19:13:29
 */
@Retention(RetentionPolicy.RUNTIME)
@Target(FIELD)
public @interface TreeId {}

注解-Pid

/**
 * 标识Pid
 *
 * @author zukxu
 * @since 2022/1/2 19:13:53
 */
@Retention(RetentionPolicy.RUNTIME)
@Target(FIELD)
public @interface TreePid {
}

使用

测试类

@Data
@Accessors(chain = true)
public class SysMenu {

    /**
     * id
     */
    @TreeId
    private String id;

    /**
     * 菜单名称
     */
    private String name;

    /**
     * 父id
     */
    @TreePid
    private String pid;

}

测试方法

@Test
    void testTreeNode() {
        Connection conn = null;
        Statement stat = null;
        ResultSet res = null;
        try {
            Class.forName(driverClassName);
            conn = getConnection();
            String sql = "select * from sys_menu";
            stat = conn.createStatement();
            res = stat.executeQuery(sql);
            List<SysMenu> menuList = new ArrayList<>();
            while(res.next()) {
                String id = res.getString("id");
                String name = res.getString("name");
                String pid = res.getString("pid");
                menuList.add(new SysMenu().setId(id).setName(name).setPid(pid));
            }
            buildTree(menuList);
        } catch(SQLException | ClassNotFoundException e) {
            e.printStackTrace();
        } finally {
            close(res, stat, conn);
        }
    }

  private void buildTree(List<SysMenu> menuList) {
        ConvertTree<SysMenu> convertTree = new ConvertTree<>();
        //硬编码
        List<TreeNode<SysMenu>> forest = convertTree.getForest(menuList, "id", "pid");
        System.out.println(JSON.toJSONString(forest));

        //注解方式
        List<TreeNode<SysMenu>> forest1 = convertTree.getForest(menuList);
        System.out.println(JSON.toJSONString(forest1));
    }