java中用递归实现树形结构

本文以一个多级菜单的案列描述了在java中如何用递归来组装树形结构的数据。

java中生成树形结构主要分为两步,

(1) 在源数据list中找到所有的根节点

(2) 递归为每一个根节点找到其所有的子节点

下面就用代码来实现下。

首先建立描述菜单结构的实体类

public class Menu {
    private String id;
    private String parentId;
    private String name;
    private List<Menu> children;
  // 省略get/set,构造方法
}

然后是测试类

public class Main {
    public static void main(String[] args) {
        //构造测试数据
        Menu menu1 = new Menu("1",null,"1");
        Menu menu2 = new Menu("1-1","1","1");
        Menu menu3 = new Menu("1-1-1","1-1","1-1-1");
        Menu menu4 = new Menu("2",null,"2");
        Menu menu5 = new Menu("2-1","2","2-1");
        Menu menu6 = new Menu("2-1-1","2-1","2-1-1");
        Menu menu7 = new Menu("1-2","1","1-2");

        List<Menu> list = new ArrayList<>();
        list.add(menu1);
        list.add(menu2);
        list.add(menu3);
        list.add(menu4);
        list.add(menu5);
        list.add(menu6);
        list.add(menu7);

        //生成树的方法
        List<Menu> tree = createTree(list);
        System.out.println(tree);
    }

    //构造树形结构
    public static List<Menu> createTree(List<Menu> sourceList){
        List<Menu> list = new ArrayList<>();
        for (Menu menu : sourceList) {
            //找到根节点进行处理，找下一级节点
            if(null == menu.getParentId()){
                //把所有的根节点放到一个list
                list.add(findChildren(menu,sourceList));
            }
        }

        return list;
    }

    public static Menu findChildren(Menu rootMenu,List<Menu> list){
        //这个方法是在找rootMenu的所有子节点,然后返回rootMenu
        for (Menu menu : list) {
            if(rootMenu.getId().equals(menu.getParentId())){
                if(rootMenu.getChildren() == null){
                    rootMenu.setChildren(new ArrayList<>());
                }
                // 把这个节点menu作为新的根节点继续向下构造树,再把构造的结果作为rootMenu的子节点
                rootMenu.getChildren().add(findChildren(menu,list));
            }
        }

        return rootMenu;
    }
}

上边的代码中先找到所有的根节点,再通过findChildren方法为每一个根节点找到所有的子节点,最终形成一个树形结构。