二叉树遍历-后序-迭代

### 二叉树的先序、中序和后序遍历 #### 定义与基本概念 二叉树是一种常见的数据结构，其遍历方法主要包括 **先序遍历 (Pre-order Traversal)**、**中序遍历 (In-order Traversal)** 和 **后序遍历 (Post-order Traversal)**。这三种遍历方式分别按照不同的访问顺序处理节点 \(N\) 及其左右子节点 \((L, R)\)[^2]。 - **先序遍历**: 节点 \(N\) 的访问优先于其左右子节点，顺序为 \(NLR\)。 - **中序遍历**: 左子节点 \(L\) 首先被访问，接着是当前节点 \(N\), 最后是右子节点 \(R\)，顺序为 \(LNR\)。 - **后序遍历**: 当前节点 \(N\) 是最后一个被访问的，顺序为 \(LRN\)。 #### 示例说明 假设有一个简单的二叉树如下所示： ``` A / \ B C / \ D E ``` 对于上述二叉树，可以得到以下遍历结果： - **先序遍历**: `A -> B -> D -> E -> C` （\(NLR\)） - **中序遍历**: `D -> B -> E -> A -> C` （\(LNR\)） - **后序遍历**: `D -> E -> B -> C -> A` （\(LRN\)） 这些遍历的结果可以通过递归或迭代的方式来实现[^1][^2]。 --- #### 实现代码示例 以下是基于 JavaScript 的二叉树遍历实现代码，涵盖了 Node 类和 BinaryTree 类的设计以及具体的遍历逻辑。 ```javascript // 定义节点类 class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } // 定义二叉树类 class BinaryTree { constructor() { this.root = null; } _insertNode(node, newNode) { if (newNode.value < node.value) { // 插入到左子树 if (!node.left) { node.left = newNode; } else { this._insertNode(node.left, newNode); } } else { // 插入到右子树 if (!node.right) { node.right = newNode; } else { this._insertNode(node.right, newNode); } } } insert(value) { const newNode = new Node(value); if (!this.root) { this.root = newNode; } else { this._insertNode(this.root, newNode); } } _preOrderTraversalNode(node, result) { if (node !== null) { result.push(node.value); // 访问当前节点 this._preOrderTraversalNode(node.left, result); // 先访问左子树 this._preOrderTraversalNode(node.right, result); // 再访问右子树 } } preOrderTraversal() { let result = []; this._preOrderTraversalNode(this.root, result); return result; // 返回先序遍历结果 } _inOrderTraversalNode(node, result) { if (node !== null) { this._inOrderTraversalNode(node.left, result); // 先访问左子树 result.push(node.value); // 访问当前节点 this._inOrderTraversalNode(node.right, result); // 再访问右子树 } } inOrderTraversal() { let result = []; this._inOrderTraversalNode(this.root, result); return result; // 返回中序遍历结果 } _postOrderTraversalNode(node, result) { if (node !== null) { this._postOrderTraversalNode(node.left, result); // 先访问左子树 this._postOrderTraversalNode(node.right, result); // 再访问右子树 result.push(node.value); // 最后访问当前节点 } } postOrderTraversal() { let result = []; this._postOrderTraversalNode(this.root, result); return result; // 返回后序遍历结果 } } // 创建并测试二叉树 const tree = new BinaryTree(); tree.insert(50); tree.insert(30); tree.insert(70); tree.insert(20); tree.insert(40); console.log('先序遍历:', tree.preOrderTraversal()); // 输出: [50, 30, 20, 40, 70] console.log('中序遍历:', tree.inOrderTraversal()); // 输出: [20, 30, 40, 50, 70] console.log('后序遍历:', tree.postOrderTraversal()); // 输出: [20, 40, 30, 70, 50] ``` --- #### 关系分析 通过给定的先序遍历和中序遍历序列，可以唯一确定一棵二叉树，并进一步推导出该树的后序遍历序列[^3]。这是因为： - 先序遍历的第一个元素总是根节点； - 利用根节点可以在中序遍历中划分出左子树和右子树； - 这种分治的思想使得问题能够逐步分解为更小规模的子问题，最终完成整棵树的重建及后续操作。 ---

### 二叉树迭代后序遍历算法实现 #### 背景介绍 二叉树的后序遍历是指按照“左子树 -> 右子树 -> 根节点”的顺序访问二叉树中的所有节点。相比递归方式，迭代方法更复杂一些，因为它需要手动模拟栈的行为来替代函数调用栈的作用。 #### 方法一：双栈法 一种常见的迭代实现方法是使用两个栈完成后序遍历。具体过程如下： 1. 初始化第一个栈 `stack` 并将根节点压入其中。 2. 循环执行以下操作直到 `stack` 为空： - 弹出栈顶元素并将其加入第二个栈 `output_stack` 中。 - 如果弹出的节点有左孩子，则将左孩子压入 `stack`。 - 如果弹出的节点有右孩子，则将右孩子压入 `stack`。 3. 最终从 `output_stack` 中依次弹出元素即为后序遍历结果[^1]。 以下是对应的 Python 实现代码： ```python def postorderTraversal(root): if not root: return [] stack, output_stack = [root], [] while stack: node = stack.pop() output_stack.append(node) if node.left: stack.append(node.left) if node.right: stack.append(node.right) result = [] while output_stack: result.append(output_stack.pop().val) return result ``` #### 方法二：单栈法 另一种更为高效的迭代方法仅需一个栈即可完成。其核心思想是对前序遍历稍作修改，使得访问顺序变为“中->右->左”，最后再反转结果得到真正的后序遍历序列[^4]。 下面是这种方法的具体实现： ```python def postorderTraversal(root): if not root: return [] stack, result = [], [] current_node = root while stack or current_node: if current_node: stack.append(current_node) result.insert(0, current_node.val) # 提前记录中间结点值，并放在最前面 current_node = current_node.right # 先处理右边部分 else: temp = stack.pop() # 出栈后再转向左边继续探索 current_node = temp.left return result ``` #### 方法三：Morris 遍历 (空间优化版) 对于追求极致性能的应用场景来说，还可以采用 Morris 遍历来进一步减少额外内存消耗至常数级别 O(1)[^2]。不过需要注意的是此技术会临时改变原树结构，在实际应用时应谨慎考虑是否适用。 由于篇幅所限这里不再展开讨论具体的实现细节，请参阅相关资料获取更多信息[^3]。 ---