如何使用递归和栈实现深度优先搜索？

深度优先搜索的过程和递归调用在逻辑上是一致的。

写一个 TreeNode类代码,支持插入节点

class TreeNode {
    constructor(key){
        this.key = key;
        this.sons = []
    }
    insert(key){
        let node = new TreeNode(key);
        this.sons.push(node)  
        return node
    }
}
}

尝试创建一棵树

let str = 'hello word'
let str2 = 'abcdefg'

// 根节点
let root = new TreeNode("root")

createTree(str,root)

createTree(str2,root)

function createTree(strs,parent){
    if(strs.length !==0){
        let found = parent.sons.find((item)=>item.key === strs[0])
        if(found){
            let newStrs = strs.slice(1)
            createTree(newStrs,parent)
        }else{
            let node = parent.insert(strs[0])
            let newStrs = strs.slice(1)
            createTree(newStrs,node)
        }
      
    }else if(strs.length === 0){
        console.log('创建完毕',root)
        return root
    }
}

开始深度优先搜索

// 使用栈来实现深度优先搜索
// 大致思路是将所有的结点push到数组中,然后取最后一个处理,边删边处理.
// 直到没有为止
function dfsByStack(root) {
    let stack = []; 
      // 创建堆栈对象，js使用数组代替堆栈,其中每个元素都是TreeNode类型
    stack.push(root);    // 初始化的时候，压入根结点
    while (stack.length) {  // 只要栈里还有结点，就继续下去
    // 取出刚刚push进去的节点
    let node = stack.pop();  // 弹出栈顶的结点 拿到第一个进去的结点
    if (node.sons.length == 0) {
      // 已经到达叶子结点了，输出
        console.log('已经到达叶子结点',node.key)
    } else {
      // 非叶子结点，遍历它的每个子结点
      // 注意，这里使用了一个临时的栈stackTemp
      // 这样做是为了保持遍历的顺序，和递归遍历的顺序是一致的
      // 如果不要求一致，可以直接压入stack
      let stackTemp = []
      for (let index = 0; index < node.sons.length; index++) {
          const son = node.sons[index];
          console.log(son.key)
          stackTemp.push(son)
      }
      //  将各个节点放入栈中排序
      //  顺序反过来
      while (stackTemp.length) {
        stack.push(stackTemp.pop());
      }
    }
    }
  }  

广度优先搜索（Breadth First Search)

广度优先搜索BFS（Breadth First Search）也称为宽度优先搜索，它是一种先生成的结点先扩展的策略。 。

开始广度优先搜索

bfs(root.sons)
function bfs(queue){
    if(queue.length === 0){console.log('结束了');return;}
    let tmpQueue = []
    for (let index = 0; index < queue.length; index++) {
        const element = queue[index];
        console.log(element.key)
        if(element.sons && element.sons.length){
           // 准备下一个搜索所需要的数据
            tmpQueue.push(...element.sons)
        }
    }
    bfs(tmpQueue)
}

微信公众号

本文链接：