java二叉树遍历——深度优先(DFS)与广度优先(BFS) 递归版与非递归版
2024-09-20 02:10:24
介绍
深度优先遍历：从根节点出发，沿着左子树方向进行纵向遍历，直到找到叶子节点为止。然后回溯到前一个节点，进行右子树节点的遍历，直到遍历完所有可达节点为止。
广度优先遍历：从根节点出发，在横向遍历二叉树层段节点的基础上纵向遍历二叉树的层次。
DFS实现：
数据结构：栈
父节点入栈，父节点出栈，先右子节点入栈，后左子节点入栈。递归遍历全部节点即可
BFS实现：
数据结构：队列
父节点入队，父节点出队列，先左子节点入队，后右子节点入队。递归遍历全部节点即可
树的实现
public class TreeNode<V> {
private V value;
private List<TreeNode<V>> childList;//子节点列表
public TreeNode(V value) {
this.value = value;
}
public TreeNode(V value, List<TreeNode<V>> childList) {
this.value = value;
this.childList = childList;
}
public V getValue() {
return value;
}
public void setValue(V value) {
this.value = value;
}
public List<TreeNode<V>> getChildList() {
return childList;
}
public void setChildList(List<TreeNode<V>> childList) {
this.childList = childList;
}
}
深度优先搜索算法（DFS）
深度优先搜索算法是指沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。
递归实现
public static <V> void dfs(TreeNode<V> tree, int depth) {
if (tree != null) {
//打印节点值以及深度
System.out.println(tree.getValue().toString() + ", " + depth);
if (tree.getChildList() != null && !tree.getChildList().isEmpty()) {
for (TreeNode<V> item : tree.getChildList()) {
dfs(item, depth + 1);
}
}
}
}
非递归实现
public static <V> void dfsNotRecursive(TreeNode<V> tree) {
if (tree != null) {
//次数之所以用 Map 只是为了保存节点的深度，
//如果没有这个需求可以改为 Stack<TreeNode<V>>
Stack<Map<TreeNode<V>, Integer>> stack = new Stack<>();
Map<TreeNode<V>, Integer> root = new HashMap<>();
root.put(tree, 0);
stack.push(root);
while (!stack.isEmpty()) {
Map<TreeNode<V>, Integer> item = stack.pop();
TreeNode<V> node = item.keySet().iterator().next();
int depth = item.get(node);
//打印节点值以及深度
System.out.println(tree.getValue().toString() + ", " + depth);
if (node.getChildList() != null && !node.getChildList().isEmpty()) {
for (TreeNode<V> treeNode : node.getChildList()) {
Map<TreeNode<V>, Integer> map = new HashMap<>();
map.put(treeNode, depth + 1);
stack.push(map);
}
}
}
}
}
分类
一般来说 DFS 算法又分为如下三种：
1.前序遍历(Pre-Order Traversal) ：指先访问根，然后访问子树的遍历方式
private static <V> void dfs(TreeNode<V> tree, int depth) {
if (d != null) {
//打印节点值以及深度
System.out.println(tree.getValue().toString() + ", " + depth);
if (tree.getChildList() != null && !tree.getChildList().isEmpty()) {
for (TreeNode<V> item : tree.getChildList()) {
dfs(item, depth + 1);
}
}
}
}
2.后序遍历(Post-Order Traversal)：指先访问子树，然后访问根的遍历方式
private static <V> void dfs(TreeNode<V> tree, int depth) {
if (d != null) {
if (tree.getChildList() != null && !tree.getChildList().isEmpty()) {
for (TreeNode<V> item : tree.getChildList()) {
dfs(item, depth + 1);
}
}
//打印节点值以及深度
System.out.println(tree.getValue().toString() + ", " + depth);
}
}
3.中序遍历(In-Order Traversal)：指先访问左（右）子树，然后访问根，最后访问右（左）子树的遍历方式。
中序遍历一般是用二叉树实现：
private static <V> void dfs(TreeNode<V> root, int depth) {
if (root.getLeft() != null){
dfs(root.getLeft(), depth + 1);
}
if (root.getRight() != null){
dfs(root.getRight(), depth + 1);
}
//打印节点值以及深度
System.out.println(d.getValue().toString() + ", " + depth);
}
广度优先搜索算法（Breadth-First Search，BFS）
广度优先搜索算法是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。
递归实现
public static <V> void bfs(List<TreeNode<V>> children, int depth) {
List<TreeNode<V>> thisChildren, allChildren = new ArrayList<>();
for (TreeNode<V> child: children) {
//打印节点值以及深度
System.out.println(child.getValue().toString() + ", " + depth);
thisChildren = child.getChildList();
if (thisChildren != null && thisChildren.size() > 0) {
allChildren.addAll(thisChildren);
}
}
if (allChildren.size() > 0) {
bfs(allChildren, depth + 1);
}
}
递归实现的方式我自己想了好久没想出来，最后还是在网上搜到的算法。
可以看到非递归实现有个问题就是无法遍历根节点，不过问题不大，而且我也还没想出来其他更优雅的办法来实现。
非递归实现
public static <V> void bfsNotRecursive(TreeNode<V> tree) {
if (tree != null) {
//跟上面一样，使用 Map 也只是为了保存树的深度，没这个需要可以不用 Map
Queue<Map<TreeNode<V>, Integer>> queue = new ArrayDeque<>();
Map<TreeNode<V>, Integer> root = new HashMap<>();
root.put(tree, 0);
queue.offer(root);
while (!queue.isEmpty()) {
Map<TreeNode<V>, Integer> itemMap = queue.poll();
TreeNode<V> itemTreeNode = itemMap.keySet().iterator().next();
int depth = itemMap.get(itemTreeNode);
//打印节点值以及深度
System.out.println(itemTreeNode.getValue().toString() + ", " + depth);
if (itemTreeNode.getChildList() != null &&
!itemTreeNode.getChildList().isEmpty()) {
for (TreeNode<V> child : itemTreeNode.getChildList()) {
Map<TreeNode<V>, Integer> map = new HashMap<>();
map.put(child, depth + 1);
queue.offer(map);
}
}
}
}
}
最新文章
- 解决jquery操作checkbox全选全不选无法勾选问题
- 用手机自带uc浏览器查看静态页面，css样式不显示
- java内存模型及GC原理
- ImageMagick资料
- yum install 与 yum groupinstall 的区别
- (译) Angular运行原理揭秘 Part 1
- ThinkPHP函数详解：import方法
- Hibernate（六）一对一双向关联映射
- python 下的数据结构与算法---3:python内建数据结构的方法及其时间复杂度
- flex实现股票行情走势图
- openwrt makefile选项
- 各类编译器 allocator 底层
- ROS_Kinetic_08 ROS的集成开发环境(IDEs)之使用Eclipse
- Python 嘉宾列表问题
- CenOS_6.6_简单搭建vsFTP
- System.BadImageFormatException”C#报错
- 20165327 2017-2018-2 《Java程序设计》第6周学习总结
- laravel 集合接口
- JMeter测试WebSocket的经验总结
- [转]VS清除打开项目时的TFS版本控制提示