二叉树的几种遍历
还记得上大学时学数据结构这们课程，老师重点讲了树特别是二叉树这种数据结构。讲到二叉树的遍历，有前序、中序、后序 3 种方式，当时只记住了 3 种递归遍历的方式，后来在实际工作中有一次用到类似数据结构，结果发现递归过多会导致堆栈溢出的问题，后来对二叉树的非递归遍历做了一番研究，特此记录下来，希望对看到的同学有所帮助。
一般我们这样定义一棵二叉树：
//kotlin代码
class Node<T>(value: T?) {
var left: Node<T>? = null
var right: Node<T>? = null
}
二叉树.png
所有的遍历方式，都是针对节点自己与其左右子节点的相对遍历顺序而言的，当前节点相对其子节点先遍历则是先序，最后遍历则是后序。
1. 前序遍历
前序遍历按照根-左-右的顺序依次遍历节点，即先遍历当前节点，再遍历左子节点，最后是右子节点。
1.1 前序遍历-递归方式
递归方式很简单，直接上代码：
//前序遍历-递归方式
fun <T> preOrder(root: Node<T>?) {
root ?: return
//先遍历当前节点
print("${root.value} ")
//再遍历左子树
preOrder(root.left)
//最后遍历右子树
preOrder(root.right)
}
1.2 前序遍历-非递归-辅助堆栈-O(n)空间复杂度
二叉树前序-辅助堆栈-示意图
//前序遍历-非递归方式，借助一个辅助堆栈
fun <T> preOrder(root: Node<T>?) {
root ?: return
//一般借助一个辅助堆栈
var stack = Stack<Node<T>>()
stack.push(root)
while (stack.isNotEmpty()) {
var curr = stack.pop()
//先遍历当前节点
print("${curr.value} ")
//先将右子节点入栈, 因为堆栈具有先进后出的特性
curr.right?.let {
stack.push(it)
}
//再将左子节点入栈
curr.left?.let {
stack.push(it)
}
}
}
1.3 前序遍历-非递归-O(1)空间复杂度
这种遍历方式非常巧妙，不用任何辅助堆栈，只在 O(1) 空间复杂度的基础上就能实现，非常建议仔细理解学习一下。
这种算法的核心思想是，针对每一个目标节点 p，如果其左子节点不为空，则找到其左子节点的最右叶子节点 pd，将节点 pd 的右子节点指向 p，也就是 pd.right = p，看个示意图：
如上图所示，针对节点 p，其左子节点的最右叶子节点为 1，将节点 1 与节点p暂时连接起来。正是靠这个连接，我们才能在 O(1) 空间复杂度上完成遍历，完整的遍历过程如下图所示，结合代码理解起来更好：
fun <T> preOrder(root: Node<T>?) {
root ?: return
var p = root
while (p != null) {
//predecessor 就是当前节点的左子节点的最右叶子节点
var predecessor = p.left
while (predecessor?.right != null && predecessor.right != p) {
predecessor = predecessor.right
}
if (p.left == null) {
//如果没有左子节点，则继续遍历右子节点
print("${p.value} ")
p = p.right
} else {
if (predecessor!!.right == p) {
//说明节点 p 第二次遍历到，当前节点 p 以及其左子树均已遍历过了，我们继续遍历其右子树
predecessor.right = null
p = p.right
} else {
//需要进行节点连接 predecessor.right -> p
predecessor.right = p
print("${p.value} ")
p = p.left
}
}
}
}
2. 中序遍历
中序遍历按照左-根-右的顺序依次遍历节点。
2.1 中序遍历-递归方式
//左-根-右递归执行
fun <T> inOrder(root: Node<T>?) {
root ?: return
//先遍历左子树
inOrder(root.left)
//遍历根节点
print("${root.value} ")
//最后遍历右子树
inOrder(root.right)
}
2.2 中序遍历-非递归-辅助堆栈-O(n)空间复杂度
中序遍历非递归方式比较不好理解，遍历时我们总是要先找到当前节点的左子节点之后，再遍历当前节点。
fun <T> inOrder(root: Node<T>?) {
root ?: return
//辅助堆栈
var stack = Stack<Node<T>>()
//p为当前目标节点
var p: Node<T>? = root
while (stack.isNotEmpty() || p != null) {
//找到目标节点最左边的子节点
while (p != null) {
//所有节点依次入栈
stack.push(p)
p = p.left
}
if (stack.isNotEmpty()) {
var node = stack.pop()
print("${node.value} ")
//左边的节点处理过，还要处理右边的节点
node.right?.let {
//目标节点变为右边的节点
p = it
}
}
}
}
上面的代码结合遍历过程图理解会更容易一点。
2.3 中序遍历-非递归-O(1)空间复杂度
与前序遍历非递归遍历的方式几乎一模一样。
fun <T> inOrder(root: Node<T>?) {
root ?: return
var p = root
while (p != null) {
var predecessor = p.left
while (predecessor?.right != null && predecessor.right != p) {
predecessor = predecessor.right
}
if (p.left == null) {
print("${p.value} ")
p = p.right
} else {
if (predecessor!!.right == p) {
predecessor.right = null
//注意这里的区别，前序与中序遍历无非是对根节点的遍历先后顺序
print("${p.value} ")
p = p.right
} else {
predecessor.right = p
p = p.left
}
}
}
}
3. 后序遍历
后序遍历按照左-右-根的顺序依次遍历节点。
3.1 后序遍历-递归方式
fun <T> postOrder(root: Node<T>?) {
root ?: return
postOrder(root.left)
postOrder(root.right)
print("${root.value} ")
}
3.2 后序遍历-非递归(借助辅助堆栈)
这里介绍一种使用2个辅助堆栈的遍历方法，理解以及代码实现都非常简单。
fun <T> postOrder(root: Node<T>?) {
root ?: return
var s1 = Stack<Node<T>>()
var s2 = Stack<Node<T>>()
s1.push(root)
while (s1.isNotEmpty()) {
var node = s1.pop()
node.left?.let {
s1.push(it)
}
node.right?.let {
s1.push(it)
}
s2.push(node)
}
while (s2.isNotEmpty()) {
var node = s2.pop()
print("${node.value} ")
}
}
这种我觉得是最简单的后序遍历方式了，实质上是利用了堆栈的先进后出特性。
4. 层序遍历
层序遍历就是按照树的结构，一层一层从左往右遍历，只需要借助一个队列即可，遍历方式很简单，看代码即可了解：
fun <T> levelOrder(root: Node<T>?) {
root ?: return
var queue = LinkedList<Node<T>>()
queue.offer(root)
var level = 0
while (queue.isNotEmpty()) {
//当前这一层总共有多少个节点
var levelCount = queue.size
//当前层的节点遍历完之后，其子节点都是下一层的节点了
while (levelCount > 0) {
levelCount--
var node = queue.pollFirst()
print("${node.value} ")
node.left?.let {
queue.offer(it)
}
node.right?.let {
queue.offer(it)
}
}
level++
println()
}
println("total level: $level")
}
5. 根据遍历顺序生成树
常见的有根据前序遍历、中序遍历，生成一棵树，或者是根据中序遍历、后序遍历生成一棵树，以前者为例来说明如何生成一棵树。
首先，前序遍历的第 1 个元素肯定是根节点，在中序遍历列表里，找到该根节点，该根节点左边的元素肯定是其左子树，根节点右边的元素肯定是其右子树，这样我们基本就能确定一棵二叉树的根节点及其左右子树了。接着，再用同样的方式分别对其左子树、右子树递归下去，就能完整地构建整颗二叉树了。
fun buildTree(
preOrderArray: IntArray, inOrderArray: IntArray,
preStart: Int, preEnd: Int, inStart: Int, inEnd: Int
): Node<Int>? {
//递归结束条件
if (preStart == preEnd) {
return Node(preOrderArray[preStart])
}
if (preStart > preEnd) {
return null
}
//根节点是前序数组的第一个元素
var root = Node(preOrderArray[preStart])
//在中序遍历数组中找到根节点
var rootIndexInInOrder = inStart
for (i in inStart..inEnd) {
if (inOrderArray[i] == root.value) {
rootIndexInInOrder = i
break
}
}
//中序遍历中左子树的范围 [inStart, rootIndexInInOrder - 1]
//中序遍历中右子树的范围 [rootIndexInInOrder + 1, inEnd]
//递归构造左右子树
//左子树长度
var leftTreeLen = rootIndexInInOrder - inStart
//前序遍历中左子树的范围 [preStart + 1, preStart + leftTreeLen]
//前序遍历中右子树的范围 [preStart + leftTreeLen + 1, preEnd]
var leftChild = buildTree(preOrderArray, inOrderArray,
preStart + 1, preStart + leftTreeLen,
inStart, rootIndexInInOrder - 1
)
var rightChild = buildTree(preOrderArray, inOrderArray,
preStart + leftTreeLen + 1, preEnd,
rootIndexInInOrder + 1, inEnd
)
root.left = leftChild
root.right = rightChild
return root
}
6. 小结
本文介绍了二叉树的各种遍历方式：前序、中序、后序、层序遍历，除了递归的方式更是着重讲了非递归的方式，其中 O(1) 空间复杂度的遍历算法最为巧妙，需要好好理解。
二叉树的遍历是算法学习中的基础，最好能手写出来，很多复杂的算法思想都是由此演化而来，以后不管是刷题还是面试，相信都能帮到你。
