扁平数组转为树结构
题目描述:
给定以下数据格式的扁平数组:
const flatArray = [
{ id: 1, parentId: null, name: 'root1' },
{ id: 2, parentId: 1, name: 'child1' },
{ id: 3, parentId: 1, name: 'child2' },
{ id: 4, parentId: 2, name: 'grandchild1' },
{ id: 5, parentId: 3, name: 'grandchild2' },
];
你需要将其转换为以下树状结构:
const tree = [
{
"id": 1,
"parentId": null,
"name": "root1",
"children": [
{
"id": 2,
"parentId": 1,
"name": "child1",
"children": [
{
"id": 4,
"parentId": 2,
"name": "grandchild1",
"children": []
}
]
},
{
"id": 3,
"parentId": 1,
"name": "child2",
"children": [
{
"id": 5,
"parentId": 3,
"name": "grandchild2",
"children": []
}
]
}
]
}
];
请编写一个名为 flatArrayToTree
的函数,接受上述类型的扁平数组作为参数,并返回相应的树状结构数组。
方案一:使用Map和递归
function flatArrayToTree(flatArray) {
// 创建一个映射,方便通过id查找节点
const map = new Map();
flatArray.forEach(item => {
map.set(item.id, { ...item, children: [] });
});
// 定义一个递归函数,用于构建每个节点的子树
function buildTree(node) {
flatArray.forEach(item => {
if (item.parentId === node.id) {
const childNode = map.get(item.id);
// 递归构建子树,并添加到当前节点的children中
node.children.push(buildTree(childNode));
}
});
return node;
}
// 过滤出根节点并递归构建整棵树
return flatArray
.filter(item => item.parentId === null)
.map(rootNode => buildTree(map.get(rootNode.id)));
}
const tree = flatArrayToTree(flatArray);
方案一解释
首先,我们创建一个 Map
来存储每个节点及其子节点列表。
接着定义一个递归函数 buildTree
用于构建父子关系。遍历扁平数组时,对于每个节点,将其添加到 Map
中并初始化其 children
属性为空数组。对于有 parentId
的节点,将其添加到相应父节点的 children
数组中。
最后从 Map
中提取 parentId
为 null
的节点形成结果数组。
方案二:使用对象作为索引和循环
function flatArrayToTree(flatData) {
const result = [];
const map = {};
// 先构建一个id映射表
flatData.forEach(item => {
map[item.id] = { ...item, children: [] };
});
// 然后根据parentId将子节点添加到父节点的children属性下
flatData.forEach(item => {
if (item.parentId !== null) {
map[item.parentId].children.push(map[item.id]);
} else {
result.push(map[item.id]);
}
});
return result;
}
const tree = flatArrayToTree(flatArray);
方案二解释
首先遍历扁平数组,创建一个键值对形式的哈希表,键是每个元素的 id
,值是该元素本身。这样我们可以快速通过 id
找到对应的节点。
再次遍历扁平数组,对于每个元素,检查其 parentId
是否存在于哈希表中。如果存在,说明找到了其父节点,将当前元素添加到其父节点的 children
数组中。若不存在 parentId
(即为根节点),则直接添加到结果数组中。
最终得到的结果数组就是所求的树形结构。
最深层级
在构建树结构的时候,如果需要记录最深层级,应该怎么做呢?下面是可以记录最深层级的方案:
function flatArrayToTree(flatData) {
let maxDepth = 0;
const result = [];
const map = {};
// 先构建一个id映射表
flatData.forEach(item => {
map[item.id] = { ...item, children: [], depth: 0 };
});
// 然后根据parentId将子节点添加到父节点的children属性下,并计算深度
flatData.forEach(item => {
if (item.parentId !== null) {
const parent = map[item.parentId];
parent.children.push(map[item.id]);
// 更新当前节点及其父节点的深度
let currentDepth = parent.depth + 1;
map[item.id].depth = currentDepth;
// 更新最大深度
maxDepth = Math.max(maxDepth, currentDepth);
} else {
result.push(map[item.id]);
}
});
return { tree: result, maxDepth };
}
const { tree, maxDepth } = flatArrayToTree(flatArray);
console.log('Tree:', tree);
console.log('Max Depth:', maxDepth);
增加 maxDepth
变量记录最大深度,在每次将子节点添加到父节点的 children
属性下时,记录层级,计算深度。
树结构转扁平数组
以上是扁平数组转为树结构的情况,下面来看针对已有的树形结构,将其转换回扁平数组的情况。
实现
function treeToArray(treeNodes) {
let result = [];
//递归函数 traverse,用于处理单个节点
function traverse(node) {
const newNode = { ...node };
delete newNode.children;
// 将没有子节点的新节点添加到结果数组中
result.push(newNode);
// 如果当前节点包含 children 属性(即有子节点)
if (node.children) {
node.children.forEach(traverse);
}
}
treeNodes.forEach(traverse);
return result;
}
const flatArray = treeToArray(tree);
解释
首先定义了一个 treeToArray
函数,该函数内部定义了一个名为 traverse
的递归函数,用于遍历树形结构的每一个节点并将节点添加到扁平数组中。
然后遍历输入的树形结构,对每个节点调用 traverse
函数。在 traverse
函数内部,如果当前节点有子节点,则对其每个子节点进行同样的遍历操作。
最后返回扁平数组。
总结
在解决扁平数组与树结构之间的转换问题时,关键在于识别父子关系并通过建立索引或映射结构进行层次遍历,以实现数据的转换。
在实际业务中,扁平数组与树结构的转化,常见在目录树组件,级联选择组件等情况。
原文链接:https://juejin.cn/post/7354632375446126619 作者:FEWY