树形结构数据是一种比较常见的数据格式，主要作为前端树形、级联等控件的数据源，以更清晰、更美观大方地展示数据之间的层次或所属关系，如常常用于表示"权限/菜单"、"分类"、"地区/区域"、"公司部门"等具有隶属关系的信息。
图1 级联选择器
图2 树形控件
组件所使用的数据，即树形结构数据，主要是以下面的格式出现，其中我们称数据中的每个对象为"节点"，按照隶属关系，还可以分为两种类型，一种是父节点，另一种是子节点。有一种父节点更为特殊，由于它处于最顶部，没有父节点，我们常称其为"根节点"；"children"被称为当前节点的"子节点"。
[
{
"name": "xxx",
"children": [
{
"name": "xxx",
"children": null,
"id": 3,
"parentId": 1
},
],
"id": 1,
"parentId": -1
},
...
]
不过，一般情况下，数据库或其他方式不会直接存储这种具有层次关系的数据，数据往往都以扁平的形式存在，仅通过某个字段属性来表示它们之间的关系（如上面所示的parent_id属性），一方面是为了更容易查询，另一方面是为了让存储数据更通用、更容易操作。
图3 存储在数据库中的商品分类数据
所以实际上，这种格式的数据，是需要专门编写方法或函数来生成的，这也正是本篇文章的主题所在。
作者有在网上查找过很多实现的方案，但由于大家的思维个性、编程风格不同，具体的落地实现也不同，堪称五花八门、各显神通... 有的写得比较复杂，让人难以理解；有的虽然写得简单，但有些地方显得很累赘；还有的就是调用特别复杂。
总体上，我认为它们的最大不足之处就是，经常是传入一些硬编码的数据类型，限制了生成树形结构数据方法的通用性，这样会有很高的概率出现重复性的代码。比如，昨天"权限菜单"需要树形结构数据，需要编写一套方法，而今天"公司部门"也需要树形结构数据，由于方法不具备通用性，因此也必须再编写另一套方法。
这样既不美观，后期也不好维护。
我想要的是一个更通用、更简单的实现方案。
因此，以上查询结果并不符合我的需求，于是决定自己手动编写。（在考虑到并不难实现之后...）
一、定义类
以下将生成树形结构数据的类声明为"TreeMaker"，这个类只对外暴露一个"make"方法，调用这个方法后，传入的数据就能转为树形结构格式数据。
public class TreeMaker {
public static <T extends TreeNode<T>> List<T> make(List<T> list) {
// ...
}
private static <T extends TreeNode<T>> List<T> makeChildren(T parent, List<T> list, List<T> toRemove) {
// ...
}
}
二、准备接口
想要具有通用性，接口是必要的。
首先要准备的是TreeNode接口，这个接口接收一个泛型参数T，参数对应的正是实际的数据类型，所有想要使用本生成树形结构数据方法的数据类型，都必须要实现该接口。
public interface TreeNode<T> {
void setChildren(List<T> children);
boolean isRootNode();
boolean isParentNode(T node);
}
这个接口主要有三个方法：
- isRootNode()：用于判断某个节点是否为根节点；
- isParentNode(T node)：判断当前节点是否为传入节点的父节点；
- setChildren(List<T> children)：为节点设置children子节点。
实现的逻辑需要根据实际的数据类型而定。
三、编写TreeMaker类方法的逻辑
1、make方法
public static <T extends TreeNode<T>> List<T> make(List<T> list) {
if (list == null || list.size() == 0) {
return new ArrayList<>();
}
List<T> rootNodes = list.stream().filter(T::isRootNode).collect(Collectors.toList());
list.removeAll(rootNodes);
List<T> toRemove = new ArrayList<>();
for (T rootNode : rootNodes) {
makeChildren(rootNode, list, toRemove);
if (toRemove.size() > 0) {
// 将已经处理过的节点从列表中删除
list.removeAll(toRemove);
toRemove.clear();
}
}
return rootNodes;
}
2、makeChildren
private static <T extends TreeNode<T>> List<T> makeChildren(T parent, List<T> list, List<T> toRemove) {
List<T> children = new ArrayList<>();
for (T node : list) {
if (parent.isParentNode(node)) {
toRemove.add(node);
// 递归添加节点
node.setChildren(makeChildren(node, list, toRemove));
children.add(node);
}
}
if (children.size() > 0) {
parent.setChildren(children);
return children;
}
return null;
}
四、使用TreeMaker
本篇文章的demo放在这里，需要的读者自行下载。
在完成了以上的逻辑后，整个生成树形结构数据的方案也宣告完成了，但在使用TreeMaker之前，还差最后一步。
其实前面也有提到过，想要使用TreeMaker的数据类型，必须要实现TreeNode接口。
1、实现TreeNode接口
下面的测试数据TestNode类型为例，该类型判断为"根节点"的逻辑比较简单，如果"parentId"属性为null，则认定其为根节点；而如果判断某个节点的"parentId"与当前节点的"id"相同，则会认定传入的节点为当前节点的子节点。
public class TestNode implements TreeMaker.TreeNode<TestNode> {
// ... 省略
@JSONField(serialize = false)
public boolean isRootNode() {
return parentId == null;
}
public boolean isParentNode(TestNode node) {
return id.equals(node.parentId);
}
public void setChildren(List<TestNode> children) {
this.children = children;
}
public List<TestNode> getChildren() {
return children;
}
}
为了测试方法的通用性，此处还额外准备了另一种数据类型，其实现接口的逻辑不同于TestNode类型。
public class TestCategory implements TreeMaker.TreeNode<TestCategory> {
// ... 省略
@JSONField(serialize = false)
public boolean isRootNode() {
return pId.equals(-1); // 此处判断是否为根节点的依据是其pId是否为-1
}
public boolean isParentNode(TestCategory node) {
return id.equals(node.pId);
}
public void setChildren(List<TestCategory> children) {
this.children = children;
}
public List<TestCategory> getChildren() {
return children;
}
}
2、准备测试类、测试数据和测试方法
public class Test {
public static void main(String[] args) {
example1();
example2();
}
/**
* 测试方法1
* ---
* id/name/parent_id
* ---
* 1/node-1/null
* 2/node-2/null
* 3/node-3/1
* 4/node-4/1
* 5/node-5/4
* 6/node-6/2
* 7/node-7/5
* 8/node-8/5
* 9/node-9/2
* 10/node-10/2
*/
public static void example1() {
List<TestNode> list = new ArrayList<>();
TestNode n1 = new TestNode(1, "node-1", null);
TestNode n2 = new TestNode(2, "node-2", null);
list.add(n1);
list.add(n2);
TestNode n3 = new TestNode(3, "node-3", 1);
TestNode n4 = new TestNode(4, "node-4", 1);
TestNode n5 = new TestNode(5, "node-5", 4);
TestNode n6 = new TestNode(6, "node-6", 2);
TestNode n7 = new TestNode(7, "node-7", 5);
TestNode n8 = new TestNode(8, "node-8", 5);
TestNode n9 = new TestNode(9, "node-9", 2);
TestNode n10 = new TestNode(10, "node-19", 2);
list.add(n3);
list.add(n4);
list.add(n5);
list.add(n6);
list.add(n7);
list.add(n8);
list.add(n9);
list.add(n10);
List<TestNode> t = TreeMaker.make(list);
// 使用fastjson将列表转为json字符串
String treeJson = JSON.toJSONString(t, SerializerFeature.WriteMapNullValue);
String path = "/Users/xieshixin/personalplace/demo/treeMaker-demo/tree.json";
write(path, treeJson);
}
/**
* 测试方法2
* ---
* id/category_name/p_id
* ---
* 1/数码/-1
* 2/服装/-1
* 3/手机/1
* 4/笔记本/1
* 5/耳机/1
* 6/外套/2
* 7/衬衫/2
* 8/牛仔裤/2
* 9/休闲裤/2
* 10/电器/-1
* 11/冰箱/10
* 12/电磁炉/10
*/
public static void example2() {
List<TestCategory> list = new ArrayList<>();
// 根节点
TestCategory n1 = new TestCategory(1, "数码", -1);
TestCategory n2 = new TestCategory(2, "服装", -1);
TestCategory n3 = new TestCategory(10, "电器", -1);
list.add(n1);
list.add(n2);
list.add(n3);
TestCategory n4 = new TestCategory(3, "手机", 1);
TestCategory n5 = new TestCategory(4, "笔记本", 1);
TestCategory n6 = new TestCategory(5, "耳机", 1);
TestCategory n7 = new TestCategory(6, "外套", 2);
TestCategory n8 = new TestCategory(7, "衬衫", 2);
TestCategory n9 = new TestCategory(8, "牛仔裤", 2);
TestCategory n10 = new TestCategory(9, "休闲裤", 2);
TestCategory n11 = new TestCategory(11, "冰箱", 10);
TestCategory n12 = new TestCategory(12, "电磁炉", 10);
list.add(n4); list.add(n5); list.add(n6); list.add(n7); list.add(n8); list.add(n9);
list.add(n10); list.add(n11); list.add(n12);
String path = "/Users/xieshixin/personalplace/demo/treeMaker-demo/category-tree.json";
List<TestCategory> t = TreeMaker.make(list);
String treeJson = JSON.toJSONString(t, SerializerFeature.WriteMapNullValue);
write(path, treeJson);
}
public static void write(String path, String data) {
Writer writer = null;
try {
writer = new FileWriter(path);
writer.write(data);
} catch (IOException e) {
e.printStackTrace();
} finally {
if (writer != null) {
try {
writer.close();
} catch (IOException e) {
e.printStackTrace();
}
}
}
}
}
执行测试类的入口方法后，将会得到以下的数据。
图4 结果1
图5 结果2
至此，本篇文章也进入尾声了。
虽然生成树形结构数据的代码算不上复杂，但是如果平时不注意，总是以硬编码的形式来实现的话，难免会出现很多无用、重复的逻辑，一个项目中出现一两处还可以接受，而几个以上的项目多处出现这种功能相同、实现有差异的代码的话，维护难度是不言而喻的，仅仅是看到都会让人觉得头大心烦，更别说改动了。
同样的，其他功能模块也会存在类似的情况，因此，想要避免这种情况的发生，只能从日常的点滴开始做起，把功能抽象，再抽象，使之变得通用、广泛，这样后期无论是修改，还是维护或管理，都会变得简单很多。
以上就是本文的所有内容，希望对读者有所帮助。