### 二叉排序树的创建与查找功能实现 #### 创建二叉排序树 二叉排序树（Binary Search Tree, BST）是一种特殊的二叉树，其左子树的所有节点值小于根节点值，右子树的所有节点值大于或等于根节点值。以下是一个使用Python实现二叉排序树的创建代码示例： ```python class TreeNode: def __init__(self, val): self.val = val self.left = None self.right = None class BinarySortTree: def __init__(self): self.root = None def add(self, val): node = TreeNode(val) if self.root is None: self.root = node return queue = [self.root] while queue: temp_node = queue.pop(0) if node.val < temp_node.val: if temp_node.left is None: temp_node.left = node return else: queue.append(temp_node.left) elif node.val >= temp_node.val: if temp_node.right is None: temp_node.right = node return else: queue.append(temp_node.right) # 测试代码 if __name__ == '__main__': bst = BinarySortTree() note_array = [7, 3, 10, 12, 5, 1, 9] for item in note_array: bst.add(item) ``` 此代码通过`add`方法将元素插入到二叉排序树中[^2]。 #### 查找功能实现 在二叉排序树中查找一个特定值时，可以根据节点值与目标值的关系递归地向左子树或右子树进行搜索。以下是查找功能的实现代码： ```python def search(self, key): bt = self.root while bt: entry = bt.val if key < entry: bt = bt.left elif key > entry: bt = bt.right else: return entry return None # 测试查找功能 if __name__ == '__main__': bst = BinarySortTree() note_array = [7, 3, 10, 12, 5, 1, 9] for item in note_array: bst.add(item) result = bst.search(9) print("查找结果：", result) # 输出应为 9 ``` 此代码实现了基于迭代的查找方法，返回找到的节点值或`None`表示未找到[^3]。 ### 中序遍历验证 为了验证二叉排序树是否正确构建，可以使用中序遍历输出所有节点值，其结果应为升序排列： ```python def in_order(self, node): if node is None: return self.in_order(node.left) print(node.val, end=" ") self.in_order(node.right) # 测试中序遍历 if __name__ == '__main__': bst = BinarySortTree() note_array = [7, 3, 10, 12, 5, 1, 9] for item in note_array: bst.add(item) bst.in_order(bst.root) # 输出应为 1 3 5 7 9 10 12 ``` 此代码实现了中序遍历，并打印出所有节点值[^2]。