我们将再次使用在子树上的递归来实现这个算法 。我们的方法将与之前一样只包含对递归辅助函数的调用：
def delete(self, item):"""remove item from binary search treepost: item is removed from the tree"""self.root = self._subtreeDelete(self.root, item)_subtreeDelete方法将会是实现删除算法的核心 。它也必须返回被删除元素的子树的根节点：
def _subtreeDelete(self, root, item):if root is None:# Empty tree, nothing to doreturn Noneif item < root.item:# modify leftroot.left = self._subtreeDelete(root.left, item)elif item > root.item:# modify rightroot.right = self._subtreeDelete(root.right, item)else:# delete rootif root.left is None:# promote right subtreeroot = root.rightelif root.right is None:# promote left subtreeroot = root.leftelse:# overwrite root with max of left subtreeroot.item, root.left = self._subtreeDelMax(root.left)return root如果你能够把树结构理解为递归结构的话，这段代码对你来说应该不太难理解 。这个算法里，如果需要被删除的元素是在左子树或者右子树里，我们将会递归调用_subtreeDelete方法来生成修改后的子树 。当（子）树的根节点是这个需要被删除的节点的时候，我们将需要处理3种可能的情况：提升右子树、提升左子树，或者用前序节点的元素来替换当前元素 。最后一种情况实际上可以用另一个递归方法_subtreeDelMax来处理 。这个方法将会查找这个树的最大值，然后删除包含这个值的节点 。这个方法可以像下面的代码片段这样来实现：
def _subtreeDelMax(self, root):if root.right is None:# root is the maxreturn root.item, root.left # return max and promote left subtreeelse:# max is in right subtree, recursively find and delete itmaxVal, root.right = self._subtreeDelMax(root.right)return maxVal, root7.5.3　遍历整个二叉搜索树（BST）现在，我们已经对一组元素进行了有用的抽象 。我们可以向这个集合里添加元素，查找它们，并且删除它们；缺少的只是一些用来迭代这个集合的简单方法 。鉴于二叉搜索树的组织方式，中序遍历会非常实用，因为它将能够按照顺序来输出各个元素 。然而，我们的BST类的用户在编写自己的遍历算法的时候，并不需要知道这个数据结构的内部细节 。好在，我们有多种可能的方法来实现这一目标 。
一种方法是编写简单的遍历算法，将整个树里的元素重新组装成某种序列的形式，比如可以组装成列表或者是队列 。我们可以通过编写递归中序遍历这个算法来轻松地生成Python列表 。这里的代码为BST类提供了asList方法：
def asList(self):"""gets item in in-order traversal orderpost: returns list of items in tree in orders"""items = []self._subtreeAddItems(self.root, items)return itemsdef _subtreeAddItems(self, root, itemList):if root is not None:self._subtreeAddItems(root.left, itemList)itemList.append(root.item)self._subtreeAddItems(root.right, itemList)辅助函数_subtreeAddItems在这里执行的是树的标准的中序遍历，其中对元素的处理只需要把这个元素附加到itemList 。你可以比较一下这段代码和7.2节里的通用遍历算法，从而加深对遍历算法的理解 。我们的asList方法只需创建一个初始列表，然后通过调用_subtreeAddItems来填充这个列表 。通过添加这个方法，我们可以轻松地将BST对象转换为有序列表 。当然，这也就意味着我们可以通过它来遍历集合中的所有元素 。例如，我们可以按照下面这段代码来顺序输出BST对象里的内容：
for item in myBST.asList():print item这个遍历二叉搜索树的方案唯一真正的问题在于，它产生的列表和原本的集合是一样大的 。如果这个集合很大，而同时我们也只是想找到一种能够循环所有元素的方法，那么生成另一个相同大小的集合并不会是一个很好的主意 。
另一个方案是：使用一个被称为访问者模式（visitor pattern）的设计模式来实现 。这种模式的思路是：容器将会提供一个方法，这个方法能够遍历整个数据结构，并且在每个节点上都能够执行一些客户端请求的功能 。在Python里，我们可以通过一个将任意函数作为参数的方法来实现这个模式，这个方法将会把这个函数应用到树结构里的每个节点 。我们还是使用一个递归的辅助方法来实际执行整个遍历过程：
def visit(self, f):"""perform an in-order traversal of the treepost: calls f with each TreeNode item in an in-order traversalorder"""self._inorderVisit(self.root, f)def _inorderVisit(self, root, f):if root is not None:self._inorderVisit(root.left, f)f(root.item)self._inorderVisit(root.right, f)