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

# BST.pyfrom TreeNode import TreeNodeclass BST(object):def __init__(self):"""create empty binary search treepost: empty tree created"""self.root = None现在，让我们来解决把元素添加到二叉搜索树这个问题。一次只添加一个叶节点来生成一个树很容易实现。这个实现的一个关键点是，在给定的现有二叉搜索树里，有且只有一个位置可以被用来放新插入的元素。让我们来考虑一个例子。假设我们想在图7.6所示的二叉搜索树中插入5 。那么，从根节点6开始的话，我们可以知道5必须进入左子树。这个左子树的根的值是2，所以我们继续进入它的右子树。这个子树的根的值是4，因此我们将继续进入它的右子树。而这个时候，这个右子树是空的。也就是说，应该在这个地方插入5作为新的叶节点。

文章插图

图7.6　插入二叉搜索树的示例
我们可以使用迭代或者递归的方法来实现这个基本的插入算法。无论使用哪种方式，我们都会从树的顶部开始，不断地向下执行，并且根据需要来决定是去左子树还是右子树，直到找到新元素应该存放的位置。和其他链式结构的算法相同的是，我们需要在整个结构为空的时候，特别注意一下特殊情况。这是因为，在这种情况下，相关的操作需要我们去更改根节点的实例变量。这是算法的一个版本，它使用循环来向下遍历整个树结构：

def insert(self, item):"""insert item into binary search treepre: item is not in selfpost: item has been added to self"""if self.root is None:# handle empty tree caseself.root = TreeNode(item)else:# start at rootnode = self.root# loop to find the correct spot (break to exit)while True:if item == node.item:raise ValueError("Inserting duplicate item")if item < node.item:# item goes in left subtreeif node.left is not None:# follow existing subtreenode = node.leftelse:# empty subtree, insert herenode.left = TreeNode(item)breakelse:# item goes in right subtreeif node.right is not None: # follow existing subtreenode = node.rightelse:# empty subtree, insert herenode.right = TreeNode(item)break

这段代码鉴于它的嵌套决策结构，看起来相当复杂。但是，跟踪代码的话，你应该不会有太多的麻烦。代码里需要注意的是，我们有一个保证这个元素在这个树里不存在的先验条件。一个纯粹二叉搜索树是不允许一个值有多个副本的，因此我们会去检查这个条件，在这个树结构里如果已经存在了相同的元素就抛出异常。假如想要扩展这个设计，让它允许出现多个值的话，只需要轻松地在每个节点中都保留已添加的值的次数就可以了。
随着这个算法的出现，为了能够让你记忆得更清晰，我们还可以再考虑一下如何使用递归来解决这个问题。我们在前面曾经说过，树结构是一种自然递归的数据结构，但是我们的BST类并不是一个真正的递归结构。但是，树的互相链接节点本身的结构是递归的。因此，我们可以认为树里的任何一个节点都是它的子树的根，并且，它本身会包含两个更小的子树。当然，None值代表着这个子树为空。有了这样的点子，我们就能够很容易地将插入算法转换为对子树进行操作的递归方法。我们将会按照这个设计，写一个递归的辅助方法，通过调用这个辅助方法来执行插入操作。这样的话，插入方法本身将会非常小：

def insert_rec(self, item):"""insert item into binary search treepre: item is not in selfpost: item has been added to self"""self.root = self._subtreeInsert(self.root, item)

清楚地了解_subtreeInsert做了什么是非常重要的。可以看到，这个方法将会接收一个节点和需要被插入的元素（item）；同时，这个节点将会是被插入的元素所在的子树的根节点。在一开始的情况下，这个节点是完整的树结构（self.root）。_subtreeInsert将会同时包含执行插入的操作，以及会返回可以被用来当作结果的（子）树的根节点。这种方法能够确保我们的插入（insert）操作即使面对的是最初的空树也能工作。因为，在这种情况下，self.root在开始的时候是None（表示空树），而在_subtreeInsert返回了包含这个item（元素）的TreeNode之后，这个节点就会成为这个树的新的根节点。
现在，让我们来编写递归的辅助函数_subtreeInsert吧。函数的参数为我们提供了元素需要被插入的树结构的根节点，在最后，这个函数还需要返回结果树的根节点。整个算法非常简单：如果这个（子）树是空的，我们只需返回包含这个元素的TreeNode就行了。而如果这个树不为空的话，我们递归地把这个元素添加到（相应的）左子树或者右子树里就行了，然后返回这个树的根节点来作为新树的根节点（因为这个节点没有被改变）。下面是完成这些相应工作的代码：