跳到主要内容位置

树的广度优先遍历

树的广度优先遍历指的是,从根节点开始,遍历下一层中所有的子节点,然后再继续遍历下一层子节点,以此类推。

子节点可以从左到右遍历,也可以从右到左遍历。

因为遍历节点的顺序相对固定,所以广度优先遍历不区分前序、中序和后序。

同样的遍历方式也可以用于图中。

应用

广度优先遍历可以应用于搜索引擎爬虫、社交网站寻找人脉关系、导航寻找最短路径上。

思路

广度优先遍历的大体思路是(以二叉树为例),利用一个队列,把根节点放入队列中,然后开始从队列里取出节点,进行遍历,再把当前遍历节点的所有子节点追加到队尾。按照队列先进先出的原则,当这一层所有节点都遍历完成之后,才能轮到下一层节点,这样队列为空之后,所有节点就遍历完了。

代码

这里是代码,queue 就是维护的队列,result 是遍历结果,我们会把遍历到的节点值放到这个结果数组中。后面在循环中会判断 queue 是否为空,然后遍历其中的节点,并把节点的子节点追加到队尾:

breadthFirstTraversal() {
let result = [];
let queue = [];
queue.push(this.root);
while (queue.length) {
let current = queue.shift();
result.push(current.value);
if (current.left) {
queue.push(current.left);
}
if (current.right) {
queue.push(current.right);
}
}
return result;
}

小结

好了,这个就是树的广度优先遍历,你学会了吗?如果有帮助请三连并关注,想学更多的开发知识,可以在评论区留言,感谢观看!

提示

《Vue 3.x 全家桶完全指南与实战》课程已上线,包括 Vue 3.x、TypeScript、Vue Router 4.x、Vuex 4.x 所有初级到高级的语法特性详解,让你完全胜任 Vue 前端开发的工作。点击查看详情。

新书《JavaScript 基础语法详解》已上架,可在京东、当当、淘宝等各大电商购买