实现树结构的基本算法和相应的数据结构( 五 ) _树结构

def _subtreeInsert(self, root, item):if root is None:# inserting into empty treereturn TreeNode(item)# the item becomes the new tree rootif item == root.item:raise ValueError("Inserting duplicate item")if item < root.item:# modify left subtreeroot.left = self._subtreeInsert(root.left, item)else:# modify right subtreeroot.right = self._subtreeInsert(root.right, item)return root # original root is root of modified tree到目前为止，我们可以创建一个BST对象并且添加元素到这个对象里了。因此，我们能够使用某种方法来查找树里的元素了。我们曾经讨论过基本的搜索算法，在这个算法里应该能够很容易地实现。因为它只需要一个循环来从根节点向下遍历整个树，直到找到这个目标元素或者到达整个树的底部：
def find(self, item):""" Search for item in BSTpost: Returns item from BST if found, None otherwise"""node = self.rootwhile node is not None and not(node.item == item):if item < node.item:node = node.leftelse:node = node.rightif node is None:return Noneelse:return node.item你可能会想知道为什么这个方法会从树结构里返回元素，而不是仅仅返回一个布尔值来表示找到了这个元素。这是为了简单起见，目前为止我们所用的所有插图都使用了数字来代表数据值。然而，我们可以在二叉搜索树里存储任意类型的对象，对这个类型唯一的要求是对象具有可比性。一般来说，两个对象可能相等（==），但它们不一定是相同的。稍后，我们将会看到如何利用这个属性，来将我们的BST转换为类似于字典的对象。
为了抽象数据类型的完整，我们还应该在BST类里添加一个用来删除元素的方法。从二叉搜索树中删除特定元素有点麻烦，我们有很多不同的情况需要考虑。让我们从简单的情况开始：如果要删除的节点是叶节点，我们可以简单地通过把它的父节点里的引用设置为None来将这个节点从树结构里删除。但是，如果要删除的节点有子节点应该怎么办？如果这个需要被删除的节点只有一个子节点的话，我们需要做的工作仍然很简单。我们可以简单地在被删除节点的父节点里把用来指向它的引用设置为它的子节点就行了。图7.7所示为被删除节点的左子节点被提升到了它的父节点的左子节点的情况。你可能也希望研究下其他只有单个子节点的情况（还有3个）来向自己证明，这个方式是正确的。

文章插图

图7.7　从二叉搜索树中删除4
现在，我们继续讨论被删除的节点有两个子节点的情况，这个时候应该怎么做呢？我们不能随便选任意一个子节点来占据被删除节点的位置，因为这可能会让另一个子节点的链接出现问题。这种困境的一个解决方案是：因为我们需要一个节点来维护整个树的结构，所以就简单地把这个节点留在那里就行了。我们可以通过替换节点里的数据，而不是删除这个节点来达到这个目标。因此，我们只需要找到一个可以被方便地删除的节点，然后把这个节点的值传输到目标节点里；与此同时，让这个树还能够保持树的二分查找属性。
让我们来考虑图7.8中左边的这个树。假设我们要从这个树里删除6 。这个树里还有什么值可以被放在这个位置呢？可以发现，如果在这个节点里放置5或7的话，这个二叉搜索树将会继续保持二分查找属性。一般来说，将被删除节点里的元素替换为其直接前序节点或者直接后序节点都是正确的操作，这是因为，这些节点里的值都保证了这个节点与树里的其余节点的关系保持相同。假设我们决定使用直接前序，那么，我们将会把这个值放入被删除的节点里，然后从树里删除这个前序节点就行了。这样的操作，将会让我们得到图7.8右边所展示的树。

文章插图

图7.8　从二叉搜索树中删除6
在这个时候，你可能会担心如何删除这个前序节点。难道这个操作不是和删除原来那个需要被删除的节点一样，还是那么难吗？幸运的是，事实上，并不会这么困难。前序节点里的值始终是需要被删除的节点的左子树里的最大值。很明显，要找到二叉搜索树里包含最大值的节点，我们只需要沿着树，并且始终选择右子树那个链接就行了。当我们用完了所有的链接之后，我们就会停在最大节点上。这也就意味着：前序节点必然有一个空的右子树。因此，我们总是可以通过简单地提升它的左子树来删除这个节点。