通用化递归建树与裁剪树_java 树裁剪

• 背景：项目中经常碰到需要生成森林/树（严格上讲，非二叉树的森林）的场景，比如部门树、菜单树等等
  树的遍历:无非BSF/DSF,借助递归/线性表（栈、队列）实现。
• 要点有三：
  1.用递归方式实现DSF遍历来构建森林/树
  2.利用接口+泛型，抽象化树节点，以便支持更多不同类型节点（部门/菜单）的场景
  3.标记化泛型树节点，实现对树的裁剪

1.如何构建一棵森林/树？

• 在构建之前，需要定义树节点。简单起见，定义树节点如下

public class Node {
    private String id;
    private String parentId;
    private String name;
    private List<Node> children = new ArrayList<>();

    public Node(String id, String parentId, String name) {
        this.id = id;
        this.parentId = parentId;
        this.name = name;
    }
    ......
}
1
2
3
4
5
6
7
8
9
10
11
12
13

• 利用递归方式构建森林/树

public static List<Node> buildTree(Node parent,List<Node> nodes){
    if(Objects.isNull(parent)){
        return nodes.stream().filter(node->Objects.equals(node.getParentId(), 0)).map(node->{
            node.getChildren().addAll(buildTree(node,nodes));
            return node;
        }).collect(Collectors.toList());
    }else{
        return nodes.stream().filter(node->Objects.equals(node.getParentId() , parent.getId())).map(node->{
            node.getChildren().addAll(buildTree(node,nodes));
            return node;
        }).collect(Collectors.toList());
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 以构建一棵动物分类树为例，测试如下

List<Node> nodes = new ArrayList<Node>(){
  {
    add(new Node(1,0,"动物-0"));
    add(new Node(2,1,"无脊椎-1"));
    add(new Node(3,2,"无外骨骼-1-1"));
    add(new Node(4,3,"身体不分节-1-1-1"));
    add(new Node(5,4,"涡虫-1-1-1-1"));
    add(new Node(6,3,"身体分节-1-1-2"));
    add(new Node(7,6,"蚯蚓-1-1-2-1"));
    add(new Node(8,2,"有外骨骼-1-2"));
    add(new Node(9,8,"有翅-1-2-1"));
    add
1
2
3
4
5
6
7
8
9
10
11