### 二叉树的创建与遍历 #### 定义节点结构 为了构建和操作二叉树，首先定义一个简单的二叉树节点类。每个节点包含数据、指向左子节点的指针以及指向右子节点的指针。 ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right ``` #### 构建二叉树实例 通过给定的数据列表来初始化一棵具体的二叉树： ```python def build_binary_tree(values): if not values: return None root = TreeNode(values.pop(0)) queue = [root] while values: current_node = queue.pop(0) # 左孩子 val_left = values.pop(0) if values else None if val_left is not None: current_node.left = TreeNode(val_left) queue.append(current_node.left) # 右孩子 if values: val_right = values.pop(0) if val_right is not None: current_node.right = TreeNode(val_right) queue.append(current_node.right) return root ``` #### 前序遍历（Preorder Traversal） 前序遍历按照访问根结点->左子树->右子树的方式进行遍历[^1]。 ```python def preorder_traversal(root): result = [] def traverse(node): if node: result.append(node.value) traverse(node.left) traverse(node.right) traverse(root) return result ``` #### 中序遍历（Inorder Traversal） 中序遍历遵循左子树->根结点->右子树这样的顺序来进行访问。 ```python def inorder_traversal(root): result = [] def traverse(node): if node: traverse(node.left) result.append(node.value) traverse(node.right) traverse(root) return result ``` #### 后序遍历（Postorder Traversal） 后序遍历则是先处理两个子树再回到父节点完成最后的操作。 ```python def postorder_traversal(root): result = [] def traverse(node): if node: traverse(node.left) traverse(node.right) result.append(node.value) traverse(root) return result ``` #### 层次遍历（Level Order Traversal） 层次遍历是从上到下逐层读取每一层上的所有元素[^2]。 ```python from collections import deque def level_order_traversal(root): if not root: return [] results = [] q = deque([root]) while q: size = len(q) temp_result = [] for _ in range(size): curr = q.popleft() temp_result.append(curr.value) if curr.left: q.append(curr.left) if curr.right: q.append(curr.right) results.extend(temp_result) return results ```