首页先序遍历二叉树输出

先序遍历二叉树输出

时间: 2025-06-01 13:15:17 浏览: 8

### 二叉树先序遍历的实现与解释先序遍历（Pre-order Traversal）是一种深度优先搜索策略，其访问顺序为根节点 -> 左子树 -> 右子树[^1]。在实际应用中，可以通过递归或非递归的方式实现。 #### 递归实现递归方法是最直观的实现方式，它直接按照先序遍历的定义进行操作。以下是递归实现的代码示例： ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right def pre_order_traversal_recursive(root): if root is None: return [] result = [root.value] # 访问根节点 result += pre_order_traversal_recursive(root.left) # 遍历左子树 result += pre_order_traversal_recursive(root.right) # 遍历右子树 return result ``` #### 非递归实现非递归方法使用栈来模拟递归调用的过程。通过显式地维护一个栈，可以避免函数调用开销。以下是非递归实现的代码示例： ```python def pre_order_traversal_iterative(root): if root is None: return [] stack, result = [root], [] while stack: node = stack.pop() result.append(node.value) # 访问根节点 if node.right: # 先将右子节点入栈 stack.append(node.right) if node.left: # 再将左子节点入栈 stack.append(node.left) return result ``` 两种方法的时间复杂度均为 O(n)，其中 n 是二叉树中的节点数[^2]。递归方法更加简洁易懂，但可能会因为递归深度过大而导致栈溢出问题。非递归方法虽然稍显复杂，但更适用于处理大规模数据。

阅读全文