详解二叉树遍历的非递归实现

传统的二叉树遍历常通过递归方式实现，递归算法简洁明了，符合人们对问题的直观理解，其代码逻辑清晰，能够轻松地表达遍历的过程。然而，递归算法在实际应用中存在一定的局限性。递归调用会在系统栈中保存大量的函数调用信息，包括参数、局部变量和返回地址等，这导致了较高的空间复杂度。当处理大规模数据或深度较大的二叉树时，可能会引发栈溢出错误，严重影响程序的稳定性和性能。此外，递归调用本身也存在一定的时间开销，函数的调用和返回操作会消耗额外的时间资源。

为了克服递归遍历的这些缺点，非递归实现方式应运而生。非递归遍历通过使用栈、队列等辅助数据结构，以迭代的方式模拟递归过程，从而避免了递归调用带来的栈溢出风险和高空间复杂度问题。非递归实现不仅能够更有效地利用内存资源，还能在一定程度上提升算法的执行效率，使得程序在处理大型数据时更加稳定和高效。

一、二叉树基础知识

1.1 二叉树的定义与结构

二叉树是一种每个节点最多有两个子节点的数据结构，这两个子节点分别被称为左子节点和右子节点。从形式化定义来讲，二叉树要么为空，要么由一个根节点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成 。在实际存储时，通常采用链式存储结构，每个节点包含数据域以及指向左子节点和右子节点的指针。

// 定义二叉树节点结构
struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

比如，我们有如下一个简单的二叉树结构：

        1/   \2     3/ \4   5

在这个二叉树中，根节点的值为 1，它的左子节点是值为 2 的节点，右子节点是值为 3 的节点。值为 2 的节点又有自己的左子节点（值为 4）和右子节点（值为 5）。通过这样的节点连接方式，构成了一个完整的二叉树结构，这种结构使得数据的组织具有层次性和结构性，方便进行各种操作和算法实现。

1.2 二叉树遍历的递归实现

二叉树的遍历主要有前序遍历、中序遍历和后序遍历三种递归实现方式，它们的区别在于访问根节点、左子树和右子树的顺序不同。

前序遍历：先访问根节点，然后递归地前序遍历左子树，最后递归地前序遍历右子树。以刚才的二叉树为例，前序遍历的顺序是 1 -> 2 -> 4 -> 5 -> 3。递归实现的代码如下：

def preorderTraversal(root):result = []if root:result.append(root.val)result += preorderTraversal(root.left)result += preorderTraversal(root.right)return result

中序遍历：先递归地中序遍历左子树，然后访问根节点，最后递归地中序遍历右子树。对于上述二叉树，中序遍历的顺序是 4 -> 2 -> 5 -> 1 -> 3。代码实现如下：

def inorderTraversal(root):result = []if root:result += inorderTraversal(root.left)result.append(root.val)result += inorderTraversal(root.right)return result

后序遍历：先递归地后序遍历左子树，然后递归地后序遍历右子树，最后访问根节点。该二叉树的后序遍历顺序是 4 -> 5 -> 2 -> 3 -> 1。实现代码如下：

def postorderTraversal(root):result = []if root:result += postorderTraversal(root.left)result += postorderTraversal(root.right)result.append(root.val)return result

这三种递归遍历方式在代码结构上非常相似，核心都是利用递归函数不断深入到子树进行访问，只是访问根节点的时机不同。前序遍历是最先访问根节点，中序遍历在中间访问根节点，后序遍历最后访问根节点。递归实现虽然简洁直观，但由于递归调用会消耗栈空间，在处理大规模数据或深度较大的二叉树时，可能会面临栈溢出的风险，这也是我们需要研究非递归实现的重要原因。

二、二叉树遍历的非递归实现原理

2.1 栈（Stack）数据结构

栈是一种遵循后进先出（Last In First Out，LIFO）原则的数据结构。形象地说，栈就像一个只有一个出入口的弹匣，最后压入弹匣的子弹会最先被射出 。在程序中，栈通常有两个基本操作：入栈（Push）和出栈（Pop）。入栈操作是将元素添加到栈的顶部，而出栈操作则是从栈顶移除元素。例如，在一个空栈中依次入栈元素 1、2、3，此时栈的状态从栈底到栈顶为 1、2、3；当进行出栈操作时，首先弹出的是 3，然后是 2，最后是 1 。

递归遍历二叉树时，系统会自动维护一个调用栈，用于保存函数调用的上下文信息，包括参数、局部变量和返回地址等。而在非递归实现中，我们手动使用栈来模拟这个调用栈。通过栈，我们可以保存待处理的节点，以便在合适的时候访问它们。例如，在遍历二叉树的过程中，当遇到一个节点时，我们可以将其入栈，然后继续处理其左子树；当左子树处理完毕后，再从栈中取出该节点，处理其右子树。这样，栈就帮助我们实现了对二叉树节点的有序访问，避免了递归调用带来的栈溢出风险和高空间复杂度问题。

2.2 前序遍历的非递归实现

前序遍历的非递归实现步骤如下：

1. 首先创建一个空栈，用于存储节点，同时设置一个指针指向根节点。

2. 当指针不为空或者栈不为空时，进入循环：

• 如果指针不为空，说明当前有节点需要处理。将当前节点入栈，并访问该节点（例如打印节点的值），然后将指针指向当前节点的左子节点。这一步模拟了递归调用中先访问根节点，再递归访问左子树的过程。

• 如果指针为空，说明当前节点的左子树已经处理完毕。此时从栈顶取出一个节点，将指针指向该节点的右子节点，继续处理右子树。这对应于递归调用中左子树处理完后，处理右子树的操作。

下面是前序遍历非递归实现的代码示例（以Python为例）：

# 定义二叉树节点类
class TreeNode:def __init__(self, val=0, left=None, right=None):self.val = valself.left = leftself.right = rightdef preorderTraversal(root):if not root:return []result = []stack = [root]while stack:node = stack.pop()result.append(node.val)# 先将右子节点入栈，再将左子节点入栈，这样出栈时先处理左子树if node.right:stack.append(node.right)if node.left:stack.append(node.left)return result# 示例二叉树
#       1
#      / \
#     2   3
#    / \
#   4   5
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)print(preorderTraversal(root))  # 输出: [1, 2, 4, 5, 3]

结合上述代码和示例二叉树分析执行过程：

1. 初始化时，将根节点 1 入栈，此时栈中元素为 [1] 。

2. 从栈中弹出节点 1，访问其值 1 并加入结果列表，然后将节点 1 的右子节点 3 和左子节点 2 依次入栈，此时栈中元素为 [3, 2]，结果列表为 [1] 。

3. 弹出节点 2，访问其值 2 并加入结果列表，再将节点 2 的右子节点 5 和左子节点 4 依次入栈，此时栈中元素为 [3, 5, 4]，结果列表为 [1, 2] 。

4. 弹出节点 4，访问其值 4 并加入结果列表，由于节点 4 没有子节点，继续下一次循环。此时栈中元素为 [3, 5]，结果列表为 [1, 2, 4] 。

5. 弹出节点 5，访问其值 5 并加入结果列表，节点 5 也没有子节点，继续循环。此时栈中元素为 [3]，结果列表为 [1, 2, 4, 5] 。

6. 弹出节点 3，访问其值 3 并加入结果列表，节点 3 没有子节点，栈为空，循环结束，最终结果列表为 [1, 2, 4, 5, 3]，完成前序遍历。

2.3 中序遍历的非递归实现

中序遍历非递归实现的步骤如下：

1. 同样先创建一个空栈，设置指针指向根节点。

2. 当指针不为空或者栈不为空时，执行以下操作：

• 如果指针不为空，将当前节点入栈，然后将指针指向其左子节点。这一步是为了先将左子树的所有节点入栈，因为中序遍历是先访问左子树。

• 当指针为空时，说明当前节点的左子树已经全部入栈。从栈顶取出一个节点，访问该节点（例如打印节点的值），然后将指针指向该节点的右子节点，继续处理右子树。

中序遍历非递归实现的代码示例（Python）：

def inorderTraversal(root):if not root:return []result = []stack = []current = rootwhile current or stack:while current:stack.append(current)current = current.leftcurrent = stack.pop()result.append(current.val)current = current.rightreturn resultprint(inorderTraversal(root))  # 输出: [4, 2, 5, 1, 3]

与前序遍历非递归实现相比，主要区别在于访问节点的时机。前序遍历是在节点入栈时就访问，而中序遍历是在节点从栈中弹出时访问。例如，在上述示例二叉树中，中序遍历首先将节点 1 的左子树节点 2 和节点 2 的左子节点 4 依次入栈，当节点 4 的左子节点为空时，开始从栈中弹出节点 4 并访问，然后处理节点 4 的右子树（为空），接着弹出节点 2 并访问，再处理节点 2 的右子树，以此类推，按照左 - 根 - 右的顺序完成遍历。

2.4 后序遍历的非递归实现

后序遍历非递归实现的难点在于需要确保左子树和右子树都访问完才能访问根节点。常见的实现思路有两种：一种是使用标记位，另一种是使用两个栈。

使用标记位的实现思路：为每个节点添加一个标记位，用于表示该节点的右子树是否已经访问过。

1. 创建一个空栈，设置指针指向根节点。

2. 当指针不为空或者栈不为空时，执行以下操作：

• 如果指针不为空，将当前节点连同其标记位（初始为 False）入栈，然后将指针指向其左子节点。

• 当指针为空时，查看栈顶节点。如果栈顶节点的右子树为空或者右子树已经访问过（标记位为 True），则弹出栈顶节点并访问，同时更新上一个访问的节点为该节点；否则，将栈顶节点的标记位设为 True，将指针指向栈顶节点的右子节点。

使用两个栈的实现思路：

1. 创建两个栈，一个用于存储节点（栈 1），另一个用于存储最终遍历结果（栈 2）。

2. 将根节点入栈 1。

3. 当栈 1 不为空时，执行以下操作：

• 从栈 1 中弹出一个节点，将其入栈 2。

• 如果该节点有左子节点，将左子节点入栈 1；如果有右子节点，将右子节点入栈 1。这一步保证了栈 2 中节点的顺序是根 - 右 - 左。

4. 最后，依次从栈 2 中弹出节点，得到的顺序就是后序遍历的结果（左 - 右 - 根）。

下面是使用标记位的后序遍历非递归实现代码示例（Python）：

def postorderTraversal(root):if not root:return []result = []stack = []current = rootlast_visited = Nonewhile current or stack:while current:stack.append((current, False))current = current.leftcurrent, visited = stack.pop()if not visited and current.right:stack.append((current, True))current = current.rightelse:result.append(current.val)last_visited = currentcurrent = Nonereturn resultprint(postorderTraversal(root))  # 输出: [4, 5, 2, 3, 1]

以使用标记位的代码为例分析执行逻辑：

1. 初始化时，指针指向根节点 1，将 (1, False) 入栈，此时栈中元素为 [(1, False)] 。

2. 指针指向节点 1 的左子节点 2，将 (2, False) 入栈，接着指针指向节点 2 的左子节点 4，将 (4, False) 入栈。此时栈中元素为 [(4, False), (2, False), (1, False)] 。

3. 由于节点 4 没有左子节点，从栈中弹出 (4, False) ，因为右子节点为空，直接访问节点 4 并加入结果列表，更新 last_visited 为 4，current 设为 None。此时栈中元素为 [(2, False), (1, False)] ，结果列表为 [4] 。

4. 因为 current 为 None，查看栈顶元素 (2, False) ，由于右子节点 5 不为空且未访问（标记位为 False），将 (2, True) 重新入栈，指针指向节点 5，将 (5, False) 入栈。此时栈中元素为 [(5, False), (2, True), (1, False)] 。

5. 节点 5 没有左子节点，弹出 (5, False) ，右子节点为空，访问节点 5 并加入结果列表，更新 last_visited 为 5，current 设为 None。此时栈中元素为 [(2, True), (1, False)] ，结果列表为 [4, 5] 。

6. 查看栈顶元素 (2, True) ，右子树已访问，弹出并访问节点 2，更新 last_visited 为 2，current 设为 None。此时栈中元素为 [(1, False)] ，结果列表为 [4, 5, 2] 。

7. 查看栈顶元素 (1, False) ，右子节点 3 不为空且未访问，将 (1, True) 重新入栈，指针指向节点 3，将 (3, False) 入栈。此时栈中元素为 [(3, False), (1, True)] 。

8. 节点 3 没有左子节点，弹出 (3, False) ，右子节点为空，访问节点 3 并加入结果列表，更新 last_visited 为 3，current 设为 None。此时栈中元素为 [(1, True)] ，结果列表为 [4, 5, 2, 3] 。

9. 查看栈顶元素 (1, True) ，右子树已访问，弹出并访问节点 1，加入结果列表，栈为空，循环结束，最终结果列表为 [4, 5, 2, 3, 1]，完成后序遍历。

三、复杂度分析

3.1 时间复杂度

对于前序遍历的非递归实现，每个节点会被访问一次且仅一次，入栈和出栈操作也各进行一次。在遍历过程中，我们通过栈来模拟递归调用，确保每个节点都能被正确处理。无论是在平衡二叉树还是非平衡二叉树中，都需要对每一个节点进行操作，因此时间复杂度为 O (n)，其中 n 是二叉树的节点数。

中序遍历非递归实现同样如此，在从根节点开始沿着左子树不断入栈，以及从栈中弹出节点并处理其右子树的过程中，每个节点都会被访问一次。在最坏情况下，例如二叉树是一条链的情况，依然需要遍历所有节点，所以时间复杂度也是 O (n) 。

后序遍历的非递归实现，无论是使用标记位还是两个栈的方法，也都是对每个节点进行一次访问，并且每个节点最多入栈和出栈两次（在使用标记位时，某些节点可能会重新入栈一次）。在遍历左子树、右子树和访问根节点的过程中，不会遗漏任何节点，所以时间复杂度同样为 O (n) 。

3.2 空间复杂度

空间复杂度主要考虑栈的最大深度。在平均情况下，对于平衡二叉树，栈的深度为 O (log n)，因为平衡二叉树的高度与节点数的对数成正比 。然而，在最坏情况下，当二叉树退化为一条链时，栈的深度会达到 O (n)，因为此时需要将所有节点依次入栈，以模拟递归调用的过程。例如，对于一个只有右子节点的单链二叉树，从根节点开始，每个节点都要入栈，直到最后一个节点，此时栈的大小与节点数相同。所以，二叉树遍历非递归实现的空间复杂度在最坏情况下为 O (n) 。

四、实际应用场景

4.1 编译器中的语法分析

在编译器的工作流程中，语法分析是一个至关重要的阶段。编译器首先通过词法分析器将输入的源代码分解成一个个的单词（Token），例如变量名、关键字、运算符等 。接着，语法分析器利用这些 Token 构建抽象语法树（AST），而二叉树遍历在这个过程中发挥着核心作用。

以一个简单的算术表达式 (3 + 5) * 2 为例，语法分析器会将其构建成一棵抽象语法树。在这棵树中，根节点可能是乘法运算符 *，其左子树是表示加法运算 3 + 5 的子树，右子树是表示常量 2 的节点。其中，加法子树的根节点是加法运算符 +，左子节点是常量 3，右子节点是常量 5。

通过前序遍历这棵抽象语法树，编译器可以按照运算符的优先级顺序生成中间代码。在前序遍历中，首先访问根节点 *，这意味着先处理乘法运算；然后访问左子树的根节点 +，处理加法运算；最后访问右子树的常量 2。这样，就可以根据遍历结果生成类似于 (3 + 5) 2 * 的中间代码形式，方便后续的代码生成和优化阶段使用 。

中序遍历抽象语法树则可以得到中缀表达式，对于上述例子，中序遍历的结果是 3 + 5 * 2，这与原始的表达式形式一致（除了括号），可以用于语法检查和表达式的显示等操作。

后序遍历在代码生成阶段也有重要应用。以后序遍历上述抽象语法树为例，得到的结果是 3 5 + 2 *，这是后缀表达式（逆波兰表达式）的形式。后缀表达式非常适合计算机进行求值计算，在代码生成阶段，可以根据后缀表达式更方便地生成目标机器代码，因为它消除了运算符优先级和括号的影响，计算机可以按照顺序依次处理操作数和运算符 。

4.2 数据库索引结构

在数据库中，B - 树和 B + 树是常见的索引结构，它们都与二叉树有着密切的关系，并且在查询数据时依赖于类似二叉树遍历的操作。

以 B + 树为例，B + 树是一种多路平衡查找树，它的非叶子节点只存储键值，用于索引；叶子节点存储所有数据，并通过链表连接 。当进行数据查询时，例如要查找某个特定键值对应的数据，数据库系统会从 B + 树的根节点开始，按照键值的比较进行类似二叉树遍历的过程。

假设我们有一个按照学号建立 B + 树索引的学生信息表。当查询学号为 1005 的学生信息时，从根节点开始，根节点可能包含多个键值范围，通过比较 1005 与这些键值，确定应该进入哪个子节点继续查找。如果根节点的键值范围是 [1000, 1010], [1011, 1020] 等，由于 1005 在 [1000, 1010] 范围内，就进入对应的子节点。在子节点中继续进行类似的比较和选择，直到到达叶子节点。在叶子节点中，通过链表顺序查找或者二分查找（如果叶子节点数据有序存储支持二分查找），最终找到学号为 1005 的学生信息 。

这个过程类似于二叉树的中序遍历思想，不断地在树的节点中进行比较和选择，沿着合适的分支向下查找，直到找到目标数据。与二叉树不同的是，B + 树每个节点可以有多个子节点，这使得树的高度相对较低，从而减少了磁盘 I/O 操作，提高了查询效率。在大规模数据库中，减少磁盘 I/O 对于性能提升至关重要，B + 树这种结构和遍历方式很好地满足了这一需求 。

4.3 非递归实现的要点和优势总结

实现过程中，栈的运用是核心要点之一。通过巧妙地利用栈的后进先出特性，我们能够模拟递归调用的过程，从而实现对二叉树节点的有序访问 。

对于前序遍历的非递归实现，我们先将根节点入栈，然后在循环中不断弹出栈顶节点并访问，接着将其右子节点和左子节点依次入栈，确保先处理左子树。中序遍历则是先沿着左子树不断将节点入栈，当左子树处理完毕后，从栈中弹出节点并访问，再处理其右子节点 。后序遍历的非递归实现相对复杂，无论是使用标记位还是两个栈的方法，都是为了确保在左子树和右子树都访问完后才访问根节点。

与递归实现相比，非递归实现具有诸多优势: 在空间复杂度方面，递归实现依赖系统栈，在处理深度较大的二叉树时容易导致栈溢出，而非递归实现通过手动管理栈，可以更有效地控制内存使用，避免栈溢出问题 。在执行效率上，递归调用存在一定的时间开销，包括函数调用和返回操作，而非递归实现减少了这些额外开销，在大规模数据处理时性能更优。此外，非递归实现的代码更便于调试，因为我们可以清晰地看到栈的操作过程，更容易定位和解决问题 。

That’s all, thanks for reading!
觉得有用就点个赞、收进收藏夹吧！关注我，获取更多干货～