Java - 常用算法-递归算法(树遍历)

in TCEHJava with 0 comment

需求:无限级菜单

说明:

  1. 仅简单实现菜单功能,因此字段为id,name,parentId,level
  2. parentId为父级id

菜单功能结构图:

菜单功能结构.jpg

菜单表数据:

menu.jpg

Java核心代码:


    /**
     * 
     * @author Back 菜单实体
     */
    class MenuEntiy {
        private int id;
        private String name;
        private int parentId;
        private int level;
        private List<MenuEntiy> childMenus;

        public int getId() {
            return id;
        }

        public void setId(int id) {
            this.id = id;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getParentId() {
            return parentId;
        }

        public void setParentId(int parentId) {
            this.parentId = parentId;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }

        public List<MenuEntiy> getChildMenus() {
            return childMenus;
        }

        public void setChildMenus(List<MenuEntiy> childMenus) {
            this.childMenus = childMenus;
        }

        @Override
        public String toString() {
            return "Menu [id=" + id + ", name=" + name + ", parentId=" + parentId + ", level=" + level + ", childMenus=" + childMenus + "]";
        }

    }
    /**
     * 获取菜单
     */
    private String getMenus() {
        String sql = "Select id,name,parentId,level From menu";
        // 查出所有菜单数据
        List<MenuEntiy> menus = getMenuDatas(sql);
        // 组装好的菜单数据
        List<MenuEntiy> returnMenus = new ArrayList<MenuEntiy>();
        for (MenuEntiy menu : menus) {
            // 先找出所有一级菜单
            if (menu.level == 1) {
                getSubMenusByRecursion(menu, menus);
                returnMenus.add(menu);
            }
        }
        return JSONObject.toJSONString(returnMenus);
    }

    /**
     * 递归查找所有或特定菜单的子菜单
     * 
     * @param parentMenu
     *            父级菜单
     * @param menus
     *            所有菜单
     */
    private void getSubMenusByRecursion(MenuEntiy parentMenu, List<MenuEntiy> menus) {
        // 子菜单
        List<MenuEntiy> childMenus = new ArrayList<MenuEntiy>();
        for (MenuEntiy menu : menus) {
            // 当父级菜单的Id,等于某项菜单的parentId时,即后者为前者的子菜单,即可加入childMenus
            if (parentMenu.getId() == menu.parentId) {
                childMenus.add(menu);
            }
        }
        // childMenus加完所有parentMenu的子菜单,即可设置到parentMenu的childMenus属性。
        parentMenu.setChildMenus(childMenus);
        // 查找子菜单下的菜单
        for (MenuEntiy childMenu : childMenus) {
            // 递归,查找下一级菜单
            getSubMenusByRecursion(childMenu, menus);
        }
    }

遍历顺序:

先广度--->再深度。即菜单1/菜单2--->菜单1-1/菜单1-2/菜单1-3--->菜单1-1-1/菜单1-1-2 ....。由此类推,遍历完菜单1的子菜单,再遍历菜单2的子菜单。

运行结果:

运行结果.jpg

Comments are closed.