将数据库表记录生成树，存储树形结构

有一类数据在数据库表中是一行一行地存储的，一旦查询出来并展示到前端页面，就呈现出“树状”。例如某大公司的部门数据，可分为一级、二级、三级部门等，在前端页面通常以树形展示。如何设计呢？

第一版

import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.ArrayList;
import java.util.List;

@Data
@AllArgsConstructor
@NoArgsConstructor
public class Node {
    /**
     * 主键id
     */
    private Long id;

    /**
     * 名称
     */
    private String name;

    /**
     * 关联父id
     */
    private Long parentId;

    /**
     * 当前节点所处层级，通常level在10以内
     * 非必须属性
     */
    private int level;

    /**
     * 关联子对象集合
     */
    private List<Node> children = new ArrayList<>();

    public Node(Long id, String name, Long parentId, int level) {
        this.id = id;
        this.name = name;
        this.parentId = parentId;
        this.level = level;
    }
}

import org.apache.commons.collections4.CollectionUtils;
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

public class TreeUtil {
    /**
     * 根据parentId属性，使用递归算法，为每个节点的children属性赋值，实际上，就是生成一棵树
     * @param nodeList children属性为null的节点列表，可理解为某数据库表的集合
     * @return children属性正确的节点列表，其size()即为一级节点数量
     */
    public static List<Node> build(List<Node> nodeList) {
        List<Node> res = new ArrayList<>();
        for (Node node : nodeList) {
            // 如果是父节点
            if (node.getParentId() == 0L) {
                buildChildren(node, nodeList);
                res.add(node);
            }
        }
        return res;
    }

    /**
     *  递归查找某个节点的孩子
     * @param node
     * @param list
     */
    public static void buildChildren(Node node, final List<Node> list) {
        // 从list中找到node的孩子
        List<Node> children = list.stream().filter(p->p.getParentId().equals(node.getId())).collect(Collectors.toList());
        if (!CollectionUtils.isEmpty(children)) {
            for (Node child : children) {
                // 递归调用，从list中找到孩子的孩子
                buildChildren(child, list);
            }
            node.setChildren(children);
        }
    }

    /**
     * 以可读的样式打印部门树，仅用于调试
     * @param list
     */
    public static void printTree(List<Node> list) {
        if (CollectionUtils.isEmpty(list)) {
            return;
        }

        for (Node node : list) {
            System.out.println();
            int level = node.getLevel();

            if (level == 0) {
                // 不打印0级
            } else if (level == 1) {
                System.out.print("" + node.getName());
            } else if (level == 2) {
                System.out.print("  + " + node.getName());
            } else if (level == 3) {
                System.out.print("    + " + node.getName());
            } else if (level == 4) {
                System.out.print("      + " + node.getName());
            } else {
                throw new IllegalArgumentException("暂时支持到4级");
            }
            printTree(node.getChildren());
        }
    }
}

import org.junit.Test;
import java.util.ArrayList;
import java.util.List;

public class ServiceTest {

    /**
     * 只有一级部门
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test() {
        // 模拟从数据库中查询出来的结果集
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node(1L,"某某集团公司",0L, 0));
        nodes.add(new Node(2L,"部门1-1",1L, 1));
        nodes.add(new Node(3L,"部门1-2",1L, 1));
        nodes.add(new Node(4L,"部门1-3",1L, 1));
        List<Node> list = TreeUtil.build(nodes);
        TreeUtil.printTree(list);
    }

    /**
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * | 5  | 部门2-1      | 2        | 2     |
     * | 6  | 部门2-2      | 2        | 2     |
     * | 7  | 部门2-3      | 3        | 2     |
     * | 8  | 部门2-4      | 3        | 2     |
     * | 9  | 部门2-5      | 4        | 2     |
     * | 10 | 部门2-6      | 4        | 2     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test02() {
        // 模拟从数据库中查询出来的结果集
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node(1L,"某某集团公司",0L, 0));
        nodes.add(new Node(2L,"部门1-1",1L, 1));
        nodes.add(new Node(3L,"部门1-2",1L, 1));
        nodes.add(new Node(4L,"部门1-3",1L, 1));

        nodes.add(new Node(5L,"部门2-1",2L, 2));
        nodes.add(new Node(6L,"部门2-2",2L, 2));
        nodes.add(new Node(7L,"部门2-3",3L, 2));
        nodes.add(new Node(8L,"部门2-4",3L, 2));
        nodes.add(new Node(9L,"部门2-5",4L, 2));
        nodes.add(new Node(10L,"部门2-6",4L, 2));
        List<Node> list = TreeUtil.build(nodes);
        TreeUtil.printTree(list);
    }

    /**
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * | 5  | 部门2-1      | 2        | 2     |
     * | 6  | 部门2-2      | 2        | 2     |
     * | 7  | 部门2-3      | 3        | 2     |
     * | 8  | 部门2-4      | 3        | 2     |
     * | 9  | 部门2-5      | 4        | 2     |
     * | 10 | 部门2-6      | 4        | 2     |
     * | 11 | 部门3-1      | 5        | 3     |
     * | 12 | 部门3-2      | 5        | 3     |
     * | 13 | 部门3-3      | 6        | 3     |
     * | 14 | 部门3-4      | 6        | 3     |
     * | 15 | 部门3-5      | 7        | 3     |
     * | 16 | 部门3-6      | 7        | 3     |
     * | 17 | 部门3-7      | 8        | 3     |
     * | 18 | 部门3-8      | 8        | 3     |
     * | 19 | 部门3-9      | 9        | 3     |
     * | 20 | 部门3-10     | 9        | 3     |
     * | 21 | 部门3-11     | 10       | 3     |
     * | 22 | 部门3-12     | 10       | 3     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test03() {
        // 模拟从数据库中查询出来的结果集
        List<Node> nodes = new ArrayList<>();
        nodes.add(new Node(1L,"某某集团公司",0L, 0));
        nodes.add(new Node(2L,"部门1-1",1L, 1));
        nodes.add(new Node(3L,"部门1-2",1L, 1));
        nodes.add(new Node(4L,"部门1-3",1L, 1));

        nodes.add(new Node(5L,"部门2-1",2L, 2));
        nodes.add(new Node(6L,"部门2-2",2L, 2));
        nodes.add(new Node(7L,"部门2-3",3L, 2));
        nodes.add(new Node(8L,"部门2-4",3L, 2));
        nodes.add(new Node(9L,"部门2-5",4L, 2));
        nodes.add(new Node(10L,"部门2-6",4L, 2));

        nodes.add(new Node(11L,"部门3-1",5L, 3));
        nodes.add(new Node(12L,"部门3-2",5L, 3));
        nodes.add(new Node(13L,"部门3-3",6L, 3));
        nodes.add(new Node(14L,"部门3-4",6L, 3));
        nodes.add(new Node(15L,"部门3-5",7L, 3));
        nodes.add(new Node(16L,"部门3-6",7L, 3));
        nodes.add(new Node(17L,"部门3-7",8L, 3));
        nodes.add(new Node(18L,"部门3-8",8L, 3));
        nodes.add(new Node(19L,"部门3-9",9L, 3));
        nodes.add(new Node(20L,"部门3-10",9L, 3));
        nodes.add(new Node(21L,"部门3-11",10L, 3));
        nodes.add(new Node(22L,"部门3-12",10L, 3));
        List<Node> list = TreeUtil.build(nodes);
        TreeUtil.printTree(list);
    }
}

第二版

如果你有一个“公司部门”树，他有一个“医院科室”树，它们都大同小异，那 TreeUtil.java 中将有很多重复的代码。能否将抽象层次提升，搞一个通用的，即带泛型的实现呢？

import lombok.Data;
import java.util.List;

/**
 * T可能是公司的部门、医院的科室等实体类
 */
@Data
public class GenericTree<T> {
    private T t;
    private List<T> children;
}

/**
 * 无论是公司的部门，还是医院的科室等实体类，必须有自身ID和父节点ID
 */
public interface IBaseTree {
    Long getId();
    Long getParentId();
}

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.stream.Collectors;

public class TreeUtil2 {

    public static <T extends IBaseTree> List<GenericTree> build(List<T> list){
        List<GenericTree> res = new ArrayList<>();
        List<T> collect = list.stream().filter(p -> p.getParentId() == 0).collect(Collectors.toList());
        for (T t : collect) {
            GenericTree ztree = new GenericTree();
            setZtree(t, list, ztree);
            res.add(ztree);
        }
        return res;
    }

    private static <T extends IBaseTree> void setZtree(T t, List<T> list, GenericTree ztree) {
        ztree.setT(t);
        ztree.setChildren(buildChildren(t, list));
    }

    private static <T extends IBaseTree> List buildChildren(T t, List<T> list) {
        List res = new ArrayList<>();
        for (T l : list) {
            GenericTree ztree = new GenericTree();
            if(Objects.equals(l.getParentId(), t.getId())){
                setZtree(l, list, ztree);
                res.add(ztree);
            }
        }
        return res;
    }
}

import org.apache.commons.collections4.CollectionUtils;
import org.junit.Test;
import java.util.ArrayList;
import java.util.List;

public class Service2Test {

    /**
     * 只有一级部门
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test() {
        // 模拟从数据库中查询出来的结果集
        List<Node2> nodes = new ArrayList<>();
        nodes.add(new Node2(1L,"某某集团公司",0L, 0));
        nodes.add(new Node2(2L,"部门1-1",1L, 1));
        nodes.add(new Node2(3L,"部门1-2",1L, 1));
        nodes.add(new Node2(4L,"部门1-3",1L, 1));
        List<GenericTree> list = TreeUtil2.build(nodes);
        printTree(list);
    }

    /**
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * | 5  | 部门2-1      | 2        | 2     |
     * | 6  | 部门2-2      | 2        | 2     |
     * | 7  | 部门2-3      | 3        | 2     |
     * | 8  | 部门2-4      | 3        | 2     |
     * | 9  | 部门2-5      | 4        | 2     |
     * | 10 | 部门2-6      | 4        | 2     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test02() {
        // 模拟从数据库中查询出来的结果集
        List<Node2> nodes = new ArrayList<>();
        nodes.add(new Node2(1L,"某某集团公司",0L, 0));
        nodes.add(new Node2(2L,"部门1-1",1L, 1));
        nodes.add(new Node2(3L,"部门1-2",1L, 1));
        nodes.add(new Node2(4L,"部门1-3",1L, 1));

        nodes.add(new Node2(5L,"部门2-1",2L, 2));
        nodes.add(new Node2(6L,"部门2-2",2L, 2));
        nodes.add(new Node2(7L,"部门2-3",3L, 2));
        nodes.add(new Node2(8L,"部门2-4",3L, 2));
        nodes.add(new Node2(9L,"部门2-5",4L, 2));
        nodes.add(new Node2(10L,"部门2-6",4L, 2));
        List<GenericTree> list = TreeUtil2.build(nodes);
        printTree(list);
    }

    /**
     * +----+--------------+----------+-------+
     * | id | name         | parentId | level |
     * +----+--------------+----------+-------+
     * | 1  | 某某集团公司 | 0        | 0     |
     * | 2  | 部门1-1      | 1        | 1     |
     * | 3  | 部门1-2      | 1        | 1     |
     * | 4  | 部门1-3      | 1        | 1     |
     * | 5  | 部门2-1      | 2        | 2     |
     * | 6  | 部门2-2      | 2        | 2     |
     * | 7  | 部门2-3      | 3        | 2     |
     * | 8  | 部门2-4      | 3        | 2     |
     * | 9  | 部门2-5      | 4        | 2     |
     * | 10 | 部门2-6      | 4        | 2     |
     * | 11 | 部门3-1      | 5        | 3     |
     * | 12 | 部门3-2      | 5        | 3     |
     * | 13 | 部门3-3      | 6        | 3     |
     * | 14 | 部门3-4      | 6        | 3     |
     * | 15 | 部门3-5      | 7        | 3     |
     * | 16 | 部门3-6      | 7        | 3     |
     * | 17 | 部门3-7      | 8        | 3     |
     * | 18 | 部门3-8      | 8        | 3     |
     * | 19 | 部门3-9      | 9        | 3     |
     * | 20 | 部门3-10     | 9        | 3     |
     * | 21 | 部门3-11     | 10       | 3     |
     * | 22 | 部门3-12     | 10       | 3     |
     * +----+--------------+----------+-------+
     */
    @Test
    public void test03() {
        // 模拟从数据库中查询出来的结果集
        List<Node2> nodes = new ArrayList<>();
        nodes.add(new Node2(1L,"某某集团公司",0L, 0));
        nodes.add(new Node2(2L,"部门1-1",1L, 1));
        nodes.add(new Node2(3L,"部门1-2",1L, 1));
        nodes.add(new Node2(4L,"部门1-3",1L, 1));

        nodes.add(new Node2(5L,"部门2-1",2L, 2));
        nodes.add(new Node2(6L,"部门2-2",2L, 2));
        nodes.add(new Node2(7L,"部门2-3",3L, 2));
        nodes.add(new Node2(8L,"部门2-4",3L, 2));
        nodes.add(new Node2(9L,"部门2-5",4L, 2));
        nodes.add(new Node2(10L,"部门2-6",4L, 2));

        nodes.add(new Node2(11L,"部门3-1",5L, 3));
        nodes.add(new Node2(12L,"部门3-2",5L, 3));
        nodes.add(new Node2(13L,"部门3-3",6L, 3));
        nodes.add(new Node2(14L,"部门3-4",6L, 3));
        nodes.add(new Node2(15L,"部门3-5",7L, 3));
        nodes.add(new Node2(16L,"部门3-6",7L, 3));
        nodes.add(new Node2(17L,"部门3-7",8L, 3));
        nodes.add(new Node2(18L,"部门3-8",8L, 3));
        nodes.add(new Node2(19L,"部门3-9",9L, 3));
        nodes.add(new Node2(20L,"部门3-10",9L, 3));
        nodes.add(new Node2(21L,"部门3-11",10L, 3));
        nodes.add(new Node2(22L,"部门3-12",10L, 3));
        List<GenericTree> list = TreeUtil2.build(nodes);
        printTree(list);
    }

    private static final class Node2 implements IBaseTree {
        private Long id;
        private Long parentId;
        private String name;
        private int level;

        public Node2(Long id, String name, Long parentId, int level) {
            this.id = id;
            this.name = name;
            this.parentId = parentId;
            this.level = level;
        }

        @Override
        public Long getId() {
            return id;
        }

        public void setId(Long id) {
            this.id = id;
        }

        @Override
        public Long getParentId() {
            return parentId;
        }

        public void setParentId(Long parentId) {
            this.parentId = parentId;
        }

        public String getName() {
            return name;
        }

        public void setName(String name) {
            this.name = name;
        }

        public int getLevel() {
            return level;
        }

        public void setLevel(int level) {
            this.level = level;
        }
    }

    /**
     * 以可读的样式打印部门树，仅用于调试
     * @param list
     */
    private static void printTree(List<GenericTree> list) {
        if (CollectionUtils.isEmpty(list)) {
            return;
        }

        for (GenericTree ztree : list) {
            // TODO 坏的味道
            Node2 node = (Node2)ztree.getT();

            System.out.println();
            int level = node.getLevel();

            if (level == 0) {
                // 不打印0级
            } else if (level == 1) {
                System.out.print("" + node.getName());
            } else if (level == 2) {
                System.out.print("  + " + node.getName());
            } else if (level == 3) {
                System.out.print("    + " + node.getName());
            } else if (level == 4) {
                System.out.print("      + " + node.getName());
            } else {
                throw new IllegalArgumentException("暂时支持到4级");
            }
            printTree(ztree.getChildren());
        }
    }
}

把大象装进冰箱里（把树形数据装进数据库表里）

上面说的“树形数据”也可以称之为“层次化数据”（hierarchical data），对于如何装进表里，业界有各种解决思路：

Adjacency list (邻接表)，就是上面的做法，通俗地讲就是，每个节点只记录自己的父节点，不记录爷爷节点、祖父节点，只需要一张表即可。
Closure table (闭合表)，通俗地讲就是，每个节点不仅要记录自己的父节点，还要记录自己的爷爷节点、自己的祖父节点、依此类推，需要两张表。这看似复杂，但当需求变态时，还得闭合表好使，例如进行某棵子树的移动。这篇博客有详细讲解，其中某些SQL的写法很有技巧性，从零写还真烧脑。
Path enumeration (路径枚举)，待补充。
Nested Set（嵌套集合），待补充。