### 使用 Python 实现二叉树的创建与遍历 #### 1. 定义二叉树节点 首先，定义一个 `Node` 类来表示二叉树中的每个节点。该类包含三个属性：`_data` 存储节点值，`_left` 和 `_right` 分别指向左子树和右子树。 ```python class Node: def __init__(self, data=None, left=None, right=None): self._data = data self._left = left self._right = right ``` --- #### 2. 创建二叉树 通过递归的方式构建二叉树。以下代码展示了一个通用方法来根据列表创建二叉树： ```python def create_tree(data_list, index=0): if index >= len(data_list) or data_list[index] is None: return None # 创建当前节点 node = Node(data=data_list[index]) # 递归创建左子树和右子树 node._left = create_tree(data_list, 2 * index + 1) node._right = create_tree(data_list, 2 * index + 2) return node ``` 在这个函数中，`data_list` 是用来描述二叉树的一个列表，其中索引关系决定了父子节点之间的连接方式[^2]。 --- #### 3. 前序遍历 前序遍历按照“根-左-右”的顺序访问节点。以下是其实现代码： ```python def preorder_traversal(node): if node is not None: print(node._data, end=" ") # 首先访问根节点 preorder_traversal(node._left) # 然后递归访问左子树 preorder_traversal(node._right) # 最后递归访问右子树 ``` --- #### 4. 中序遍历 中序遍历按照“左-根-右”的顺序访问节点。以下是其实现代码： ```python def inorder_traversal(node): if node is not None: inorder_traversal(node._left) # 首先递归访问左子树 print(node._data, end=" ") # 然后访问根节点 inorder_traversal(node._right) # 最后递归访问右子树 ``` --- #### 5. 后序遍历 后序遍历按照“左-右-根”的顺序访问节点。以下是其实现代码： ```python def postorder_traversal(node): if node is not None: postorder_traversal(node._left) # 首先递归访问左子树 postorder_traversal(node._right) # 然后递归访问右子树 print(node._data, end=" ") # 最后访问根节点 ``` --- #### 测试代码 下面是一段完整的测试代码，演示如何创建一棵简单的二叉树并执行三种遍历操作： ```python if __name__ == "__main__": # 数据列表表示二叉树结构 data_list = ['a', 'b', 'e', 'c', 'd', None, 'f'] # 创建二叉树 root = create_tree(data_list) # 执行前序遍历 print("Preorder traversal:") preorder_traversal(root) print() # 执行中序遍历 print("Inorder traversal:") inorder_traversal(root) print() # 执行后序遍历 print("Postorder traversal:") postorder_traversal(root) print() ``` 运行这段代码将会输出对应的前序、中序和后序遍历结果[^3]。 --- ### 总结 上述代码实现了二叉树的创建及其三种基本遍历方法（前序、中序、后序）。每种遍历都采用了递归的方式来实现，逻辑清晰且易于理解。 ---