数据结构相关

数组转树形

详情

type NodeType = {
    id:string
    name:string
    pid:string
}

type TreeNodeType = NodeType&{
children?:TreeNodeType[]
}

function listToTree(arr:NodeType[]):TreeNodeType[]{
    let arrSet = new Map()
    let tree = TreeNodeType[]
    // let root 
    arr.forEach(item=>{
        let node = {...item}
        arrSet.set(item.id,node)
        const pNode = arrSet.get(node.pid)
        if(pNode){
            if(!pNode?.children){
                pNode.children = []
            }
            pNode.children.push(node)
        }
        if(!node.pid && node.pid!==0){
            tree.push(node)
        }
    })
    return tree
}

树形转数组

bfs(广度优先遍历)

详情

type NodeType = {
    id:string
    name:string
    pid:string
}

type TreeNodeType = NodeType&{
    children?:TreeNodeType[]
}

function flatBFS(tree:TreeNodeType[]):NodeType[]{
    let nodeToParent:Map<NodeType,NodeType> = new Map()
    let queue:NodeType = []
    let arr:NodeType[] = []
    tree.forEach(node=>queue.unshift(node))

    while(queue.length>0){
        const curNode = queue.pop()
        if(!curNode) break
        const {id,name,children = []} = curNode
        const pNode = nodeToParent.get(curNode)
        let node = {id,name,pid:pNode.id}
        arr.push(node)

        if(children.length){
            children.forEach(node=>{
                nodeToParent.set(node,curNode)
                queue.unshift(node)
            })
        }
    }
    return arr
}

dfs(深度优先遍历)

详情

type NodeType = {
    id:string
    name:string
    pid:string
}

type TreeNodeType = NodeType&{
    children?:TreeNodeType[]
}

function flatDFS(tree: TreeNodeType[]): NodeType[] {
    const nodeToParent = new Map<TreeNodeType, TreeNodeType | undefined>()
    const stack: TreeNodeType[] = []
    const arr: NodeType[] = []

    // 为了保持根节点从左到右的顺序，这里先倒序入栈
    for (let i = tree.length - 1; i >= 0; i--) {
        const node = tree[i]
        nodeToParent.set(node, undefined)
        stack.push(node)
    }

    while (stack.length > 0) {
        const curNode = stack.pop()
        if (!curNode) {
            break
        }

        const { id, name, children = [] } = curNode
        const pNode = nodeToParent.get(curNode)

        arr.push({
            id,
            name,
            // 根节点没有父节点，这里用空字符串占位
            pid: pNode ? pNode.id : ''
        })

        // 栈是后进先出，所以子节点也要倒序入栈，才能保持从左到右的 DFS 顺序
        for (let i = children.length - 1; i >= 0; i--) {
            const child = children[i]
            nodeToParent.set(child, curNode)
            stack.push(child)
        }
    }

    return arr
}