[转]js数组和树结构数据相互转换

转自：https://blog.csdn.net/ChuGuoFei/article/details/104434897?utm_medium=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.not_use_machine_learn_pai&depth_1-utm_source=distribute.pc_relevant.none-task-blog-OPENSEARCH-1.not_use_machine_learn_pai

数组转树结构采取递归和非递归两种方式，树结构转扁平化数组采取深度优先遍历（递归和非递归两种方式）和广度优先遍历实现。

let arr = [
            { id: 2, name: '部门B', parentId: 0 },
            { id: 3, name: '部门C', parentId: 1 },
            { id: 1, name: '部门A', parentId: 2 },
            { id: 4, name: '部门D', parentId: 1 },
            { id: 5, name: '部门E', parentId: 2 },
            { id: 6, name: '部门F', parentId: 3 },
            { id: 7, name: '部门G', parentId: 2 },
            { id: 8, name: '部门H', parentId: 4 },
            { id: 9, name: '部门I', parentId: 8 }
        ];

/**
 * 数组转树  非递归求解
 * 利用数组和对象相互引用  时间复杂度O(n)
 * @param {Object} list
 */
function totree(list,parId) {
    let obj = {};
    let result = [];
    //将数组中数据转为键值对结构 (这里的数组和obj会相互引用)
    list.map(el => {
        obj[el.id] = el;
    })
    for(let i=0, len = list.length; i < len; i++) {
        let id = list[i].parentId;
        if(id == parId) {
            result.push(list[i]);
            continue;
        }
        if(obj[id].children) {
            obj[id].children.push(list[i]);
        } else {
            obj[id].children = [list[i]];
        }
    }
    return result;
}

let res1 = totree(arr,0)

console.log('-------数组转树  非递归求解  利用数组和对象相互引用  时间复杂度O(n)-------')
console.log(res1)

/**
 * 数组转树  递归求解
 */
function toTree(list,parId){
    let len = list.length
    function loop(parId){
        let res = [];
        for(let i = 0; i < len; i++){
            let item = list[i]
            if(item.parentId === parId){
                item.children = loop(item.id)
                res.push(item)
            }
        }
        return res
    }
    return loop(parId)
}

let res2 = toTree(arr,0)
console.log('-------数组转树  递归求解  利用数组和对象相互引用  时间复杂度O(n)-------')
console.log(res2)


/**
 * 树转数组扁平化结构   
 * 深度优先遍历  堆栈  后进先出
 */
function deep(node){
    let stack = node,
        data = [];
    while(stack.length != 0){
        let pop = stack.pop();
        data.push({
            id: pop.id,
            name: pop.name,
            parentId: pop.parentId
        })
        let children = pop.children
        if(children){
            for(let i = children.length-1; i >=0; i--){
                stack.push(children[i])
            }
        }
    }
    return data
}

console.log('-------树转数组扁平化结构 深度优先遍历 堆栈 后进先出-------')
console.log(deep(JSON.parse(JSON.stringify(res1))))



/**
 * 树转数组扁平化结构   
 * 深度优先遍历  递归
 */
function deepTraversal(data) {
    const result = [];
    data.forEach(item => {
        const loop = data => {
            result.push({
                id: data.id,
                name: data.name,
                parentId: data.parentId
            });
            let child = data.children
            if(child){
                for(let i = 0; i < child.length; i++){
                    loop(child[i])
                }
            }
        }
        loop(item);
    })
    return result;
}

console.log('-------树转数组扁平化结构 深度优先遍历 递归-------')
console.log(deepTraversal(JSON.parse(JSON.stringify(res1))))

/**
 * 广度优先
 * 队列  先进先出
 */
function wideTraversal(node){
    let stack = node,
        data = [];
    while(stack.length != 0){
        let shift = stack.shift();
        data.push({
            id: shift.id,
            name: shift.name,
            parentId: shift.parentId
        })
        let children = shift.children
        if(children){
            for(let i = 0; i < children.length; i++){
                stack.push(children[i])
            }
        }
    }
    return data
}

console.log('-------树转数组扁平化结构 广度优先 队列 先进先出-------')
console.log(wideTraversal(JSON.parse(JSON.stringify(res1))))