JS实现树的深度优先搜索和广度优先搜索

这是我参与更文挑战的第20天，活动详情查看： 更文挑战

前面我们讲了二叉树的搜索，二叉树的搜索可以有很多扩展，可以扩展成树的搜索，图的搜索，图的搜索可以扩展成爬虫的逻辑。今天我们就了解一下树的搜索。

搜索分为两种，一种是深度优先搜索，一种是广度优先搜索。
深度优先搜索是沿着节点的一条边，一路走到黑，然后返回到出发节点，再继续下一条边，如果找到目标节点，则返回，如果找不到，就会遍历完全部节点。
而广度优先搜索则是一层一层去寻找。如上图，用广度优先搜索是先从A开始，如果没找到就继续从第二层CB找，如果找到目标节点，则返回，如果找不到，就会一层一层遍历全部节点。
深度优先搜索更适合探索未知，因为它是先往远的地方走，能走多远走多远。
广度优先搜索更适合探索局域，例如我知道这里附近有要找的东西，那么我就从这附近一层一层的找。

代码实现树的深度优先搜索

function Node(value) {
    this.value = value;
    this.childs = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");

a.childs.push(c);
a.childs.push(f);
a.childs.push(b);
b.childs.push(d);
b.childs.push(e);

function deepSearch(root, target) {
    if (root == null) return false;
    if (root.value == target) return true;
    var result = false;
    for (var i = 0 ; i < root.childs.length ; i ++) {
        result |= deepSearch(root.childs[i], target);
    }
    return result ? true : false;
}

console.log(deepSearch(a, "e"));
复制代码

代码实现树的广度优先搜索

function Node(value) {
    this.value = value;
    this.childList = [];
}

var a = new Node("a");
var b = new Node("b");
var c = new Node("c");
var d = new Node("d");
var e = new Node("e");
var f = new Node("f");

a.childList.push(c);
a.childList.push(f);
a.childList.push(b);
b.childList.push(d);
b.childList.push(e);

function f1(rootList,target){
    if (rootList == null || rootList.length == 0) return false;
    var childList = [];//当前层所有节点的子节点，都在这个list中，这样传入下一层级的时候，就可以遍历整个层级的节点。
    for (var i = 0; i < rootList.length; i++) {
         if (rootList[i] !== null && rootList[i].value == target) {
             return true;
         } else {
            childList = childList.concat(rootList[i].childList);
         }     
    }
    return f1(childList,target);
}
console.log(f1([a],'e'));
复制代码