递归思想解决树形菜单问题

其实树形菜单的问题我们其实很常见，平常权限管理中的菜单就是最好应用，及时记录下来，后面碰到类似的问题也能及时更好地解决！
在程序中，所谓的递归，就是函数自己直接或间接的调用自己。调用自己分两种：

• 直接调用自己
• 间接调用自己

就递归而言最重要的就是跳出结构，因为跳出了才可以有结果.所有要有一个条件判断！
比如：本例中就是判断当前菜单的下一级菜单集合为空

所以我们的树形菜单看做一个类似树形的集合，拆分出来就是分析一棵树
最后菜单的树形递归其实可以看做是二叉树的前序遍历：
按照根节点->左子树->右子树的顺序访问二叉树

image.png

先序遍历：（1）访问根节点；（2）采用先序递归遍历左子树；（3）采用先序递归遍历右子树；
(注：每个节点的分支都遵循上述的访问顺序，体现“递归调用”)
先序遍历结果：A BDFE CGHI

思维过程：
（1）先访问根节点A，
（2）A分为左右两个子树，因为是递归调用，所以左子树也遵循“先根节点-再左-再右”的顺序，所以访问B节点，
（3）然后访问D节点，
（4）访问F节点的时候有分支，同样遵循“先根节点-再左--再右”的顺序,
（5）访问E节点，此时左边的大的子树已经访问完毕，
（6）然后遵循最后访问右子树的顺序，访问右边大的子树，右边大子树同样先访问根节点C,
（7）访问左子树G,
（8）因为G的左子树没有，所以接下俩访问G的右子树H,
（9）最后访问C的右子树I

下面直接贴上代码，为了方便没有采用数据库，主要是要学会递归的思想：

Menu菜单类实体类：

package com.apple;

import java.util.List;

/**
 * @description: 菜单类
 * @author: Apple
 * @create: 2019-07-13 23:13
 **/
public class Menu {
    private int        id;
    private String     name;
    private int        parentId;
    private List<Menu> 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 List<Menu> getChildMenus() {
        return childMenus;
    }

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

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

MenuDao实体操作类，包含了对菜单的一些操作：

package com.apple.rmi;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: 菜单操作类
 * @author: Apple
 * @create: 2019-07-13 23:16
 **/
public class MenuDao {
    /**
     * @return 返回所有的菜单集合
     */
    public List<Menu> getAllMenus() {
        ArrayList<Menu> allMenus = new ArrayList();
        //构建三个一级菜单
        Menu menu = new Menu();
        menu.setId(1);
        menu.setName("一级菜单-1");
        menu.setParentId(0);
        Menu menu2 = new Menu();
        menu2.setId(2);
        menu2.setName("一级菜单-2");
        menu2.setParentId(0);
        Menu menu3 = new Menu();
        menu3.setId(3);
        menu3.setName("一级菜单-3");
        menu3.setParentId(0);

        Menu menu4 = new Menu();
        menu4.setId(4);
        menu4.setName("二级菜单-1");
        menu4.setParentId(1);  //设置在一级菜单-1 下面
        Menu menu5 = new Menu();
        menu5.setId(5);
        menu5.setName("二级菜单-2");
        menu5.setParentId(1);  //设置在一级菜单-1 下面

        Menu menu6 = new Menu();
        menu6.setId(6);
        menu6.setName("三级菜单-1");
        menu6.setParentId(4);  //设置在二级菜单-1 下面
        Menu menu7 = new Menu();
        menu7.setId(7);
        menu7.setName("二级菜单-3");
        menu7.setParentId(2);  //设置在一级菜单-2 下面
        //添加所有菜单
        allMenus.add(menu);
        allMenus.add(menu2);
        allMenus.add(menu3);
        allMenus.add(menu4);
        allMenus.add(menu5);
        allMenus.add(menu6);
        allMenus.add(menu7);
        return allMenus;
    }

    /**
     * @return 返回一级菜单集合
     */
    public List<Menu> getOneMenuList() {
        List<Menu> allMenus    = getAllMenus();
        List<Menu> oneMenuList = new ArrayList<Menu>();
        for (Menu menu : allMenus) {
            //如果当前菜单的parentId为0代表是顶级（一级）菜单
            if (menu.getParentId() == 0) {
                oneMenuList.add(menu);
            }
        }
        return oneMenuList;
    }

    /**
     * @param id
     * @return 返回下一层菜单集合
     */
    public List<Menu> getNextMenuList(int id) {
        List<Menu> allMenus     = getAllMenus();
        List<Menu> nextMenuList = new ArrayList<Menu>();
        for (Menu menu : allMenus) {
            if (menu.getParentId() == id) {  //判断上一层菜单的id是否是下一层的parentId
                nextMenuList.add(menu);
            }
        }
        return nextMenuList;
    }

    /**
     * 递归调用
     *
     * @param menuList
     */
    public void getMenuTree(List<Menu> menuList) {
        //第一次获得的是一级菜单集合，后面传入的是下一级菜单的集合
        List<Menu> oneMenuList = menuList;
        for (int i = 0; i < oneMenuList.size(); i++) {
            Menu menu = oneMenuList.get(i);
            //获得下一级的菜单集合
            List<Menu> nextMenuList = getNextMenuList(menu.getId());
            //递归终止条件判断，如果当前菜单的下一级菜单集合为空，则当前菜单为最后一级菜单
            if (nextMenuList.size() != 0) {
                //设置当前菜单的下一级菜单列表
                menu.setChildMenus(nextMenuList);
                //递归调用第二层的
                getMenuTree(nextMenuList);
            }     
        }
    }

    public static void main(String[] args) {
        MenuDao menuDao = new MenuDao();
        //先获得顶级菜单集合
        List<Menu> menuList = menuDao.getOneMenuList();
        //递归调用，最终目的是为了获得每一个Menu当中的childMenus
        menuDao.getMenuTree(menuList);
        for (Menu menu : menuList) {
            System.out.println(menu.toString());
        }
    }

}

最后的输出结果如下所示：

Menu{
  id=1,
  name='一级菜单-1',
  parentId=0,
  childMenus=[
    Menu{
      id=4,
      name='二级菜单-1',
      parentId=1,
      childMenus=[
        Menu{
          id=6,
          name='三级菜单-1',
          parentId=4,
          childMenus=null
        }
      ]
    },
    Menu{
      id=5,
      name='二级菜单-2',
      parentId=1,
      childMenus=null
    }
  ]
}
Menu{
  id=2,
  name='一级菜单-2',
  parentId=0,
  childMenus=[
    Menu{
      id=7,
      name='二级菜单-3',
      parentId=2,
      childMenus=null
    }
  ]
}
Menu{
  id=3,
  name='一级菜单-3',
  parentId=0,
  childMenus=null
}

总结：
　　其实我们所做的递归就是为了得到Menu实体类中的下一级子菜单childMenus，所以我们在平常分析问题的时候应该从本质出发，先多花一点时间想清楚问题，不要一上来就直接写代码，然后逐步思考用什么方法解决，思路最重要，有了思路转化为代码就是一件很简单的事情了