一、背景
在编程中，树形结构是一种常见的数据结构，用于表示具有层级关系的数据。比如机构树、菜单树、目录树、文件夹树等等。
在过去的这些年，我和很多人潜移默化的会使用递归函数来遍历和构造树形结构。然而，递归虽然直观，但在处理大型数据集时可能会导致性能问题，尤其是当递归深度过大时，稍不注意还可能引发栈溢出错误。
最近，我在处理一个项目时，发现了一种不使用递归来构造树形结构的方法。这种方法基于类似哈希映射（HashMap）和迭代的方式，能够高效地处理大量数据，同时避免了递归带来的潜在问题。
这个方法来自于前端的zTree插件，ztree是一个依靠 jQuery 库实现的多功能 “树插件”。其优异的性能、灵活的配置、多种功能的组合是 zTree 最大优点。这个插件我也一直在使用，真的特别的好，以前中国各行各业好多Web系统中，都是用ztree去做树结构导航功能。
zTree的主页：https://www.treejs.cn/
本文会基于zTree中的某个方法，尝试用Java实现一遍，分享给大家。
二、正文开始
2.1、从前端zTree插件中学习
源码地址：https://gitee.com/zTree/zTree_v3/blob/master/js/jquery.ztree.core.js
如果有了一定的编程能力，建议大家还是看下ztree的源码，不管是后端还是前端，它的源码也是值得我们参考学习的。比如本文说的树构造的问题，很多人在写机构树、菜单树这种业务功能的时候，可能会用递归算法去把一个数组结构的数据，根据一定的标识构造成树结构的形式(即带有层级结构格式，例如文件夹层级)的数据，可能在工作或生活中，由于缺少对代码的深度思考，让我们的内心忽略了实现这种业务的其他办法。
ztree是一个jQuery的插件，你只要提供类似于如下的基本的二维数据结构：
var nodes = [
{id:1, pId:0, name: "父节点1"},
{id:11, pId:1, name: "子节点1"},
{id:12, pId:1, name: "子节点2"}
];
它内部就会自动处理变成如下的数据结构：
var nodes = [{
name: "父节点1",
id:1,
children: [
{id:11,name: "子节点1"},
{id:12,name: "子节点2"}
]}
];
那ztree是怎么做的，首先其提供了一个【setting.data.simpleData.enable】配置项，用于告诉ztree是否是简单格式的数据(即二维表格的数据数据)，然后根据这个配置项，让我们找到其源码目录下的js文件夹下的jquery.ztree.core.js文件，搜索一下，大概在895行的位置上，有一段如下代码：
if (setting.data.simpleData.enable) {
newNodes = data.transformTozTreeFormat(setting, newNodes);
}
这段代码的意图很明显了吧，如果这个参数配置项为真，就把现在结构的数据传递到transformTozTreeFormat这个方法中，并返回一个新结构，而这个新结构便是具有树结构的数据了。 接下来，在搜索一下这个方法，代码段如下，20行左右的代码量：
transformTozTreeFormat: function (setting, sNodes) {
var i, l,
key = setting.data.simpleData.idKey,
parentKey = setting.data.simpleData.pIdKey,
childKey = setting.data.key.children;
if (!key || key == "" || !sNodes) return [];
if (tools.isArray(sNodes)) {
var r = [];
var tmpMap = {};
for (i = 0, l = sNodes.length; i < l; i++) {
tmpMap[sNodes[i][key]] = sNodes[i];
}
for (i = 0, l = sNodes.length; i < l; i++) {
if (tmpMap[sNodes[i][parentKey]] && sNodes[i][key] != sNodes[i][parentKey]) {
if (!tmpMap[sNodes[i][parentKey]][childKey])
tmpMap[sNodes[i][parentKey]][childKey] = [];
tmpMap[sNodes[i][parentKey]][childKey].push(sNodes[i]);
} else {
r.push(sNodes[i]);
}
}
return r;
} else {
return [sNodes];
}
}
当你看到里面的那个for是否会有几分钟的不止所措呢，我们来优化下代码：
for (i = 0, l = sNodes.length; i < l; i++) {
var nodeValue = sNodes[i][key];
var parentNodeValue = sNodes[i][parentKey];
if (tmpMap[parentNodeValue] && nodeValue != parentNodeValue) {
if (!tmpMap[parentNodeValue][childKey])
tmpMap[parentNodeValue][childKey] = [];
tmpMap[parentNodeValue][childKey].push(sNodes[i]);
} else {
r.push(sNodes[i]);
}
}
让我们来解析一下刚才上面的代码：
1、首先读取了3行参数配置项，动态获取了id的名称是那个属性，父Id的名称是哪个属性，子集合是哪个属性；
2、然后判断是否为空数据、是否指定了id的属性，没有指定的话返回当前数组；
3、定义了2个属性:r、tmpMap，其中r用来存储新结构数据，tmpMap用于将每一行的数据进行一个映射绑定，相当于做了一个根据唯一标识ID快速从数组中查询某个对象的的操作，如果要取出ID等于15的数据，直接tmpMap["15"]即可。
4、开始遍历数据，判断临时的那个tmpMap映射中是否有当前节点的父节点数据，并且当前节点的标识和父标识不相等： 如果条件成立，说明当前节点是那个父节点的儿子，那么在判断当前节点的父节点的儿子数组是否为空或者不存在，如果不存在，先初始化一个儿子的空数组，然后把当前节点，放到那个父节点的儿子数组里面，依次循环往复，如果当前节点的父节点在临时的tmpMap映射中不存在，说明了，这时的遍历的节点，就是是一个最顶级的节点了(有些时候根据提供的数据会是多个)； 反之条件不成立，说明当前节点为顶级节点
5、返回新的树结构的数组。
再简单总结一下：
函数首先获取了节点数据的id、父节点id和子节点键名，然后遍历sNodes数组，将每个节点按id存入临时映射对象tmpMap中，再遍历一次sNodes，将每个节点添加到其父节点的子节点数组中（如果父节点存在且当前节点不是父节点本身）。最后返回所有根节点（没有父节点的节点）的数组。
我不知道以上我的这段解析是否可以让你明白，建议经验不足的开发者可以多思考一下。挺好的。
ztree这段代码，其实非常巧妙，20行简简单单的代码，不仅扩展了我们的思维方式，也提高了我们的开发能力，做某些功能开发时，也会联想到这种思想，并用这种思想解决一些实际的构造和遍历的问题。
2.2、用Java实现一遍
如果我们理解了JavaScript的方法，那我们用Java实现一遍是否可以呢，答案是没问题的。
示例代码如下所示，首先我们创建一个TreeNode节点类：
import lombok.Data;
import java.util.ArrayList;
import java.util.List;
@Data
public class TreeNode {
private String id;
private String parentId;
private List<TreeNode> children;
// 假设还有其他字段...
public TreeNode(String id, String parentId) {
this.id = id;
this.parentId = parentId;
this.children = new ArrayList<>();
}
}
然后我们在创建一个转换类TreeUtils：
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TreeUtils {
public static List<TreeNode> transformToTreeFormat(List<TreeNode> nodes) {
if (nodes == null || nodes.isEmpty()) {
return Collections.emptyList();
}
Map<String, TreeNode> idNodeMap = new HashMap<>();
for (TreeNode node : nodes) {
idNodeMap.put(node.getId(), node);
}
List<TreeNode> rootNodes = new ArrayList<>();
for (TreeNode node : nodes) {
TreeNode parentNode = idNodeMap.get(node.getParentId());
if(parentNode != null && !node.getId().equals(node.getParentId())){
if (parentNode.getChildren() == null) {
parentNode.setChildren(new ArrayList<>());
}
parentNode.getChildren().add(node);
}else{
rootNodes.add(node);
}
}
return rootNodes;
}
}
是不是感觉非常熟悉，没错，这正式我们基于JavaScript的代码写来的，基本思想是完全一致的。
然后我们再写个测试类TreeTest：
import com.google.gson.Gson;
import com.google.gson.JsonObject;
import java.util.ArrayList;
import java.util.List;
public class TreeTest {
public static void main(String[] args) {
// 创建测试数据
List<TreeNode> nodes = new ArrayList<>();
nodes.add(new TreeNode("1", null)); // 根节点
nodes.add(new TreeNode("2", "1")); // 1的子节点
nodes.add(new TreeNode("3", "1")); // 1的子节点
nodes.add(new TreeNode("4", "2")); // 2的子节点
nodes.add(new TreeNode("5", "2")); // 2的子节点
nodes.add(new TreeNode("6", "3")); // 3的子节点
nodes.add(new TreeNode("7", null)); // 另一个根节点
nodes.add(new TreeNode("8", "7")); // 7的子节点
nodes.add(new TreeNode("9", "8")); // 8的子节点
nodes.add(new TreeNode("10", "8")); // 8的子节点
// 调用transformToTreeFormat方法转换节点列表为树形结构
List<TreeNode> tree = TreeUtils.transformToTreeFormat(nodes);
System.out.println(new Gson().toJson(tree));
}
}
然后我们在JSON工具中，看下结果：
明显的看到，结果已经是树结构的JSON对象了，是不是很巧妙呢。
在这个Java版本中，我们首先定义了一个TreeNode类来表示树的节点，其中包含id、父节点id和子节点列表。然后，在TreeUtils类的transformToTreeFormat方法中，我们创建了一个映射，将每个节点的id映射到对应的节点对象。接着，我们遍历所有节点，将没有父节点或父节点不是自身的节点添加到根节点列表中，否则将节点添加到其父节点的子节点列表中。最后返回根节点列表。
这种方法的核心思想是利用哈希映射的快速查找特性，避免了递归带来的性能开销。同时，通过两次遍历节点数组，我们可以有效地构建出完整的树形结构。
在实际应用中，我发现这种方法在处理大型数据集时表现出色。与递归方法相比，它的性能更好，且更加稳定。此外，由于它不需要递归调用栈，因此可以处理更深的树形结构，而不会引发栈溢出错误。
当然，这种方法也有一些局限性。例如，它假设节点的id是唯一的，并且父节点id能够唯一确定一个父节点。如果数据不满足这些条件，那么这种方法可能无法正确构建树形结构。此外，如果节点数组中的节点顺序不正确（例如，子节点出现在父节点之前），那么也可能导致构建错误的树形结构。
总的来说，不使用递归来构造树形结构是一种值得尝试的方法。它能够提高性能，避免递归带来的潜在问题。
当然，在实际应用中，我们需要根据数据的特性和需求来选择合适的方法。
希望这篇文章能够对你有所启发，帮助你在编程中更加灵活地处理树形结构数据。
喜欢这篇文章的，可以关注、收藏、分享、点赞哦，欢迎和我一起交流哦。