二叉搜索树的中序遍历：从顺序到 Go 实现

二叉树的遍历，是学习树结构时绕不开的基础。所谓“遍历”，就是按照某种固定顺序访问树中的每个节点，并且每个节点只访问一次。

本文从一个具体例子出发，介绍二叉搜索树的中序遍历，并用 Go 写出递归和迭代两种实现。

什么是二叉搜索树

二叉搜索树（Binary Search Tree，简称 BST）首先是一棵二叉树，也就是每个节点最多有两个子节点。它通常还满足下面的规则：

左子树中的值小于当前节点的值；
右子树中的值大于当前节点的值；
左右子树本身也分别是二叉搜索树。

如果业务允许重复值，还需要额外约定重复值固定放在左侧还是右侧。本文示例中的节点值互不重复。

一棵以 8 为根节点的二叉搜索树，以及中序遍历得到的升序序列

图中以 8 为根节点。比 8 小的值位于左子树，比 8 大的值位于右子树，这正是二叉搜索树最重要的结构特征。

中序遍历的顺序

中序遍历对每个节点都执行同样的三步：

遍历左子树；
访问当前节点；
遍历右子树。

可以简记为：左—根—右。

对于上图中的二叉搜索树，中序遍历结果是：

1 → 3 → 4 → 6 → 7 → 8 → 10 → 13 → 14

结果恰好是升序排列。这并不是巧合：因为二叉搜索树保证左侧的值更小、右侧的值更大，所以按照“左—根—右”访问时，自然会得到从小到大的序列。

Go 递归实现

递归写法与“左—根—右”的定义几乎完全一致，适合用来理解中序遍历。

package main

type TreeNode struct {
	Value int
	Left  *TreeNode
	Right *TreeNode
}

func InorderTraversal(root *TreeNode) []int {
	result := make([]int, 0)

	var walk func(node *TreeNode)
	walk = func(node *TreeNode) {
		if node == nil {
			return
		}

		walk(node.Left)              // 1. 遍历左子树
		result = append(result, node.Value) // 2. 访问当前节点
		walk(node.Right)             // 3. 遍历右子树
	}

	walk(root)
	return result
}

当 node == nil 时，说明已经走到空子树，函数直接返回。其余部分严格按照左子树、当前节点、右子树的顺序执行。

Go 迭代实现

递归调用会由程序运行时维护调用栈。我们也可以自己准备一个栈，用循环完成同样的过程：

func InorderTraversalIterative(root *TreeNode) []int {
	result := make([]int, 0)
	stack := make([]*TreeNode, 0)
	current := root

	for current != nil || len(stack) > 0 {
		// 不断向左走，并记住沿途节点。
		for current != nil {
			stack = append(stack, current)
			current = current.Left
		}

		// 左子树处理完毕，访问栈顶节点。
		current = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		result = append(result, current.Value)

		// 接着处理右子树。
		current = current.Right
	}

	return result
}

这段代码可以理解为：先一路向左，把暂时不能访问的节点保存起来；走到最左端后，弹出一个节点并访问它，然后转向它的右子树。

初学时建议先掌握递归写法，再结合调用栈理解迭代写法，两者的访问顺序完全相同。

时间与空间复杂度

假设树中有 n 个节点，树的高度为 h：

时间复杂度是 O(n)，因为每个节点都会被访问一次；
空间复杂度是 O(h)，递归调用栈或迭代使用的栈最多保存一条从根到叶子的路径；
对于较平衡的树，h 约为 log n；如果树退化成链表，h 最坏会达到 n。

这里的 O(h) 指遍历过程使用的辅助空间；如果把保存全部遍历结果的 result 切片也计算在内，总空间为 O(n)。树是否平衡会影响栈深度，但不会改变完整遍历必须访问每个节点一次的 O(n) 时间复杂度。

常见误区

中序遍历并不总能得到升序序列。 只有被遍历的树满足二叉搜索树规则时，结果才是有序的。
不要忘记空节点判断。 递归函数缺少 node == nil 的终止条件，会继续访问空指针。
不要混淆三种深度优先遍历。 前序是“根—左—右”，中序是“左—根—右”，后序是“左—右—根”。

小结

中序遍历的核心只有四个字：左—根—右。把它应用到二叉搜索树上，就能按升序访问所有节点。递归实现更贴近定义，迭代实现则把隐式的调用栈改成了显式栈；理解两种写法后，后续学习查找、排序验证和树结构相关算法都会更顺畅。