二叉树的几种遍历

还记得上大学时学数据结构这们课程，老师重点讲了树特别是二叉树这种数据结构。讲到二叉树的遍历，有前序、中序、后序 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) 空间复杂度的遍历算法最为巧妙，需要好好理解。
二叉树的遍历是算法学习中的基础，最好能手写出来，很多复杂的算法思想都是由此演化而来，以后不管是刷题还是面试，相信都能帮到你。