前言

目录在日常开发中是一种非常常见的需求，今天我们来详细讨论下一种实现方案，以及查询思路。

设计思路

目录其实就是一种树形结构，子目录与父目录形成一种父子关系，所以很自然 的想到维护他们这种关系就能实现了。

数据库设计

create table tree_node
(
    id bigint not null comment '主键id'
        primary key,
    parent bigint null comment '父节点(root节点为0)'
)

• parent存储父子关系
• 这种设计很直观，也最容易理解，专业术语成为邻接表
• 唯一的缺点是在做修改、删除的时候比较麻烦，建议在确定结构后不要再修改目录结构

树节点

public class TreeNode<T> {

    /**
     * 节点ID
     */
    private Long id;

    /**
     * 节点数据
     */
    private T date;

    /**
     * 节点父节点ID
     */
    private Long parent;

    /**
     * 孩子节点
     */
    private List<TreeNode<T>> child;

    public void addChild(TreeNode<T> node) {
        if (CollectionUtils.isEmpty(this.child)) {
            this.child = new ArrayList<>();
        }
        this.child.add(node);
    }

    // Get Set ...
}

常见需求

生成树

根据节点列表生成树

• 给列表根据id建立索引
• 遍历列表，将自己加入父节点的孩子列表， 形成父子关系
• 建立一个ROOT节点作为根节点，将一级目录放在根节点下

    /**
     * 生成树
     *
     * @param nodes 所有节点
     * @return tree
     */
    public static <T> TreeNode<T> tree(List<TreeNode<T>> nodes) {
        // 建立索引
        Map<Long, TreeNode<T>> map = nodes.stream().collect(Collectors.toMap(TreeNode::getId, item -> item));
        // ROOT 节点
        TreeNode<T> root = new TreeNode<>();
        for (TreeNode<T> node : nodes) {
            if (node.getParent() == null || node.getParent() == 0) {
                root.addChild(node);
            } else {
                Long parent = node.getParent();
                map.get(parent).addChild(node);
            }
        }
        return root;
    }

获取树的某个节点

由于是目录设计，这里采用广度优先遍历，优先遍历上层目录

• 使用队列实现的广度优先遍历

    /**
     * 获取节点 采用广度优先遍历
     *
     * @param id   节点id
     * @param tree 树
     * @return result
     */
    public static <T> TreeNode<T> getNode(long id, TreeNode<T> tree) {
        Queue<TreeNode<T>> queue = new LinkedBlockingQueue<>();
        queue.add(tree);
        while (!queue.isEmpty()) {
            TreeNode<T> node = queue.poll();
            if (Objects.equals(node.getId(), id)) {
                return node;
            }
            if (!CollectionUtils.isEmpty(node.getChild())) {
                queue.addAll(node.getChild());
            }
        }
        return null;
    }

获取所有节点

有时候需要获取某个节点下面的全部节点信息，例如在做搜索的时候就有这个需求

• 这里采用深度优先遍历所有节点

    /**
     * 深度优先遍历获取所有节点
     *
     * @param tree 树
     * @param list 节点列表
     */
    public static <T> void getAllTreeNode(TreeNode<T> tree, List<TreeNode<T>> list) {
        list.add(tree);
        List<TreeNode<T>> child = tree.getChild();
        if (!CollectionUtils.isEmpty(child)) {
            for (TreeNode<T> node : child) {
                getAllTreeNode(node, list);
            }
        }
    }