JavaScript树形数组扁平化/以及扁平化数组还原到树形数组

数组扁平化/以及扁平化数组还原到树形数组"/>

JavaScript树形数组扁平化/以及扁平化数组还原到树形数组

前端数据方面的需求，一个是将树形数组扁平化，另外一个是将扁平化的数组输出为树形数组
，下面为两种相互转换的实现方式：
树形数组为：

let tree = [{"id": 1,"name": "1","pid": 0,"children": [{"id": 2,"name": "2","pid": 1,"children": []},{"id": 3,"name": "3","pid": 1,"children": [{"id": 4,"name": "4","pid": 3,"children": []}]}]}
]

打平后的数组为：

let arr = [{id: 1, name: '1', pid: 0},{id: 2, name: '2', pid: 1},{id: 3, name: '3', pid: 1},{id: 4, name: '4', pid: 3},{id: 5, name: '5', pid: 3},
]

1.首先是树形数组扁平化

// reduce实现
function treeToArray(tree) {return tree.reduce((res, item) => {const { children, ...i } = itemreturn res.concat(i, children && children.length ? treeToArray(children) : [])}, [])
}

2.扁平化数组转树tree

// 先把数据转成Map去存储，之后遍历的同时借助对象的引用，直接从Map找对应的数据做存储
function arrayToTree(items) {const result = [];   // 存放结果集const itemMap = {};  // for (const item of items) {const id = item.id;const pid = item.pid;if (!itemMap[id]) {itemMap[id] = {children: [],}}itemMap[id] = {...item,children: itemMap[id]['children']}const treeItem =  itemMap[id];if (pid === 0) {result.push(treeItem);} else {if (!itemMap[pid]) {itemMap[pid] = {children: [],}}itemMap[pid].children.push(treeItem)}}return result;
}

3.特殊情况1–每个数组的字段名key值不同

以下方法基于生成器函数：

//定义了一个 flattenTreeGenerator
生成器函数，接受一个节点和一个包含子节点键名的数组作为参数，返回一个生成器对象。当该生成器被迭代时，它会按照深度优先的顺序输出节点，直到遍历完整个树形结构。
在 flattenTree 方法中，通过调用 flattenTreeGenerator 生成器函数来扁平化树形结构，并将结果保存到 flattenedTree 数组中。加上 * 是将函数定义为一个生成器函数(generator function)。
生成器函数是一种特殊的函数，它可以在运行时暂停执行，并且可以在任何时候恢复执行，生成器函数使用 yield 关键字来控制它们的执行流程，可以通过next() 方法来让它们继续执行下去。
当生成器函数运行结束时，会自动返回一个迭代器(iterator)，用于遍历它的输出值。
在扁平化树形结构的过程中，需要递归遍历树的每一个节点，生成器函数的暂停和恢复执行的特性，使得可以用更简单的方式实 现树形结构的遍历。
在本例中，每次调用 yield 关键字时，会将当前节点的值输出，然后暂停执行，等待下一次 next() 方法的调用。
需要注意的是，在使用生成器函数时，需要使用 yield* 关键字来遍历子节点。yield*关键字可以将控制权交给子生成器函数，使得它们可以递归遍历整个树形结构。

以下方法也可以扁平化key值相同的树形数组（基于Vue2）
方法1

    *flattenTreeGenerator(node, keys) {yield node;for (const key of keys) {if (Array.isArray(node[key])) {for (const child of node[key]) {yield* this.flattenTreeGenerator(child, keys);}}}},flattenTree(arr, keys) {const result = [];for (const node of arr) {for (const item of this.flattenTreeGenerator(node, keys)) {result.push(item);}}return result;},

注释版本

/*** 生成器函数，用于扁平化树形结构* @param {Object} node - 当前节点* @param {Array} keys - 需要扁平化的属性列表*/
function* flattenTreeGenerator(node, keys) {// 生成器函数，首先 yield 当前节点yield node;// 遍历需要扁平化的属性for (const key of keys) {// 如果当前节点有对应属性且值为数组，则递归遍历数组中的子节点if (Array.isArray(node[key])) {for (const child of node[key]) {yield* flattenTreeGenerator(child, keys);}}}
}/*** 扁平化树形结构* @param {Array} arr - 原始树形结构* @param {Array} keys - 需要扁平化的属性列表* @returns {Array} - 扁平化后的结果*/
function flattenTree(arr, keys) {// 初始化结果数组const result = [];// 遍历原始树形结构中的每个节点for (const node of arr) {// 使用生成器函数扁平化当前节点，并将结果 push 到结果数组中for (const item of flattenTreeGenerator(node, keys)) {result.push(item);}}// 返回扁平化后的结果数组return result;
}

调用

      let treeDataSource = [{id: "1",children: [{id: "11",name: "aa_sub1",desc: "这是一个描述_sub1",parentId: "1",},],},{id: "2",children: [{ id: "22", parentId: "2" },{id: "23",parentId: "2",childrens1: [{id: "233",parentId: "23",childrenss2: [{ id: "2333", parentId: "233" }],},],},],},];const keys = ["children",'childrens1','childrenss2'];const flattened = this.flattenTree(treeDataSource, keys);

方法2–正常递归
调用方法和生成器递归一直，入参为：数组，key值

    flattenTree(data, keys) {// 定义函数，传入两个参数，第一个是需要扁平化的树形数组，第二个是需要扁平化的关键字const result = []; // 定义一个空数组，用来存储扁平化后的结果function traverse(node) {// 定义一个名为 traverse 的函数，用于遍历节点result.push(node); // 将当前节点添加到结果数组中for (const key of keys) {// 遍历传入的关键字数组if (Array.isArray(node[key])) {// 如果当前节点的关键字对应的值是一个数组for (const child of node[key]) {// 遍历该数组中的子节点traverse(child); // 递归调用 traverse 函数，继续遍历子节点}}}}for (const node of data) {// 遍历原始树形数组中的每个节点traverse(node); // 对每个节点递归调用 traverse 函数，遍历所有子节点}return result; // 返回扁平化后的结果数组},

3.特殊情况2–外层是对象

     tree: {id: 1,name: "A",layer: [{id: 2,name: "B",children: [{id: 4,name: "D",items: [{id: 6,name: "F",categories: [{id: 8,name: "H",},],},{id: 7,name: "G",},],},{id: 5,name: "E",},],},{id: 3,name: "C",},],},flattenedTree: [],

  methods: {// 方法1：生成器函数*flattenTreeGenerator(node, keys) {yield node;for (const key of keys) {if (Array.isArray(node[key])) {for (const child of node[key]) {yield* this.flattenTreeGenerator(child, keys);}}}},// 传入tree和每层数组的key名flattenTree() {this.flattenedTree = [...this.flattenTreeGenerator(this.tree, ["layer", "children", "items"]),];console.log(this.flattenedTree);},//-------------------------------------------//方法2：正常递归----flattenTree 方法是一个递归函数。flattenTree(node, keys) {const result = [node];keys.forEach((key) => {if (Array.isArray(node[key])) {result.push(...node[key].flatMap((child) => this.flattenTree(child, keys)));}});return result;},const keys = ["layer", "childre", "items"]const flatArr = this.flattenTree(this.tree, keys);},

还原到树形数组

    // 还原树形结构restoreTree(arr, idKey = "id", parentIdKey = "parentId") {const map = {};const roots = [];// 将节点按照 id 存储到一个对象中for (const node of arr) {map[node[idKey]] = { ...node, children: [] };}// 遍历每个节点，将其添加到其父节点的 children 属性中for (const node of arr) {const parent = map[node[parentIdKey]];if (parent) {parent.children.push(map[node[idKey]]);} else {roots.push(map[node[idKey]]);}}return roots;},

扁平化—>还原

<template><div><button @click="GeneratorFlat">生成器方法</button><button @click="openAll">普通递归</button></div>
</template>
<script>
export default {data() {return {};},methods: {// 生成器方法扁平化GeneratorFlat() {let treeDataSource = [{id: "1",children: [{id: "11",name: "aa_sub1",desc: "这是一个描述_sub1",parentId: "1",},],},{id: "2",children: [{ id: "22", parentId: "2" },{id: "23",parentId: "2",childrens1: [{id: "233",parentId: "23",childrenss2: [{ id: "2333", parentId: "233" }],},],},],},];const keys = ["children", "childrens1", "childrenss2"];const flattened = this.flattenTree(treeDataSource, keys);console.log(flattened, "生成器递归结果=================");const restoredTree = this.restoreTree(flattened);console.log(restoredTree, "还原后的树=================");},// 普通递归openAll() {let treeDataSource = [{id: "1",children: [{id: "11",name: "aa_sub1",desc: "这是一个描述_sub1",parentId: "1",},],},{id: "2",children: [{ id: "22", parentId: "2" },{id: "23",parentId: "2",childrens1: [{id: "233",parentId: "23",childrenss2: [{ id: "2333", parentId: "233" }],},],},],},];const keys = ["children", "childrens1", "childrenss2"];const flatteneds = this.flattenS(treeDataSource, keys);console.log(flatteneds, "普通递归结果=================");},//正常递归flattenS(data, keys) {// 定义函数，传入两个参数，第一个是需要扁平化的树形数组，第二个是需要扁平化的关键字const result = []; // 定义一个空数组，用来存储扁平化后的结果function traverse(node) {// 定义一个名为 traverse 的函数，用于遍历节点result.push(node); // 将当前节点添加到结果数组中for (const key of keys) {// 遍历传入的关键字数组if (Array.isArray(node[key])) {// 如果当前节点的关键字对应的值是一个数组for (const child of node[key]) {// 遍历该数组中的子节点traverse(child); // 递归调用 traverse 函数，继续遍历子节点}}}}for (const node of data) {// 遍历原始树形数组中的每个节点traverse(node); // 对每个节点递归调用 traverse 函数，遍历所有子节点}return result; // 返回扁平化后的结果数组},// ---------------------------------------------------------//生成器递归*flattenTreeGenerator(node, keys) {yield node;for (const key of keys) {if (Array.isArray(node[key])) {for (const child of node[key]) {yield* this.flattenTreeGenerator(child, keys);}}}},flattenTree(arr, keys) {const result = [];for (const node of arr) {for (const item of this.flattenTreeGenerator(node, keys)) {result.push(item);}}return result;},
// --------------------------------------------------------------------// 还原树形结构restoreTree(arr, idKey = "id", parentIdKey = "parentId") {const map = {};const roots = [];// 将节点按照 id 存储到一个对象中for (const node of arr) {map[node[idKey]] = { ...node, children: [] };}// 遍历每个节点，将其添加到其父节点的 children 属性中for (const node of arr) {const parent = map[node[parentIdKey]];if (parent) {parent.children.push(map[node[idKey]]);} else {roots.push(map[node[idKey]]);}}return roots;},},
};
</script>