掘金后端 ( ) • 2024-04-27 17:51

前言

最近在做一个权限管理类的项目，在做首页菜单功能时，遇到一个问题：

当点击某个菜单时，页面顶部需要显示当前菜单的面包屑信息。

研究了一下，最后使用递归+回溯算法，完成了需求。感觉这个功能还挺常见的，在这里记录一下具体的方案，希望可以帮到大家，谢谢！

需求

面包屑导航其实就是这样的

这个功能还是挺常见的，具体效果就是：当打开某个菜单时，在页面的顶部显示当前菜单的层级信息。一般是从当前菜单的根菜单开始。

例如：系统中菜单层级为：系统管理->权限管理->角色管理，那么当在点击角色管理菜单时，面包屑部分就会变成系统管理/权限管理/角色管理这样。

下面我们分步来实现：

封装树形菜单数据
封装菜单的面包屑层级数据

准备工作

表设计

菜单表设计如下：

这应该算是最简单的菜单表的设计了，同时也插入了一些测试数据（这里规范了根菜单的父菜单id为0）：

代码

项目依赖为 SpringBoot v2.6.13，引入了mybatis-plus，如下，创建了菜单相关的实体类、dao层接口、service层接口，此外，还封装了一个菜单Vo。

@Data
@TableName("t_menu")
public class MenuEntity {
    @TableId(type = IdType.AUTO)
    private Integer id;
    private String name;
    private Integer parentId;
}

@Mapper
public interface MenuMapper extends BaseMapper<MenuEntity> {
}

public interface MenuService extends IService<MenuEntity> {
    List<MenuVo> listTree();
}

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
}

菜单vo

@Data
public class MenuVo {
    /**
     * ID
     */
    private Integer id;
    /**
     * 菜单名称
     */
    private String name;
    /**
     * 子菜单集合
     */
    private List<MenuVo> subMenus;
}

代码实现

递归封装树形菜单

service层，定义了一个方法listTree，用来返回树形菜单数据

public interface MenuService extends IService<MenuEntity> {
    List<MenuVo> listTree();
}

实现类中，重写了该方法，通过递归的方式，完成了功能。

封装了一个方法getSubMenus，根据传入的parentId，获取它的子菜单的树形数据。实际就是递归调用本方法，这里就不再赘述。

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
    /**
     * 返回树形菜单数据
     *
     * @return
     */
    @Override
    public List<MenuVo> listTree() {
        List<MenuEntity> list = list();
        return getSubMenus(list, 0);
    }

    /**
     * 根据传入的菜单id 封装子菜单树形数据
     *
     * @param list
     * @param parentId
     * @return
     */
    private List<MenuVo> getSubMenus(List<MenuEntity> list, Integer parentId) {
        return list.stream()
                //筛选出当前菜单id的直接子菜单
                .filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo
                    BeanUtils.copyProperties(menu, vo);
                    //通过递归的方式，封装当前菜单的子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId()));
                    return vo;
                }).collect(Collectors.toList());
    }
}

递归+回溯封装面包屑信息

下面我们需要获取每一个菜单的面包屑信息，首先在MenuVo中新增一个属性，是一个List<String>集合，用来封装每一层菜单的名称。

@Data
public class MenuVo {
    /**
     * ID
     */
    private Integer id;
    /**
     * 菜单名称
     */
    private String name;
    /**
     * 子菜单集合
     */
    private List<MenuVo> subMenus;
    /**
     * 当前菜单层级信息：即面包屑数据
     */
    private List<String> titles;
}

对应MenuService中的方法也要进行修改：

@Service
public class MenuServiceImpl extends ServiceImpl<MenuMapper, MenuEntity> implements MenuService {
    /**
     * 返回树形菜单数据
     *
     * @return
     */
    @Override
    public List<MenuVo> listTree() {
        List<MenuEntity> list = list();
        return getSubMenus(list, 0, new ArrayList<>());
    }

    /**
     * 根据传入的菜单id 封装子菜单树形数据
     *
     * @param list
     * @param parentId
     * @return
     */
    private List<MenuVo> getSubMenus(List<MenuEntity> list, Integer parentId, List<String> titles) {
        return list.stream()
                //筛选出当前菜单id的直接子菜单
                .filter(menu -> parentId.equals(menu.getParentId()))
                .map(menu -> {
                    MenuVo vo = new MenuVo();
                    //封装vo
                    BeanUtils.copyProperties(menu, vo);
                    //封装面包屑信息
                    int size = titles.size();
                    titles.add(menu.getName());
                    vo.setTitles(new ArrayList<>(titles));
                    //通过递归的方式，封装当前菜单的子菜单
                    vo.setSubMenus(getSubMenus(list, menu.getId(), titles));
                    //进行回溯操作，将截至到本层菜单的标题信息都删除
                    //这里直接使用 titles.indexOf(title)，也是因为菜单名称一般都不会重复。如果会重复，可以采取其他处理方式
                    titles.removeIf((title) -> titles.indexOf(title) >= size);
                    return vo;
                }).collect(Collectors.toList());
    }
}

上面的代码中：

getSubMenus方法新增了一个参数List<String> titles，这个List集合的作用就是：将每一层的菜单名称封装到里面，方便它的每一个子菜单去获取。
第31行：将当前层的菜单名称，添加到titles中。
第32行：创建一个新的List集合，将titles中的数据复制到里面，然后赋值给vo里面的titles属性。（这里是因为如果直接将titles赋值到vo中，因为这是一个共享变量，所以最后会导致所有菜单的titles值都一样了。所以这里需要新建一个List集合。）
第34行：递归调用时，将共享变量titles，继续进行了传入。
第37行：这里是进行了回溯操作，下面简单介绍一下回溯操作。

回溯操作

在菜单数据的封装过程中，菜单的数据结构，其实就是一个树，比方说：如果每个菜单都只有两个子菜单，那它就是一个二叉树。

而树的深度优先搜索，就是通过递归来完成的。

而在递归过程中，当遍历到某个节点时，如果想对于接下来的两个分支，分别进行计算。那么就可以用到回溯操作。因为我们当前titles是一个共享变量，所以肯定左右两个分支需要分别计算，不可能把左右分支的数据都封装到titles里边，那就乱了。

所以代码中，当进行了左分支的计算之后，就将之前添加进titles的元素，再删除掉。再进行右分支的计算，这样左右分支的数据不会互相影响。

其实，如果不需要封装面包屑数据，根本用不到回溯，递归就可以了。

回溯算法的原理，一句两句说不清楚，大家可以去看力扣第39题，能看懂官方题解中的搜索回溯解法的话，回溯算法也能明白了。我也是做这道题，才了解了回溯算法的原理的。

总结

总的来说，还是很兴奋的。之前刷过一段时间的算法题，一直觉得对于我这种CRUD Boy 用处不大。结果今天在业务开发中应用到了回溯算法，虽然可能没有多高级，但还是很高兴，感觉自己学到了很多。

感谢各位的阅读，文章中有不对的地方，感谢各位指正，谢谢~

前言

需求

准备工作

表设计

代码

代码实现

递归封装树形菜单

递归+回溯 封装面包屑信息

回溯操作

总结

递归+回溯封装面包屑信息