一维数组转树
方法1:递归
时间复杂度为O(2^n)。
写法一
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: 4 },
]
let result = generateMenuTree(arr, { pId: 'pid', id: 'id' })
let resultStr = JSON.stringify(result, null, 4)
console.log('resultStr=', resultStr)
function generateMenuTree(treeData, props) {
// 把跟节点首先放进数组
const tmpTree = treeData.filter(node => node[props.pId] === 0)
// 递归生成节点及子节点数据
const findChildren = (tree) => {
tree.forEach(node => {
node.childrenDetails = treeData.filter(cNode => cNode[props.pId] === node[props.id])
if (node.childrenDetails) {
findChildren(node.childrenDetails)
}
})
}
findChildren(tmpTree)
return tmpTree
}
写法二
const getChildren = (data, result, pid) => {
for (const item of data) {
if (item.pid === pid) {
const newItem = { ...item, children: [] };
result.push(newItem);
getChildren(data, newItem.children, item.id);
}
}
}
/**
* 转换方法
*/
const arrayToTree = (data, pid) => {
const result = [];
getChildren(data, result, pid)
return result;
}
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: 4 },
]
let result = arrayToTree(arr, 0)
方法2:借助对象的引用
时间复杂度为O(2n)，空间复杂度O(n)。
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: 4 },
]
let result = arrayToTree(arr)
function arrayToTree(items) {
const result = [] // 存放结果集
const itemMap = {} //
// 先转成map存储
for (const item of items) {
itemMap[item.id] = { ...item, children: [] }
}
for (const item of items) {
const id = item.id;
const pid = item.pid;
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:遍历的同时借助对象的引用
时间复杂度为O(n)，空间复杂度O(n)。
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: 4 },
]
let result = arrayToTree(arr)
function arrayToTree(items) {
const result = [] // 存放结果集
const itemMap = {} //
// 先转成map存储
for (const item of items) {
itemMap[item.id] = { ...item, children: [] }
}
for (const item of items) {
const id = item.id;
const pid = item.pid;
const treeItem = itemMap[id];
if (pid === 0) {
result.push(treeItem);
} else {
if (!itemMap[pid]) {
itemMap[pid] = {
children: [],
}
}
itemMap[pid].children.push(treeItem)
}
}
return result;
}
树节点的id生成一维数组
递归
var treeData = [{
"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": [{
"id": 5,
"name": "部门5",
"pid": 4,
"children": []
}]
}]
}
]
}]
var idsList = []
getTreeId(treeData)
console.log('idsList=', idsList)
function getTreeId(arr) {
arr.forEach(item => {
if (!item.children) {
idsList.push(item.id)
} else {
idsList.push(item.id)
getTreeId(item.children)
}
})
}