数学篇 - 树的深度优先搜索与广度优先搜索(笔记)
如何使用递归和栈实现深度优先搜索?
深度优先搜索的过程和递归调用在逻辑上是一致的。
写一个 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)
}
微信公众号
