首页先序遍历和中序遍历后序遍历

先序遍历和中序遍历后序遍历

时间: 2025-01-03 21:43:25 浏览: 47

### 二叉树遍历方法解释 #### 先序遍历 (Preorder Traversal) 先序遍历遵循 NLR 的顺序，即首先访问根节点(N)，接着递归地访问左子树(L)，最后递归地访问右子树(R)[^2]。对于如下所示的简单二叉树： ``` A / \ B C / \ D E ``` 其先序遍历的结果将是 `A, B, D, E, C`。 ```python def preorder_traversal(root): result = [] def traverse(node): if node is None: return result.append(node.val) # 访问当前节点 traverse(node.left) # 遍历左子树 traverse(node.right) # 遍历右子树 traverse(root) return result ``` #### 中序遍历 (Inorder Traversal) 中序遍历采用 LNR 的模式执行，意味着会先递归处理左子树(L)，之后访问根节点(N)，最终递归处理右子树(R)[^1]。以上述相同的二叉树为例，其中序遍历序列应为 `D, B, E, A, C`。 ```python def inorder_traversal(root): result = [] def traverse(node): if node is not None: traverse(node.left) # 处理左子树 result.append(node.val) # 访问当前节点 traverse(node.right) # 处理右子树 traverse(root) return result ``` #### 后序遍历 (Postorder Traversal) 后序遍历按照 LRN 来操作，具体来说就是先递归探索左子树(L)，再递归探索右子树(R)，最后才访问根节点(N)。同样结构下的二叉树，后序遍历会产生这样的输出：`D, E, B, C, A`。 ```python def postorder_traversal(root): result = [] def traverse(node): if node is not None: traverse(node.left) # 左子树 traverse(node.right) # 右子树 result.append(node.val) # 当前节点 traverse(root) return result ```

阅读全文