广度优先和深度优先 #9

func-star · 2018-06-26T08:08:33Z

最近在项目中遇到的场景，在这分享一下。

通常来讲，对一个树形数组做处理，特别是层级未知的数据结构，第一想法肯定是遍历。在不考虑性能的情况下，基本上都能解决。

下面来个例子：
数据结构：

let data = [{
        id: 1,
        name: 'a',
        children: [
            { id: 11, name: 'aa' },
            {
                id: 12,
                name: 'ab',
                children: [
                    { id: 121, name: 'aba' },
                    { id: 122, name: 'abb' }
                ]
            },
            { id: 13, name: 'ac' }
        ]
    },
    {
        id: 2,
        name: 'b',
        children: [
            { id: 21, name: 'ba' },
            { id: 22, name: 'bb' }
        ]
    },
    { id: 3, name: 'c' }
];

现在我们先用大家熟悉的递归来实现一遍。

let test = (() => {
    let res = '';
    return inner = (data, id) => {
        if (!data || data.length === 0) {
            return
        }

        data.forEach(v => {
            if (v.id === id) {
                res = v.name
            }

            if (v.children && v.children.length > 0) {
                inner(v.children, id)
            }
        })
        return res;
    }
})()

let val = test(data, 123);
console.log(val);

实现完成之后我们会思考怎么才能把它的性能提高，特别是在树层级特别深的场景下，递归的性能还是比较难以接受的。

优化方案：

针对二叉树遍历，有深度优先和广度优先两种通用解决方案，我们可以根据数据结构的广度和深度选择最优的解决方案。虽然在前端日常开发中，很少会用到算法，但是这种性能优化的方案还是可以借鉴的。

广度优先

根据广度优先的思路来看一下代码实现。

let test2 = (() => {
    let res = '';
    return inner = (data, id) => {
        if (!data || data.length === 0) {
            return
        }
        let stark = []; // 初始化一个数据栈
        // 将第一层数据压入栈
        data.forEach(v => {
            stark.push(v);
        })

        while (stark.length > 0) {
            let item = stark.shift();
            if (item.id === id) {
                res = item.name;
            }
            if (item.children && item.children.length > 0) {
                stark = stark.concat(item.children)
            }
        }
        return res;
    }
})()

let val = test2(data, 123);
console.log(val);

深度优先

根据深度优先的思路来看一下代码实现。

let test3 = (() => {
    let res = '';
    return inner = (data, id) => {
        if (!data || data.length === 0) {
            return
        }

        let stark = []; // 初始化一个数据栈
        // 将第一层数据压入栈
        data.forEach(v => {
            stark.push(v);
        })

        while (stark.length > 0) {
            let item = stark.shift();
            if (item.id === id) {
                res = item.name;
            }
            if (item.children && item.children.length > 0) {
                stark = item.children.concat(stark);
            }
        }
        return res;
    }
})()

let val = test3(data, 123);
console.log(val);

func-star added the js label Jun 26, 2018

func-star removed the js label Oct 8, 2018

func-star changed the title ~~树形数组递归优化算法广度优化和深度优化~~ 树形数组递归优化算法 Oct 25, 2018

func-star changed the title ~~树形数组递归优化算法~~ 广度优先和深度优先 Feb 21, 2019

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

广度优先和深度优先 #9

广度优先和深度优先 #9

func-star commented Jun 26, 2018 •

edited

Loading

广度优先和深度优先 #9

广度优先和深度优先 #9

Comments

func-star commented Jun 26, 2018 • edited Loading

优化方案：

广度优先

深度优先

func-star commented Jun 26, 2018 •

edited

Loading