### Python 实现二叉树 #### 创建节点类 为了构建一棵二叉树，首先定义一个表示单个节点的类 `TreeNode`。该类包含三个属性：存储数据项的数据成员、指向左子节点的指针以及指向右子节点的指针。 ```python class TreeNode: def __init__(self, value=0, left=None, right=None): self.value = value self.left = left self.right = right ``` #### 插入新节点的方法 下面是一个向二叉搜索树中插入新节点的例子。如果当前节点为空，则创建一个新的根节点；如果不为空，则比较待插入值与现有节点值大小来决定往哪个方向继续寻找合适的位置[^1]。 ```python def insert_into_binary_search_tree(root, new_value): if root is None: return TreeNode(new_value) if new_value < root.value: root.left = insert_into_binary_search_tree(root.left, new_value) elif new_value > root.value: root.right = insert_into_binary_search_tree(root.right, new_value) return root ``` #### 遍历方法 遍历是指按照某种顺序访问每一个节点一次的过程。这里展示三种常见的遍历方式——前序遍历(pre-order traversal)，中序遍历(in-order traversal) 和 后序遍历(post-order traversal)： ```python def pre_order_traversal(node): if node: print(node.value, end=' ') pre_order_traversal(node.left) pre_order_traversal(node.right) def in_order_traversal(node): if node: in_order_traversal(node.left) print(node.value, end=' ') in_order_traversal(node.right) def post_order_traversal(node): if node: post_order_traversal(node.left) post_order_traversal(node.right) print(node.value, end=' ') ``` 这些函数可以用来打印出整棵树中的所有元素，也可以修改为返回列表形式的结果以便进一步处理。