java数据结构与算法之二叉树深度优先和广度优先遍历
程序员文章站
2022-07-07 18:55:35
...
一、宽度优先遍历
算法流程:
宽度优先遍历使用 队列,先进先出。
- 先将头节点压入队列中,进入while循环
- 每循环一次就从队列中弹出一个元素,弹出就打印。
- 将该弹出元素的左右孩子节点压入队列中(如果有的话),先压左孩子,再压右孩子。
- 重复上面第 2 、3 步骤,直到队列为空
- 当遍历完整棵树以后就完成了树的宽度优先遍历
代码如下:
/**
* 二叉树宽度优先遍历
* 宽度优先用队列
*/
public static void widthPriority(final TreeNode head) {
if (head == null) {
return;
}
final LinkedList<TreeNode> queue = new LinkedList<>();
queue.add(head);
while (!queue.isEmpty()) {
// 从队列里弹出一个元素,弹出就打印
final TreeNode node = queue.pop();
System.out.println(node.data);
// 左孩子压入队列(如果有)
if (node.left != null) {
queue.add(node.left);
}
// 右孩子压入队列(如果有)
if (node.right != null) {
queue.add(node.right);
}
}
}
二、深度优先遍历
二叉树的中序遍历其实就是树的深度优先遍历 !!!
方式一、自己用栈实现
/**
* 二叉树深度优先遍历(中序遍历其实就是深度优先遍历)
* 深度优先用栈实现
*/
public static void deepPriority(final TreeNode head) {
if (head == null) {
return;
}
TreeNode current = head;
final Stack<TreeNode> stack = new Stack<>();
while (!stack.isEmpty() || current != null) {
// 顺着左边界一直走到底
if (current != null) {
stack.push(current);
current = current.left;
} else {
// 如果左边界已经走到底了,则从栈中弹一个节点出来,并且将current指针指向弹出节点的right节点,继续上面while循环
final TreeNode node = stack.pop();
// 弹出就打印
System.out.print(node.data + ",");
current = node.right;
}
}
}
方式二、用递归实现
/**
* 递归的方式实现深度优先遍历
*/
public static void deepPriority02(final TreeNode head) {
if (head == null) {
return;
}
inOrderTraversalProcessor(head);
}
/**
* 中序遍历二叉树(也是深度优先遍历)
*/
public static void inOrderTraversalProcessor(final TreeNode head) {
// base case
if (head == null) {
return;
}
// 处理左子树
inOrderTraversalProcessor(head.left);
// 中序遍历,左子树递归返回就打印
System.out.print(head.data + ",");
// 处理右子树
inOrderTraversalProcessor(head.right);
}
推荐阅读
-
PHP实现二叉树深度优先遍历(前序、中序、后序)和广度优先遍历(层次)实例详解
-
python数据结构之图深度优先和广度优先实例详解
-
PHP实现二叉树的深度优先与广度优先遍历方法
-
Python数据结构与算法之图的广度优先与深度优先搜索算法示例
-
数据结构与算法-----BFS与DFS(广度优先搜索与深度优先搜索)
-
数据结构与算法_深度优先搜索(DFS)与广度优先搜索(BFS)详解
-
Java数据结构与算法:图、图的概念、深度优先搜索DFS、广度优先搜索BFS、思路分析、代码实现
-
Java数据结构与算法——深度优先搜索与广度优先搜索
-
数据结构与算法——广度和深度优先搜索
-
数据结构与算法————图的遍历DFS深度优先搜索和BFS广度优先搜索