构建树的三种方案

在业务中经常会有这样的场景，数据表存储父节点ID,前台需要构建成

{
    "name": "",
    "id": "",
    "value": "",
    "children": [
        {}
    ]
}

这样的数据格式，以便前台框架如ant design等可以展示一颗树，以组织架构为例，列出构建树的三种方法

方法一递归

let res = []
let generateTree = (list, pid, resp) => {
    let curLevelList = list.filter(x => x.pid === pid)
    resp = []
    if(curLevelList.length === 0) {
        return 
    }
    curLevelList.forEach(x => {
        let node = new TreeNode(x.id, x.pid, [])
        node.childen = generateTree(list, node.id)
        resp.push(node)
    })
    return resp 
}

res = generateTree(arr, '0', [])

方法二双层for循环

let generateTreeFor = (list, pid) => {
    let res = []
    list.forEach(x => {
        if(x.pid === pid) {
            res.push(x)
        }
        list.forEach(y => {
            if(y.pid === x.id) {
                x.children.push(y)
            }
        })
    })
    return res 
}
let res1 = generateTreeFor(arr, '0')

递归和for循环其实都有问题，比如组织架构中已经有几万个节点，这时用递归很占用内存，但是用双层for循环时间效率又比较低，可以优化一下，用一层map,然后单次遍历，每次遍历找到当前节点的父节点

方法三 map

let m = new Map()
let res = []
list.forEach(x => {
    m.set(x.id, new TreeNode(x.id, x.val, x.pid, []))
})
for(const [key, value] of m) {
    if(value.pid === pid) {
        res.push(value)
    }
    if(m.has(pid)) {
        m.get(pid).children.push(value)
    }
}
return res 

定义测试的树节点结构和遍历方法测试即可

class Node {
    constructor(id, val, pid) {
        this.id = id 
        this.val = val
        this.pid = pid 
    }
}

class TreeNode {
    constructor(id, val, pid, children) {
        this.id = id 
        this.val = val
        this.pid = pid 
        this.children = []
    }
}

function TraverseTree(tree) {
    if(!tree) {
        return 
    }
    console.log(tree.val)
    if(tree.children) {
        tree.children.forEach(x => {
            TraverseTree(x)
        })
    }
}

构建树的三种方案

业务积累

CATALOG