在日常工作中,我们经常会用到遍历操作。如遍历一颗树,找到某个节点。遍历又分为广度优先遍历 (Depth First Search)和深度优先遍历(Breadth First Search)两种。

# 1、深度优先遍历(DFS)

  首先访问根节点,其次是它的子节点,访问子节点的子节点,直到子节点没有子节点为止,就这样一直循环下去,直到根节点下所有的子节点都被访问到为止。简单点说就是,从根节点出发,按照从左到右的顺序,访问其子节点,如果子节点还有子节点,则一直向下访问,直到没有子节点为止。然后再返回到离根节点最近的而没有访问到的子节点,然后按照前面的查找方法,一遍一遍的循环下去,直到所有的节点被访问完毕为止。 算法实现如下:

    function deepTranversal(node,nodeList=[]){
        if(node){
            nodeList.push(node)
            let children=node.children;
            let len=children.length;
            if(children&&len){
                for(let i=0;i<len;i++){
                    deepTranversal(node,nodeList)
                }
            }
        }
        return nodeList;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
//验证
<div id="A">
    A
    <div id="B1">
        B1
        <span id="C1">C1</span>
        <span id="C2">C2</span>
    </div>
    <div id="B2">B2
        <span id="C3">C3</span>
        <span id="C4">C4</span>
    </div>
    <div id="B3">B3
        <span id="C5">C5</span>
        <span id="C6">C6</span>
    </div>
    <div id="B4">B4
        <span id="C7">C7</span>
        <span id="C8">C8</span>
    </div>
</div>
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
<!-- 如上所示节点树 -->
let  node=document.querySelector("#A");
for(let item of deepTranversal(node,[])){
    console.log(item.id);
}
    
1
2
3
4
5
6

输出结果如下

# 2、广度优先遍历

  首先访问根节点,其次是它的子节点,然后按照从左到右的顺序,访问子节点的子节点,直到子节点没有子节点为止,就这样一直循环下去,直到根节点下所有的子节点都被访问到为止。简单点说就是从根节点出发,一层一层的从上向下访问,同层节点从左往右访问,直到所有的节点都被访问到为止。 算法实现如下:

function breadthTranversal(node,nodeList=[]){
    let satck=[];
    if(node){
        stack.push(node);
        while(stack.length){
            let item=stack.shift();
            nodeList.push(item);
            let children=item.children;
            let len=children.length;
            for(let i=0;i<len;i++){
                stack.push(children[i]);
            }
        }
    }
    return nodeList;
}
//验证 节点还是上面的节点数据
for(let item of breadthTranversal(node,[])){
    console.log(item.id)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

输出结果如下

Last Updated: 6/4/2020, 10:33:20 AM