树形结构递归构建（TreeNode通用设计）

在实际开发中，我们总会遇见树性结构，比如菜单、组织机构等信息。

最近刚好有对树形结构操作的需求，特此记录一下通用设计。

首先的话，就是设计一个树形的通用结构，特此设计了一个接口（面向接口编程，好处你懂得）

主要就是这几个树形， id  parentId  children

import java.util.List;


public interface TreeNode {
    
    T id();

    
    T parentId();

    
    boolean root();

    
    void setChildren(List> children);

    
    List> getChildren();
}

然后编写具体的树形节点 来实现该接口

对于root() 方法 判断是否是父节点可以有自己的逻辑

比如 parentId 是否为 null, 或者是否等于 0

import lombok.Data;

import java.util.List;
import java.util.Objects;




@Data
public class Resource implements TreeNode {
    private String id;

    private String pid;

    private Integer type;

    private String name;

    private String icon;

    private boolean selected;

    private List children;

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

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

    @Override
    public boolean root() {
        return Objects.equals(this.pid, 0L);
    }

    @Override
    public void setChildren(List children) {
        this.children = children;
    }
}

然后就是就是递归构建获得树形结构的数据了

实现原理就是：

1. 遍历一遍数据集合， 找到所有的root节点（可能存在多个）

2. 然后遍历这些root节点, 把这些节点当成父节点， 递归查询其子节点。

这里做的优化就是：

每当找到了某个节点所属的父级节点，就把该节点从数据集合中删掉，避免了后续的重复遍历

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.Objects;


public class TreeUtils {

    
    public static  List generateTrees(List nodes) {
        List roots = new ArrayList<>();
        for (Iterator ite = nodes.iterator(); ite.hasNext(); ) {
            T node = ite.next();
            if (node.root()) {
                roots.add(node);
                // 从所有节点列表中删除该节点，以免后续重复遍历该节点
                ite.remove();
            }
        }

        roots.forEach(r -> {
            setChildren(r, nodes);
        });
        return roots;
    }

    
    @SuppressWarnings("all")
    public static  void setChildren(T parent, List nodes) {
        List children = new ArrayList<>();
        Object parentId = parent.id();
        for (Iterator 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);
        });
    }

    
    public static > List getLeafs(T parent) {
        List leafs = new ArrayList<>();
        fillLeaf(parent, leafs);
        return leafs;
    }

    
    @SuppressWarnings("all")
    public static  void fillLeaf(T parent, List leafs) {
        List children = parent.getChildren();
        // 如果节点没有子节点则说明为叶子节点
        if (children.isEmpty()) {
            leafs.add(parent);
            return;
        }
        // 递归调用子节点，查找叶子节点
        for (T child : children) {
            fillLeaf(child, leafs);
        }
    }
}