从树中快速找到一个已渲染节点

提示

开发中经常会遇到侧边栏、文件目录等场景，需要操作树形结构的数据

背景

最近遇到个树形表单的需求，根据用户操作，需要更新节点数据，数据结构如下：

const treeData = [{
        node: '1',
        children: [{
                node: '1-1',
                children: [{
                    node: '1-1-1',
                    children: []
                }],
            },
            {
                node: '1-2',
                children: [{
                    node: '1-2-1',
                    children: []
                }],
            },
        ],
    },
    {
        node: '3',
        children: [{
                node: '3-1',
                children: [{
                    node: '3-1-1',
                    children: []
                }],
            },
            {
                node: '3-2',
                children: [{
                    node: '3-2-1',
                    children: [{
                            node: '3-2-1-1',
                            children: []
                        },
                        {
                            node: '3-2-1-2',
                            children: []
                        },
                        {
                            node: '3-2-1-3',
                            children: []
                        },
                    ],
                }, ],
            },
        ],
    },
]

深度优先遍历没毛病？

更新节点数据，势必会涉及到查找操作，一般会用递归的方式，也就是深度优先遍历的方式去寻找目标节点，算法复杂度在 O(n) ，看起来好像可以接受，但是，如果目标节点在树的最右侧的最后一级的最右边，那将遍历整棵树所有的节点才能找到， 这个时候的 n ，将是整棵树的节点数, 为了查找一个节点去遍历整棵树，显然时不划算的 。通常情况下在操作节点时，渲染的时候往往已经经过一次dfs了，是不是在遍历的过程中可以记录一下操作元素的路径，后面查找数据时，通过路径找目标节点，而不用给整棵树做递归呢？

function findNode(list, target) {
    let node

    function dfs(list) {
        for (let i = 0; i < list.length; i++) {
            const cur = list[i]
            if (cur.node === target) {
                node = cur
                return
            } else {
                cur.children && dfs(cur.children)
            }
        }
    }
    dfs(list)
    return node
}

indexPath

当然可以，通过记录从根节点到当前操作节点每一层的索引就行了，拼接成一条 indexPath(索引路径集合) 。这里为了方便测试我直接把 indexPath 存在了源数据中，一般情况下遍历时应该是存在闭包中，然后通过点击函数获取到的; 要注意， indexPath 在存储的时候用的是字符串，后面用的时候最好转成数组

// 递归向每个节点都添加上由索引组成的path
function insertPath(list, index) {
    for (let i = 0; i < list.length; i++) {
        const curNode = list[i]
        const indexPath = index ? String(index).concat("-" + i) : i
        list[i].path = indexPath
        if (curNode.children) {
            insertPath(curNode.children, indexPath)
        }
    }
}
insertPath(treeData)

根据索引path查询

拿到 indexPath 后，就可以开始查了，直接遍历(从根节点开始)，每次循环暂存那一层的父节点，同时又通过遍历拿到的索引值，更新父节点，直到目标节点。

const indexList = [1, 2, 0, 2]
// 通过元素所在层级的索引找到该元素
function findNodeByIndexPath(indexList) {
    let obj = null
    indexList.forEach((item) => {
        // 第一次进来
        if (!obj) {
            obj = treeData[item]
        } else {
            // 更新某一层的父级，直到自己
            obj = obj.children[item]
        }
    })
    return obj
}

总结

根据索引path查询的方式，其实算法复杂度依然是 O(n) ，好像并没有什么卵用？别急~ 可以看下图对比一下 n 就知道了， 树的最大深度 和 树的节点数 意义可差多了，这俩可完全不是一个数量级的啊，尤其是在树特别深和大批量节点的情况下，这个算法除了速度上有绝对优势，而且还免去了爆栈的风险，一举两得！

算法	indexPath	dfs
n大小	0 < n <=树的最大深度	0 < n <=树的节点数