组合模式--实现树形结构

1、场景

在一些项目中，经常可以看到一些树形结构的导航栏，如：

树形结构导航栏.png

2、组合模式

又叫部分整体模式，是用于把一组相似的对象当作一个单一的对象，这种模式创建了一个包含自己对象组的类。使用组合模式来实现树形结构也简单。

3、首先创建Depart对象

public class Depart  {
    //父节点
    private String parent;
    //当前节点
    private String id;
    //子节点菜单
    private List<Depart> child;
    //省略get和set方法
}

而如何把一组数据组装成树形结构，这需要算法来处理，下面我实现了两种处理方法，注有相应的注释。

4、第一种：使用循环实现

思路：开始先获取第一级节点，循环找到对应的子节点，然后把所有子节点作为父节点，再循环找对应的子节点，依次下去，直到没有了子节点。

public static List<Depart> parse1(List<Depart> departs) {
        //获取第一级菜单
        List<Depart> heads = departs.stream().filter(e -> e.getParent() == null).collect(Collectors.toList());
        //把第一级菜单内存地址赋给result，之后的heads变化不影响result的内存地址
        List<Depart> result = heads;
        //把每一级的菜单都作为第一级菜单处理，不断查找对应的子级菜单，直到没有
        while (heads != null && heads.size() > 0) {
            List<Depart> tem = new ArrayList<>();
            for (Depart head : heads) {
                //子级菜单
                List<Depart> childs = new ArrayList<>();
                for (Depart child : departs) {
                    if (head.getId().equals(child.getParent())) {
                        childs.add(child);
                    }
                }
                //赋值到父级，对象的值改变，内存地址不变
                head.setChild(childs);
                //把当前的子级菜单保存，并作为下一轮的父级
                tem.addAll(childs);
            }
            //把子级作为下一轮的父级
            heads = tem;
        }
        return result;
    }

5、第二种：使用递归算法

思路：开始时top=null，找到第一级节点菜单，然后根据节点ID找到子节点，子节点根据自己的ID找到子子节点，不断递归下去，直到没有子节点，结束递归。

public static List<Depart> parse2(String top, List<Depart> departs) {
        List<Depart> result = new ArrayList<>();
        //处理第一级菜单，
        if (top == null) {
            for (Depart e : departs) {
                //选出一级菜单加入result
                if (StringUtils.isBlank(e.getParent())) {
                    result.add(e);
                }
            }
        } else {
            //处理子级的菜单
            for (Depart e : departs) {
                //根据parent归类到相应的父级菜单
                if (top.equals(e.getParent())) {
                    result.add(e);
                }
            }
        }
        //递归处理，若result为空，则结束递归
        //循环父节点菜单，直到没有匹配
        for (Depart e : result) {
            e.setChild(parse2(e.getId(), departs));
        }
        return result;
    }

6、使用例子

public static void main(String[] args) {
        List<Depart> list = new ArrayList<>();
        //先添加一级菜单
        Depart part = new Depart();
        part.setId("菜单0");
        list.add(part);
        part = new Depart();
        part.setId("等级0");
        list.add(part);
        for (int i = 0; i < 100; i++) {
            part = new Depart();
            part.setParent("菜单" + i);
            part.setId("菜单" + (i + 1));
            list.add(part);

            part = new Depart();
            part.setParent("等级" + i);
            part.setId("等级" + (i + 1));
            list.add(part);
        }

        Long time1 = System.currentTimeMillis();
        List<Depart> result1 = parse1(list);
        System.out.println("第一种耗时：" + (System.currentTimeMillis() - time1));
        //System.out.println(JSON.toJSONString(result1));

        Long time2 = System.currentTimeMillis();
        List<Depart> result2 = parse2(null, list);
        System.out.println("第二种耗时：" + (System.currentTimeMillis() - time2));
        //System.out.println(JSON.toJSONString(result2));
    }

总结：递归的速度是比循环的快，但当i的值很大使树形结构很深，比如i=10000时，递归就会造成栈内存溢出问题，而循环就没有这问题，但正常情况下树形结构一般不会很深，所以更推荐递归方式。