js 算法- 广度优先算法

[wolichuang]

广度优先算法

实现数组与树结构的相互转换

let data = [
  { id: 0, parentId: null, name: '生物' },
  { id: 1, parentId: 0, name: '动物' },
  { id: 2, parentId: 0, name: '植物' },
  { id: 3, parentId: 0, name: '微生物' },
  { id: 4, parentId: 1, name: '哺乳动物' },
  { id: 5, parentId: 1, name: '卵生动物' },
  { id: 6, parentId: 2, name: '种子植物' },
  { id: 7, parentId: 2, name: '蕨类植物' },
  { id: 8, parentId: 4, name: '大象' },
  { id: 9, parentId: 4, name: '海豚' },
  { id: 10, parentId: 4, name: '猩猩' },
  { id: 11, parentId: 5, name: '蟒蛇' },
  { id: 12, parentId: 5, name: '麻雀' }
]

let node = {
    "id": 0,
    "parentId": null,
    "name": "生物",
    "children": [{
        "id": 1,
        "parentId": 0,
        "name": "动物",
        "children": [{
            "id": 4,
            "parentId": 1,
            "name": "哺乳动物",
            "children": [{
                "id": 8,
                "parentId": 4,
                "name": "大象"
            }, {
                "id": 9,
                "parentId": 4,
                "name": "海豚"
            }, {
                "id": 10,
                "parentId": 4,
                "name": "猩猩"
            }]
        }, {
            "id": 5,
            "parentId": 1,
            "name": "卵生动物",
            "children": [{
                "id": 11,
                "parentId": 5,
                "name": "蟒蛇"
            }, {
                "id": 12,
                "parentId": 5,
                "name": "麻雀"
            }]
        }]
    }, {
        "id": 2,
        "parentId": 0,
        "name": "植物",
        "children": [{
            "id": 6,
            "parentId": 2,
            "name": "种子植物"
        }, {
            "id": 7,
            "parentId": 2,
            "name": "蕨类植物"
        }]
    }, {
        "id": 3,
        "parentId": 0,
        "name": "微生物"
    }]
}

转换成树

function transTree(data) {
    let result = []
    let map = {}
    if (!Array.isArray(data)) {//验证data是不是数组类型
        return []
    }
    data.forEach(item => {//建立每个数组元素id和该对象的关系
        map[item.id] = item //这里可以理解为浅拷贝，共享引用
    })
    data.forEach(item => {
        let parent = map[item.parentId] //找到data中每一项item的爸爸
        if (parent) {//说明元素有爸爸，把元素放在爸爸的children下面
            (parent.children || (parent.children = [])).push(item)
        } else {//说明元素没有爸爸，是根节点，把节点push到最终结果中
            result.push(item) //item是对象的引用
        }
    })
    return result //数组里的对象和data是共享的
}
console.log(JSON.stringify(transTree(data)))

转换成数组

function transArr(node) {
    let queue= [node]
    let data = [] //返回的数组结构
    while (queue.length !== 0) { //当队列为空时就跳出循环
        let item = queue.shift() //取出队列中第一个元素
        data.push({
            id: item.id,
            parentId: item.parentId,
            name: item.name            
        })
        let children = item.children // 取出该节点的孩子
        if (children) { 
            for (let i = 0; i < children.length; i++) {
                queue.push(children[i]) //将子节点加入到队列尾部
            }
        }
    }
    return data
}
console.log(transArr(node))