后序遍历与非递归实现

引言

在计算机科学中，树是一种常用的数据结构，其中最常见的是二叉树。对二叉树进行后序遍历（左子树 -> 右子树 -> 根节点）是基本操作之一。通常的后序遍历使用递归方法来实现，但也可以通过非递归的方式完成，通常借助栈或迭代的方法。

后序遍历的意义

在某些情况下，特别是当我们不希望使用额外的函数调用堆栈时（例如在某些嵌入式系统中），非递归后序遍历显得非常有用。接下来我们探讨如何利用栈来实现这个目标。

非递归后序遍历算法原理

为了实现非递归后序遍历，我们可以结合使用两个栈：一个用于迭代访问节点，另一个用作辅助存储遍历结果。具体步骤如下：

1. 初始化：创建一个根节点指向的栈，并将根节点压入栈中。
2. 遍历循环：
   • 当栈不为空时进行以下操作：
     1. 弹出当前栈顶节点。
     2. 将该节点添加到结果数组（或列表）中。注意，这个步骤在常规后序遍历中通常是在弹出之前执行的。
     3. 如果当前节点有左孩子，则将左孩子压入第一个栈。
     4. 如果当前节点有右孩子，则将右孩子压入第一个栈。

通过上述方法，我们能够逆向地访问每个节点的所有子节点。为了确保正确的后序遍历顺序，在添加根节点到结果数组之前需要先处理其左右子树。

具体实现代码

下面是一个使用Python语言的非递归后序遍历二叉树的具体实现：

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

def postorderTraversal(root):
    if not root:
        return []
    
    result = []  # 用于存储结果的列表
    stack1 = [root]  # 主栈，用于遍历节点
    stack2 = []      # 辅助栈
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)

    # 从辅助栈中弹出所有节点，并加入结果列表
    while stack2:
        result.append(stack2.pop().val)
    
    return result

# 示例用法
root = TreeNode(3)
root.left = TreeNode(9)
root.right = TreeNode(20)
root.right.left = TreeNode(15)
root.right.right = TreeNode(7)

print(postorderTraversal(root))  # 输出: [9, 15, 7, 20, 3]

总结

非递归实现后序遍历的方法提供了一种替代递归方法的方式，特别是在栈大小有限制的环境中。通过巧妙地使用两个栈，我们可以保证按照正确的顺序访问每个节点，并将它们添加到最终的结果列表中。

这种方法不仅适用于二叉树，还可以扩展到更复杂的多叉树结构，展现出在实际应用中的灵活性和强大功能。