文章目录
万丈高楼平地起,正所谓地基打得好,百年不会倒。
计算机程序如同高楼的建造,也是要先打好地基,再一层层往上盖。
程序是由数据结构和算法组成的,核心是数据结构和算法。
本篇我们要总结的,是二叉树这种数据结构的遍历方式,提供一些基本的模板,以便随时查阅与套用,快速的搭建程序。
二叉树的4种遍历方式,包括3种深度优先搜索(DFS)和1种广度优先搜索(BFS)。
深度优先搜索(DFS)
递归版本
前序遍历
递归思路:先访问根节点,然后递归遍历左子树,最后递归遍历右子树。
终止条件:节点为空。
/**
* 前序遍历(递归模板)
*
* @param node
*/
public void preOrder(BinaryNode<T> node) {
if (node == null) {
return;
}
System.out.print(node.element); // 访问节点,主逻辑处理
preOrder(node.leftChild);
preOrder(node.rightChild);
}
中序遍历
递归思路:先递归遍历左子树,然后访问根节点,最后递归遍历右子树。
终止条件:节点为空。
/**
* 中序遍历(递归模板)
*
* @param node
*/
public void inOrder(BinaryNode<T> node) {
if (node == null) {
return;
}
inOrder(node.leftChild);
System.out.print(node.element); // 访问节点,主逻辑处理
inOrder(node.rightChild);
}
后序遍历
递归思路:先递归遍历左子树,然后递归遍历右子树,最后访问根节点。
终止条件:节点为空。
/**
* 后序遍历(递归模板)
*
* @param node
*/
public void postOrder(BinaryNode<T> node) {
if (node == null) {
return;
}
postOrder(node.leftChild);
postOrder(node.rightChild);
System.out.print(node.element); // 访问节点,主逻辑处理
}
小结
二叉树的3种递归遍历方式,逻辑简单清晰。
在时间和空间复杂度上都是一样的:
- 时间复杂度:O(N)。其中N为节点的数量,每个节点需要访问1次.
- 空间复杂度:取决于保存调用栈的深度。最好是O(logN),平衡树;最坏是O(N),链表。 实际应用中,一般都会使用稳定的平衡树,如红黑树和AVL树。
迭代版本
对于二叉树的迭代版本,主要是借助一个栈,来模拟递归的函数调用栈,实现节点的入栈和出栈。
前序遍历
/**
* 前序遍历(迭代模板).
*
* @param root
*/
public void preOrder(BinaryNode<T> root) {
if (root == null) {
return;
}
// 创建一个栈,用于存储待遍历的节点
LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
nodeStack.push(root);
while (!nodeStack.isEmpty()) {
// 1.节点出栈,访问节点,主逻辑处理
BinaryNode<T> current = nodeStack.pop();
System.out.print(current.element);
// 2.右孩子节点入栈
if (current.rightChild != null) {
nodeStack.push(current.rightChild);
}
// 3.左孩子节点入栈
if (current.leftChild != null) {
nodeStack.push(current.leftChild);
}
}
}
中序遍历
/**
* 中序遍历(迭代模板).
*
* @param root
*/
public void inOrder(BinaryNode<T> root) {
if (root == null) {
return;
}
// 创建一个栈,用于存储待遍历的节点
LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
while (root != null || !nodeStack.isEmpty()) {
// 1.先将自己入栈,然后左孩子节点循环入栈. 后进先出,左孩子节点优先访问.
while (root != null) {
nodeStack.push(root);
root = root.leftChild;
}
// 2.节点出栈,访问节点,主逻辑处理
BinaryNode<T> current = nodeStack.pop();
System.out.print(current.element);
// 3.右孩子节点作为下一个待遍历的子树根节点
root = current.rightChild;
}
}
后序遍历
迭代版本1
借助一个列表,按照前序遍历的方式访问节点后存储结果。最后,再逆序访问节点,完成后序的遍历过程。
核心遍历逻辑与上面前序遍历的差异点是,对左右孩子节点的入栈顺序颠倒一下。
/**
* 后序遍历(迭代模板1).
*
* @param node
*/
public void postOrder(BinaryNode<T> root) {
if (root == null) {
return;
}
// 存放遍历的结果,按"前序遍历"的结果进行存储
List<T> resultList = new ArrayList<>();
// 创建一个栈,用于存储待遍历的节点
LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
nodeStack.push(root);
while (!nodeStack.isEmpty()) {
// 1.节点出栈,保存节点值
BinaryNode<T> current = nodeStack.pop();
resultList.add(current.element);
// 2.左孩子节点入栈
if (current.leftChild != null) {
nodeStack.push(current.leftChild);
}
// 1.右孩子节点入栈
if (current.rightChild != null) {
nodeStack.push(current.rightChild);
}
}
// 访问节点,主逻辑处理
for (int i = resultList.size() - 1; i >= 0; i--) {
System.out.print(resultList.get(i));
}
}
迭代版本2
这个版本不需要借助列表存储遍历结果,但逻辑显得很复杂。
/**
* 后序遍历(迭代模板2).
*
* @param node
*/
public void postOrder2(BinaryNode<T> root) {
if (root == null) {
return;
}
// 创建一个栈,用于存储待遍历的节点
LinkedList<BinaryNode<T>> nodeStack = new LinkedList<>();
BinaryNode<T> lastVisit = null;
while (root != null || !nodeStack.isEmpty()) {
// 1.先将自己入栈,然后左孩子节点循环入栈. 后进先出,左孩子节点优先访问.
while (root != null) {
nodeStack.push(root);
root = root.leftChild;
}
// 2.检查最左侧的节点,符合条件则访问节点
// 1)如果无右孩子节点,说明无子节点,则访问节点;
// 2)如果是上次访问节点的父节点,则访问节点。
BinaryNode<T> current = nodeStack.peek();
if (current.rightChild == null || current.rightChild == lastVisit) {
nodeStack.pop();
System.out.print(current.element); // 主逻辑处理
// 保存最后一次访问的节点
lastVisit = current;
// 下一次直接处理栈顶节点
root = null;
// 3.右孩子节点作为下一个待遍历的子树根节点
} else {
root = current.rightChild;
}
}
}
广度优先遍历(BFS)
迭代版本
节点的访问过程如下:
- 访问根节点;
- 访问根节点的左孩子节点left和右孩子节点right;
- 访问左孩子节点left的左右孩子节点,再访问右孩子节点right的左右孩子节点;
- …
/**
* 广度优先遍历(迭代模板). 从根到叶子节点,层次遍历.
*
* @param root
*/
public void bfs(BinaryNode<T> root) {
if (root == null) {
return;
}
// 创建一个队列,用于存储待遍历的节点
LinkedList<BinaryNode<T>> nodeQueue = new LinkedList<>();
nodeQueue.add(root);
while (!nodeQueue.isEmpty()) {
// 1.节点出列,访问节点,主逻辑处理
BinaryNode<T> current = nodeQueue.poll();
System.out.print(current.element);
// 2.左孩子节点入列
if (current.leftChild != null) {
nodeQueue.add(current.leftChild);
}
// 3.右孩子节点入列
if (current.rightChild != null) {
nodeQueue.add(current.rightChild);
}
}
}
小结
二叉树的迭代遍历方式,在实现上显得略微复杂,特别是后序遍历的第2个迭代版本的实现。
时间复杂度上和递归版本一样,都是O(N)。
空间复杂度主要取决于树的形状,可能是O(1)、O(logN)或O(N)。
---转载本站文章请注明作者和出处 二进制之路(binarylife.icu),请勿用于任何商业用途---