6.1 树的BFS与DFS搜索
搜索 DFS BFS 6.1
2023-09-14 09:06:54 时间
在实际的开发工作中,我们会遇到很多树状结构,比如说文件系统、菜单树、商品分类。也就说目录结构是一种典型的树状结构。对于刚入行开发的新人来说,他们可能会使用递归的方式去遍历一棵树。
BFS搜索叫宽度优先搜索,也叫广度优先搜索。是树的搜索方法中常见的方法,是一种按层搜索的方法。这个方法可以用递归实现,也可以用非递归方法实现。
比如这个树,宽度优先搜索顺序就是4 2 7 1 3 6 9 5 10。
那么具体要怎么实现呢?这个时候需要用到队列,为了方便理解,我建议大家想象一下,在树的根部,有一个大吸管,把树中的元素全部吸进去。
首先初始化队列,把root,也就是4进入队列
然后从左边取出队列元素,也就是4
如果4 有子元素,那么依次从后面放入队列
这时队列为
2 7
第二次循环,取出了2,但是2有子元素,从后面放入队列
这时队列为
7 1 3 6 9
原理在于把子元素放在队列的后面,取的时候先取上一层元素。所以这就实现了宽度优先搜索。
代码实现如下:
/**
* 宽度搜索
*
* @param visitor
*/
public void bfs(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
nodes.add(root);
while (!nodes.isEmpty()) {
BinaryNode<T> node = nodes.pop();
nodes.addAll(node.getChildren());
if (!visitor.test(node)) {
break;
}
}
}
实际效果
测试类代码
AVLTree<Integer> avlTree = new AVLTree<>();
for (int i = 0; i < 10; i++) {
avlTree.add(i + 1);
}
System.out.println(avlTree.toTreeString());
avlTree.bfs(x->{
System.out.print(x.getValue()+" ");
return true;
});
那么深度优先呢?
还是上面那棵树
我们把队列换成栈
初始化栈为4
取出4,这个时候放入4的子级,栈变成了
2 7
那么,因为是栈,这个时候取出的是7,然后再压入7的子元素,栈变成了
2 7 6 9
然后取出9,压入10,栈变成了
1 7 6 10
所以整个遍历顺序是4 7 9 10 6 5 2 3 1。
深度搜索默认是最右边开始的,直接深入到最深的叶子。
如果要改变深度搜索的左右顺序,把子元素压栈时,先翻转再压栈。这样能实现从左到右的遍历。
代码实现
/**
* 深度搜索
*
* @param visitor
*/
public void dfs(Predicate<Node<T>> visitor) {
final Deque<BinaryNode<T>> nodes = new ArrayDeque<>();
nodes.add(root);
while (!nodes.isEmpty()) {
BinaryNode<T> node = nodes.pop();
List<BinaryNode<T>> children = node.getChildren();
Collections.reverse(children);
children.forEach(nodes::push);
if (!visitor.test(node)) {
break;
}
}
}
实际效果:
相关文章
- 【题解】小木棍(搜索剪枝)
- 【算法竞赛 - 搜索】八数码
- 关键词搜索1688商品接口,1688商品列表接口,1688商品销量排序接口,1688商品价格排序接口代码分享
- Python tkinter 制作文章搜索软件,有没有方便快捷不知道,好玩就行了
- 无缝整合 Google 自定义搜索框到 WordPress
- typecho按分类搜索文章
- Find Any File for Mac(文件搜索)
- 深入Linux命令行:搜索篇(linux命令搜索)
- MySQL 搜索重复记录的妙招(mysql查询相同数据)
- Win10 20H1/20H2获累积更新 修复文件管理器搜索过滤功能
- 用Redis实现正则表达式的高效搜索(redis正则)
- Linux查询文件夹:最快速的搜索方式(linux 查询文件夹)
- 使用Redis来加速你的搜索(搜索地Redis)
- 利用Oracle中的Like进行模糊搜索(oracle中有like)
- jquery实现搜索框常见效果的方法