目录设计以及树的遍历-阿里云开发者社区

开发者社区> 阿里云GTS能力中心-浩鲸新智能> 正文
登录阅读全文

目录设计以及树的遍历

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

前言

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

设计思路

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

数据库设计

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

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:

阿里云GTS能力中心(浩鲸新智能),从交付的视角探讨数字化转型过程中大型软件开发实践、以及阿里云产品在各行业被集成的案例分享、技术沉淀等内容。敬请关注!

官方博客
官网链接