DFS 解决 Vue 造轮子的 Cascader 的节点查找问题
回复数(0) 浏览数(53)
{{topic.upvote_count || 0}} 编辑 回复

在学 Vue 造轮子的时候看到方方写的递归找树里节点的函数如下,因为时间不够了方方没有优化,一开始我没看懂。。。后来想了会写了个更容易理解的算法

之前的代码

let simple = (children, id) => {
    return children.filter(item => item.id === id)[0]
}
let complex = (children, id) => {
    let noChildren = []
    let hasChildren = []
    console.log(children)
    children.forEach(item => {
        if (item.children) {
            hasChildren.push(item)
        }
        else {
            noChildren.push(item)
        }
    })

    let found = simple(noChildren, id)
    if (found) {
        return found
    }
    else {
        found = simple(hasChildren, id)
        if (found) {
            return found
        }
        else {
            for (let i = 0; i < hasChildren.length; i++) {
                found = complex(hasChildren[i].children, id)
                if (found) {
                    return found
                }
            }
            return undefined
        }
    }
}

const toUpdate = complex(this.source, id)

整理后的代码

注意:因为 this.source 是个数组,而我的算法是根据 root 来写的,root 的子节点都用 children 来存放,所以不要直接传 this.source,而是 {children: this.source}

function findTreeNodeById(root, id) {
    if (!root.children || root.children.length === 0) {
        return undefined
    }
    for (let child of Object.values(root.children)) {
        // Found that object
        if (child.id === id) {
            return child
        }

        // Using DFS to find
        const possibleResult = findTreeNodeById(child, id)
        if (possibleResult) {
            return possibleResult
        }
    }

    return undefined
}

const toUpdate = findTreeNodeById({children: this.source}, id)
{{topic.upvote_count || 0}}

在学 Vue 造轮子的时候看到方方写的递归找树里节点的函数如下,因为时间不够了方方没有优化,一开始我没看懂。。。后来想了会写了个更容易理解的算法

之前的代码

let simple = (children, id) => {
    return children.filter(item => item.id === id)[0]
}
let complex = (children, id) => {
    let noChildren = []
    let hasChildren = []
    console.log(children)
    children.forEach(item => {
        if (item.children) {
            hasChildren.push(item)
        }
        else {
            noChildren.push(item)
        }
    })

    let found = simple(noChildren, id)
    if (found) {
        return found
    }
    else {
        found = simple(hasChildren, id)
        if (found) {
            return found
        }
        else {
            for (let i = 0; i < hasChildren.length; i++) {
                found = complex(hasChildren[i].children, id)
                if (found) {
                    return found
                }
            }
            return undefined
        }
    }
}

const toUpdate = complex(this.source, id)

整理后的代码

注意:因为 this.source 是个数组,而我的算法是根据 root 来写的,root 的子节点都用 children 来存放,所以不要直接传 this.source,而是 {children: this.source}

function findTreeNodeById(root, id) {
    if (!root.children || root.children.length === 0) {
        return undefined
    }
    for (let child of Object.values(root.children)) {
        // Found that object
        if (child.id === id) {
            return child
        }

        // Using DFS to find
        const possibleResult = findTreeNodeById(child, id)
        if (possibleResult) {
            return possibleResult
        }
    }

    return undefined
}

const toUpdate = findTreeNodeById({children: this.source}, id)
53
回复 编辑