一维数组转树

方法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)
        }
    })
}

Notice: Undefined variable: ub in /var/www/lordoc/common/function/browserinfo.php on line 232

Notice: Undefined variable: ub in /var/www/lordoc/common/function/browserinfo.php on line 244

Notice: Undefined offset: 1 in /var/www/lordoc/common/function/browserinfo.php on line 248