[面试题] 表转树、树转表

956 阅读2分钟

这篇文章主要是整理下“表、树互转”这个日常开发中常遇到的问题的解决方案。 我看到这个题想到的解决方法比较简单粗暴,只是解决了问题而已。后面看了其他大神的实现觉得我的代码惨不忍睹啊。在此主要是整理下搜罗到的各种实现方式,方便以后学习查看,后面会慢慢补充。

表转树: 把从数据库里查到的,数组结构的数据,转为树形结构的数据

树转表:把树形结构的数据,转为可以存入数据库的,数组结构的数据

// 表数据示例
let tableData = [
    {id: '1', pid: null, ...},
    {id: '1-1', pid: '1', ...},
    ...
]

// 树形结构数据示例
let treeData = [
    {
        id: '1',
        pid: null,
        ... // 其他节点属性
        children: [
            {
                id: '1-1', pid: '1', ...,
                children: [
                    {
                        id: '1-1-1', pid: '1-1', ...,
                    },
                    ...
                ]
            },
            {
                id: '1-2', pid: '1', ...
            }
        ]
    },
    ...
]

1. 树转表


function table2tree (data) {
    if (!Array.isArray(data) || data.length === 0) {
        return
    }
    
    let nodeMap = new Map()
    data.forEach(item => {
        nodeMap.set(item.id, {...item})
    })
    
    let result = []

    data.forEach(item => {
        let node = nodeMap.get(item.id)
        let pnode = nodeMap.get(item.pid)
        if (pnode) {
            pnode.children = pnode.children || []
            pnode.children.push(node)
            nodeMap.set(item.pid, pnode)
        } else {
            result.push(node)
        }
    })

    return result
}

店长推荐

function table2tree (tds = []) {
    let result = []
    let map = new Map()
    let rest = [...tds]
    
    do {
        let item = {...rest.shift()}
        map.set(item.id, item)
        let pnode = map.get(item.pid)
        if (item.pid === null) { // 已知根结点的pid值
            result.push(item)
        } else if (map.size === tds.length && pnode === undefined) { // 根结点pid值不确定时
            result.push(item)
        } else if (pnode) {
            (pnode.children || (pnode.children = [])).push(item)
        } else {
            rest.push(item)
        }
    } while (rest.length)
    
    return result
}

2. 表转树

// 表转树
function tree2table (tree = []) {
    let result = []
    tree.forEach(node => getItemsFromNode(node))
    
    function getItemsFromNode (node) {
        let {children, ...copy} = node
        result.push(copy)
        if (children && children.length > 0) {
            children.forEach(child => getItemsFromNode(child))
        }
    }
    
    return result
}

function tree2table (tree = [], table = []) {
    tree.forEach(({children, ...props}) => {
        table.push(props)
        children && children.length > 0 && tree2table(children, table)
    })
    
    return table
}

店长推荐

function tree2table (tree = []) {
    return tree.reduce(
        (accumulator, {children, ...props}) => [...accumulator, props, ...tree2table(children)],
        []
    )
}

3. 测试代码

tableData = [
    {id: '1', pid: null, label: '1'},
    {id: '1-1', pid: '1', label: '1-1'},
    {id: '1-1-1', pid: '1-1', label: '1-1-1'},
    {id: '1-2', pid: '1', label: '1-2'},
    {id: '2', pid: null, label: '2'},
    {id: '2-1', pid: '2', label: '2-1'},
    {id: '2-2', pid: '2', label: '2-2'}
]


tree1 = table2tree(tableData)
table1 = tree2table(tree1)

treeData = [
    {
        id: '1', pid: null, label: '1',
        children: [
            {
                id: '1-1', pid: '1', label: '1-1',
                children: [
                    {
                        id: '1-1-1', pid: '1-1', label: '1-1-1',
                    }
                ]
            },
            {
                id: '1-2', pid: '1', label: '1-2'
            }
        ]
    },
    {
        id: '2', pid: null, label: '2',
        children: [
            {
                id: '2-1', pid: '2', label: '2-1'
            },
            {
                id: '2-2', pid: '2', label: '2-2'
            }
        ]
    }
]

table2 = tree2table(treeData)
tree2 = table2tree(table2)

参考资料: