目錄設計以及樹的周遊

前言

目錄在日常開發中是一種非常常見的需求，今天我們來詳細讨論下一種實作方案，以及查詢思路。

設計思路

目錄其實就是一種樹形結構，子目錄與父目錄形成一種父子關系，是以很自然 的想到維護他們這種關系就能實作了。

資料庫設計

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);
            }
        }
    }