首页 > 其他分享 >深度优先遍历和广度优先遍历实现

深度优先遍历和广度优先遍历实现

时间:2022-11-28 23:55:26浏览次数:36  
标签:优先 遍历 arr label 广度 null children

深度优先遍历

 从根节点开始,沿着树的深度遍历树的节点,尽可能深的搜索树的分支。沿着一条可能的路径一直往下走,深入到不能深入为止。【可以纵向优先搜索】

 

 遍历结果是: 1->2->4->8->5->3->6->7
广度优先遍历

从根节点开始,沿着树的宽度遍历树的节点。横向一层(level)的去遍历。

 

遍历结果是:1->2->3->4->5->6->7->8

代码如下

var arr = [
    {
        label: '1',
        children: [
            {
                label: '1-1',
                children: null
            },
            {
                label: '1-2',
                children: [
                    { label: '1-2-1', children: null},
                    { label: '1-2-2', children: null},
                ]
            }
        ]
    },
    {
        label: '2',
        children: [
            {
                label: '2-1',
                children: [
                    { label: '2-2-1', children: null },
                    { label: '2-2-2', children: null },
                ]
            },
            {
                label: '2-2',
                children: [
                    { label: '2-2-1', children: null},
                ]
            }
        ]
    }
]

// 深度优先:
let nodeList = [];
function deepTraversal(arr) {
    for (const n of arr) {
        nodeList.push(n.label);
        if (n.children) deepTraversal(n.children);
    }
}
deepTraversal(arr)
console.log('nodeList', nodeList)

// 广度优先:
var nodeList2 = [];
function widthTraversal(arr) {
    let stack = [];
    for (const n of arr) {
        nodeList2.push(n.label);
        if (n.children) stack = [...stack, ...n.children]
    }
    if (stack.length) widthTraversal(stack);
}
widthTraversal(arr);
console.log('nodeList2', nodeList2)

 

标签:优先,遍历,arr,label,广度,null,children
From: https://www.cnblogs.com/chailuG/p/16934173.html

相关文章