通用多叉树封装工具类

通用多叉树封装工具类

根据所有树节点列表，生成含有所有树形结构的多叉树列表, 列表中每个元素都是顶层根节点

import org.apache.commons.collections4.CollectionUtils;
import java.util.*;
import java.util.stream.Collectors;
import static java.util.Collections.emptyList;

public class TreeUtils {
    /**
     * 根据所有树节点列表，生成含有所有树形结构的多叉树列表, 列表中每个元素都是顶层根节点
     * <p>如果节点列表中没有顶层根节点, 则父id不在节点列表中也可以算顶层节点</p>
     *
     * @param nodes 树形节点列表
     * @param <T>   节点类型
     * @return 树形结构列表
     */
    public static <Id, T extends TreeNode<Id, T>> List<T> generateTrees(List<T> nodes) {
        if (CollectionUtils.isEmpty(nodes)) {
            return emptyList();
        }
        // 根节点列表
        List<T> roots = new ArrayList<>();
        // 父id 对应的 子节点列表 Map
        Map<Id, List<T>> parentId2ChildrenMap = new HashMap<>(nodes.size() >> 1);
        for (T node : nodes) {
            // 是根节点 或 父id为空 都算根节点
            if (node.root() || node.parentId() == null) {
                roots.add(node);
            } else {
                // 非根节点
                // 根据 父id 合并 子节点
                parentId2ChildrenMap.computeIfAbsent(node.parentId(), k -> new ArrayList<>())
                        .add(node);
            }
        }
        // 如果节点列表中没有顶层根节点, 则父id 不在节点列表中 也可以算顶层节点
        if (roots.isEmpty()) {
            // 所有节点id集合
            final Set<Id> nodeIdSet = nodes.stream().map(T::id).collect(Collectors.toSet());
            for (T node : nodes) {
                if (!nodeIdSet.contains(node.parentId())) {
                    roots.add(node);
                }
            }
        }
        for (T root : roots) {
            // 填充子节点
            setChildren(root, parentId2ChildrenMap);
        }
        return roots;
    }

    /**
     * 设置parent的所有子节点
     *
     * @param parent               父节点
     * @param parentId2ChildrenMap 父id 对应的 子节点列表 Map
     */
    private static <Id, T extends TreeNode<Id, T>> void setChildren(T parent, Map<Id, List<T>> parentId2ChildrenMap) {
        Id parentId = parent.id();
        final List<T> children = parentId2ChildrenMap.getOrDefault(parentId, emptyList());
        // 避免子列表为null
        parent.setChildren(children);
        // 如果孩子为空，则直接返回,否则继续递归设置孩子的孩子
        if (children.isEmpty()) {
            return;
        }
        // 删除已使用的数据
        parentId2ChildrenMap.remove(parentId);
        for (T child : children) {
            // 递归设置子节点
            setChildren(child, parentId2ChildrenMap);
        }
    }

    /**
     * 从所有节点列表中查找并设置parent的所有子节点
     *
     * @param parent 父节点
     * @param nodes  所有树节点列表
     */
    public static <Id, T extends TreeNode<Id, T>> void setChildren(T parent, List<T> nodes) {
        List<T> children = new ArrayList<>();
        Object parentId = parent.id();
        for (Iterator<T> ite = nodes.iterator(); ite.hasNext(); ) {
            T node = ite.next();
            if (Objects.equals(node.parentId(), parentId)) {
                children.add(node);
                // 从所有节点列表中删除该节点，以免后续重复遍历该节点
                ite.remove();
            }
        }
        // 如果孩子为空，则直接返回,否则继续递归设置孩子的孩子
        if (children.isEmpty()) {
            return;
        }
        parent.setChildren(children);
        children.forEach(m -> {
            // 递归设置子节点
            setChildren(m, nodes);
        });
    }

    /**
     * 获取指定树节点下的所有叶子节点
     *
     * @param parent 父节点
     * @param <T>    实际节点类型
     * @return 叶子节点
     */
    public static <Id, T extends TreeNode<Id, T>> List<T> getLeaves(T parent) {
        List<T> leaves = new ArrayList<>();
        fillLeaf(parent, leaves);
        return leaves;
    }

    /**
     * 将parent的所有叶子节点填充至leafs列表中
     *
     * @param parent 父节点
     * @param leaves 叶子节点列表
     * @param <T>    实际节点类型
     */
    public static <Id, T extends TreeNode<Id, T>> void fillLeaf(T parent, List<T> leaves) {
        List<T> children = parent.getChildren();
        // 如果节点没有子节点则说明为叶子节点
        if (CollectionUtils.isEmpty(children)) {
            leaves.add(parent);
            return;
        }
        // 递归调用子节点，查找叶子节点
        for (T child : children) {
            fillLeaf(child, leaves);
        }
    }

    public static <Id, T extends TreeNode<Id, T>> List<T> treeToList(List<T> nodes) {
        List<T> result = new ArrayList<>();
        for (T entity : nodes) {
            result.add(entity);
            List<T> children = entity.getChildren();
            if (children != null && children.size() > 0) {
                List<T> entityList = treeToList(children);
                result.addAll(entityList);
            }
        }
        if (result.size() > 0) {
            for (T entity : result) {
                entity.setChildren(null);
            }
        }
        return result;
    }


    /**
     * 树节点父类，所有需要使用{@linkplain TreeUtils}工具类形成树形结构等操作的节点都需要实现该接口
     *
     * @param <Id> 节点id类型
     */
    public interface TreeNode<Id, E extends TreeNode<Id, E>> {
        /**
         * 获取节点id
         *
         * @return 树节点id
         */
        Id id();

        /**
         * 获取该节点的父节点id
         *
         * @return 父节点id
         */
        Id parentId();

        /**
         * 是否是根节点
         *
         * @return true：根节点
         */
        boolean root();

        /**
         * 设置节点的子节点列表
         *
         * @param children 子节点
         */
        void setChildren(List<E> children);

        /**
         * 获取所有子节点
         *
         * @return 子节点列表
         */
        List<E> getChildren();
    }
}

具体业务类实现工具类的方法抽象方法

import com.fasterxml.jackson.annotation.JsonFormat;
import com.pwc.sdc.FPA.utils.TreeUtils;
import io.swagger.annotations.ApiModel;
import io.swagger.annotations.ApiModelProperty;
import lombok.Data;
import java.io.Serializable;
import java.util.List;
import java.util.Map;

/**
 * @description 获取Department选择组织树返回参数
 * @date
 */
@Data
@ApiModel("获取Department选择组织树返回参数")
public class GetDepartmentSelectTreeVo  implements TreeUtils.TreeNode<Long, GetDepartmentSelectTreeVo> {

    @JsonFormat(shape= JsonFormat.Shape.STRING)
    @ApiModelProperty("id")
    private Long id;

    @JsonFormat(shape= JsonFormat.Shape.STRING)
    @ApiModelProperty("父级id")
    private Long pid;
    
    @ApiModelProperty("列名")
    private String column;

    @ApiModelProperty("层级，去除隐藏后的层级")
    private Integer level;

    @ApiModelProperty("排序")
    private Integer priority;

    @ApiModelProperty("是否显示")
    private Boolean display;

    @ApiModelProperty("整棵树的排序")
    private Integer order;

    @ApiModelProperty(value = "是否是叶子节点（只针对显示的数据）")
    private boolean leafNode;
    
    @ApiModelProperty("子级department")
    private List<GetDepartmentSelectTreeVo> subDepartment = new ArrayList<>();

    @Override
    public void setChildren(List<GetDepartmentSelectTreeVo> children) {
        this.subDepartment=children;
    }

    @Override
    public List<GetDepartmentSelectTreeVo> getChildren() {
        return this.subDepartment;
    }

    @Override
    public Long id() {
        return this.id;
    }

    @Override
    public Long parentId() {
        return this.pid;
    }

    @Override
    public boolean root() {
        return null == this.id;
    }
}

调用方法生成多叉树列表

//待封装的List
List<GetDepartmentSelectTreeVo> GetDepartmentSelectTreeVoList=new ArrayList<>();
//调用生成方法
List<GetDepartmentSelectTreeVo> tree = TreeUtils.generateTrees(GetDepartmentSelectTreeVoList);