探索树结构的基本算法及其相关数据结构

目标

• 学习树数据结构的相关术语。
• 了解树数据结构适用的各种应用程序。
• 能够使用链接或者数组来实现树结构，并且熟悉基于树的基本算法。
• 了解二叉搜索树结构以及它的各种操作的效率。
• 通过更多的练习来提高对递归算法的理解。

7.1　概要

到目前为止，我们主要处理的都是像列表、堆栈和队列这样的线性数据结构，它们一般被用来表示序列中的各个元素。在本章中，我们将对之前讲的内容进行拓展，来考虑一个被称为树（tree）的非线性数据结构。树是按照层级的方式来存储数据的，因此，它非常便于对现实世界的层次结构进行建模。例如，你肯定对表示亲属信息的家谱的概念非常熟悉。其他一些关于树的例子有分类学以及公司的汇报结构。

比如说，我们可以使用树来表示生物学家使用的生物类群里的动物。动物可以细分为脊椎动物和无脊椎动物；脊椎动物可以细分为爬行动物、鱼类、哺乳动物等。这个树看起来就会如图7.1所示。层次关系在我们的生活中随处可见，因此，树在许多的应用程序里都被用来作为数据的自然表示。

图7.1　生物学家的生物类群的一部分

可能会让你惊讶的是，事实证明，在实现之前提到普通的序列数据的时候，树也非常有用。在这一章里，我们将看到被称为二叉搜索树（binary search tree）的树结构。它被用来实现一个允许高效插入和删除（类似于链表）的集合，但它同时也能够进行高效的搜索（类似于有序数组）。基于树的数据结构和算法对于高效处理大量的数据（如数据库和文件系统）来说至关重要。

7.2　树的术语

计算机科学家们用一个包含节点的集合（类似于链表中的节点）以及用来连接它们的边（edge）来表示树。图7.2所示为一个包含7个节点的树，其中每个节点都包含着一个整数。图中最顶端的节点被称为根（root）。在这个树里，根包含的数据值是2。一个树只能有一个根。因此，你可以跟随从根开始的边（箭头）到达树里面的任何一个其他节点。

图7.2　二叉树示例

树里的每个节点都可以通过边与它的子节点（child）相连接。在一个普通的树里，一个节点可以有任意数量的子节点，但在这里，让我们先只关注二叉树（binary tree）。在二叉树里，每个节点最多只能有两个子节点。就像图7.2所示的那样，这里所描绘的树就是二叉树。树里面的关系是用家庭和树相关的术语混合起来描述的。根节点有两个子节点：包含7的节点是它的左子节点（left child）；包含6的节点是它的右子节点（right child）。这两个节点也被称为兄弟节点（sibling）。同样地，包含8和4的两个节点也是兄弟节点。那么节点5的父节点（parent）是节点7。同样节点3是节点7的后代（descendant），节点7是节点3的祖先（ancestor）。最后，没有任何子节点的节点则被叫作叶节点（leaf）。节点的深度（depth）代表它与根节点之间的边数。对于根节点来说，它的深度为零。节点7和6的深度为1，节点3的深度则为3。树的高度（height）或者说树的深度（depth）是所有节点里的最大深度。

在满二叉树（full binary tree）中，每个深度级别的每一个可能的位置都有一个节点。在最下面一层，所有的节点都是叶节点（也就是说，所有的叶节点都处于相同的深度，并且每个非叶节点都具有两个子节点）。而完全二叉树是在最深层之外的每一个可能位置都有一个节点，并且在最深的那一层，节点按照从左到右的位置进行排列。可以从满二叉树开始，然后在下一层从左到右添加节点，或者是从右到左删除最后一层的节点来创建完全二叉树。它们两个的示例如图7.3所示。

图7.3　左侧是完全二叉树，右侧是满二叉树

树的每个节点及其后代都可以被视为一个子树（subtree）。比如说，在图7.2里，节点7、5和3组合在一起可以被认为是整个树的一个子树，其中，节点7是这个子树的根节点。通过这种方式来看的话，很明显地，树可以被当作递归结构。一个二叉树可以是空树，也可以是根节点和（可能为空的）左右子树组合起来的树。

和列表类似，树的一个非常有用的操作是遍历。给定一个树，我们需要有一种合适的方式来系统地“走过”这个树的每一个节点。但是和列表不同的是，并没有一个很清晰的遍历树的方法。可以看到，树里的每一个节点都由3部分组成：数据、左子树和右子树。因此，根据我们的侧重点来决定处理这些数据，我们可以有3种不同的遍历顺序来进行选择。如果我们先在根节点处理数据，然后再去处理左右子树的话，我们将会执行被称为前序遍历（preorder traversal）的遍历方法。这个遍历方法之所以叫这个名字，是因为我们首先需要考虑的是根节点里的数据。前序遍历可以很容易地被表示成一个递归算法：

def traverse(tree):    if tree is not empty:        process data at tree’s root     # preorder traversal        traverse(tree’s left subtree)        traverse(tree’s right subtree)

把这个算法应用于图7.2里的树的话，节点将会按照2、7、5、3、6、8、4这样的顺序进行处理。

当然，我们也可以通过简单地移动实际处理数据的位置来修改遍历算法。中序遍历（inorder traversal）将会在处理两个子树之间的时候处理根节点的数据。对于我们那个例子里的树，中序遍历将会按照7、3、5、2、8、6、4的序列来处理节点。你现在可能已经猜到了，后序遍历（postorder traversal）会在处理完两个子树之后再去处理根节点，这就给了我们这样一个顺序：3、5、7、8、4、6、2。

7.3　示例应用程序：表达式树

树在计算机科学中的一个重要应用是存储程序的内部结构。当解释器或编译器分析程序的时候，它会构造一个用来提取程序结构的解析树（parse tree）。例如，考虑这样一个简单的表达式：(2 + 3) * 4 + 5 * 6。这个表达式可以用图7.4所示的树的形式来表现。可以仔细看看，树的层次结构是怎么消除对括号的需要的。表达式的基本操作数是树的叶节点，而运算符是树的内部节点。在树的低层级里的操作必须要被优先执行，只有这样它的结果才能够被用在更高层级的表达式里。很明显，加法2 + 3必须是第一个需要执行的操作，这是因为它出现在了树的最底层。

图7.4　数学表达式的树呈现

将表达式表现为树结构之后，我们就能够做很多有趣的事情了。编译器将遍历这个结构来生成执行计算的一系列机器指令。解释器也会使用这个结构来执行这个表达式。它可以获取两个子节点的值，再使用这个操作来计算出每个节点的值。如果其中的一个或两个子节点本身是一个运算符，那么就必须要先对这个子节点进行计算。一个简单的树的后序遍历就能够被用来计算表达式：

def evaluateTree(tree):    if tree’s root is an operand:        return root data    else:   # root contains an operator        leftValue = evaluateTree(tree’s left subtree)        rightValue = evaluateTree(tree’s right subtree)        result = apply operator at root to leftValue and rightValue        return result

如果你够仔细的话，你会发现这个算法其实是一个用来计算表达式的后缀版本的递归算法。简单地进行后序遍历，这个表达式树会产生这个序列：2 3 + 4 * 5 6 * +。而这正好是我们最初的表达式的后缀表示法。在第5章里，我们用了一个堆栈的算法来计算后缀方程。在这里，通过利用递归隐式地使用计算机的运行时堆栈，我们也完成了相同的任务。顺便说一句，你也可以通过执行恰当的遍历，来获取表达式的前缀版本和中缀版本。当这一切的知识都相互交织在一起的时候，难道不令人着迷吗？

7.4　树的存储方式

现在，你已经了解了树可以做什么，接下来考虑一下树可能的具体存储方式。构建树的一种简单明了的方法是使用链接来表示。和我们处理链表一样，我们可以创建一个类来表示树的节点。每个节点都有一个实例变量来保存对节点数据的引用，同时还有用来引用左右子节点的变量。我们将使用None对象来表示空子树。于是，我们有了这样一个Python的类：

# TreeNode.pyclass TreeNode(object):    def __init__(self, data = None, left=None, right=None):        """creates a tree node with specified data and references to left        and right children"""        self.item = data        self.left = left        self.right = right

使用这个TreeNode类，就能够很方便地直接像镜像一样创建我们已经看到过的二叉树图的链式结构。比如，下面这段代码就可以构建一个包含3个节点的简单树：

left = TreeNode(1)right = TreeNode(3)root = TreeNode(2, left, right)

通过简单地对TreeNode类的构造函数进行组合调用，我们也可以用一行代码来达到相同的目的：

root = TreeNode(2, TreeNode(1), TreeNode(3))

更进一步，我们甚至可以利用这种方法来创建各个树的节点，从而构建出任意复杂度的树结构。下面这段代码可以创建出类似于图7.2这样的树结构：

root = TreeNode(2,           TreeNode(7,               None,               TreeNode(5,                   TreeNode(3),                   None               )           )           TreeNode(6,               TreeNode(8),               TreeNode(4)           )       )

这里使用了缩进来帮助我们直观地让表达式的布局与树的结构相匹配。比如说，从例子里我们可以看到，在根节点（2）的下面，有两个缩进的子树（7和6）。如果你觉得这样并不是很直观的话，可以试着把头侧着看这段代码。

当然，通常来说，我们并不希望像这样通过直接操作TreeNodes类来构建复杂结构。与之相反的是，我们一般会创建一个更高级别的容器类，通过这个容器类来封装树构建的细节，并且提供一组方便的API来操作树结构。容器类的具体设计将取决于我们需要使用树去完成的任务。在下一节里，我们将会看到这方面的例子。

我们应该提到过可以用链接来存储树。但是，这并不是二叉树唯一的实现方式。在某些情况下，使用基于数组/列表的方法来实现树结构也很方便。因为，我们可以通过数组中的位置来隐式地维护节点之间的关系，而不是用显式的链接来存储子节点。

在通过数组来实现树的方案里，我们将会先假设我们总是有一个完整的树。然后，我们可以逐级地将节点放置到数组里去。所以，数组中的第一个单元格将会存储根节点，后面的两个位置将会用来存储根节点的子节点，再接下来的4个位置用来存储孙节点，后面的也以此类推。按照这种方法，对于位置i的节点，总是有：它的左子节点位于位置2*i + 1，它的右子节点将会位于位置2*i + 2；节点i的父节点会位于(i − 1)//2。在这里有一点需要注意的是，对于这些公式来说，每个节点都始终有两个子节点这个假设将会非常重要。为了满足这个假设，你将需要用一些特殊的标记值（例如None）来表示空节点。图7.2中的示例二叉树将会被存储为这样的数组：[2, 7, 6, None, 5, 8, 4, None, None, 3]。如果你想计算简单一点，你可以把数组里的第一个位置（索引0）留空，然后把根节点放在索引1的位置。这样的话，对于位置i的节点，左子节点将会位于2*i，右子节点则会位于2*i + 1，而父节点将会在位置i//2。

树基于数组的实现方法的优点是：它不需要使用内存来显式地存储子节点的链接。但是，它却需要我们为空节点浪费单元格。如果树非常稀疏的话，数组/列表里将会有大量的None元素，而且我们曾经提到过，数组/列表的实现也并不能有效地利用内存。因此，基于这些问题，通过链接来实现树将会更加合适。

7.5　应用：二叉搜索树

在这一节里，我们将会为有序序列构建另一个容器类，通过创建这个容器类，我们会了解到树的一种实现技术。在4.7节里我们讨论过应该如何权衡序列的链接和数组的实现。虽然链表提供了高效的插入和删除操作（因为不用移动元素），但它们不具备高效的搜索操作。而同时，一个有序的数组将能够提供高效的搜索操作（通过二分搜索算法），但是插入和删除操作将会需要Θ (n)的时间。然而在这里，通过使用一种特殊结构的树——二叉搜索树，我们将能够结合这两者的优点。

7.5.1　二分查找属性

二叉搜索树只是一个二叉树，但是这个树中的每一个节点都具有这样一个额外的属性：任意节点的左子树里的值都将小于节点上的值，而它的右子树里的值则会大于节点上的值。图7.5所示为一个二叉搜索树的例子。

图7.5　二叉搜索树的例子

在一个二叉搜索树里搜索元素的话，一般来说将会非常高效。我们将会先从树的根节点开始，并且检查这个节点的数据值。如果根节点的值就是我们要查找的值，那么就完成整个搜索。如果我们搜索的值小于根节点的值，那么我们就能知道，如果这个值存在于树里的话，它只可能在左子树里。类似地，如果我们要搜索的值大于根节点的值，那说明它应该在右子树里。我们可以到相对应的子树里，用相同的规则来继续这个搜索过程，直到我们找到这个元素，或者会找到一个空子树的节点，这说明二叉搜索树里并没有这个值，而如果要把这个值插入到二叉搜索树的话，这个节点正好是这个值所会在的位置。如果这个树相当“平衡”的话，那么对于每个节点来说，我们基本上能够做到将必须要进行比较的元素的数量减少一半。换句话说，我们正在执行二分搜索算法，这也就是为什么它被称为二叉搜索树。

7.5.2　实现一个二叉搜索树

遵循良好的设计原则，我们将编写一个BST（Binary Search Tree）类，这个类将会被用来封装二叉搜索树的所有细节，并且提供一组易于使用的接口。我们的树结构将会维护一组元素，并且允许我们进行添加、删除和搜索特定值的操作。在这里，我们将会使用链接来练习引用相关的知识，当然你也可以很简单地把它转换为之前我们讨论过的基于数组的实现。BST对象将会包含对TreeNode对象的引用，这个TreeNode对象的引用是二叉搜索树的根节点。在最初的时候，树是空树。因此，这个引用将会是None。于是，有了我们的类的构造函数：

# BST.pyfrom TreeNode import TreeNodeclass BST(object):    def __init__(self):        """create empty binary search tree        post: 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 tree        pre: item is not in self        post: item has been added to self"""        if self.root is None:   # handle empty tree case            self.root = TreeNode(item)        else:            # start at root            node = 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 subtree                    if node.left is not None:  # follow existing subtree                        node = node.left                    else:                      # empty subtree, insert here                        node.left = TreeNode(item)                        break                else:                          # item goes in right subtree                    if node.right is not None: # follow existing subtree                        node = node.right                    else:                      # empty subtree, insert here                        node.right = TreeNode(item)                        break

这段代码鉴于它的嵌套决策结构，看起来相当复杂。但是，跟踪代码的话，你应该不会有太多的麻烦。代码里需要注意的是，我们有一个保证这个元素在这个树里不存在的先验条件。一个纯粹二叉搜索树是不允许一个值有多个副本的，因此我们会去检查这个条件，在这个树结构里如果已经存在了相同的元素就抛出异常。假如想要扩展这个设计，让它允许出现多个值的话，只需要轻松地在每个节点中都保留已添加的值的次数就可以了。

随着这个算法的出现，为了能够让你记忆得更清晰，我们还可以再考虑一下如何使用递归来解决这个问题。我们在前面曾经说过，树结构是一种自然递归的数据结构，但是我们的BST类并不是一个真正的递归结构。但是，树的互相链接节点本身的结构是递归的。因此，我们可以认为树里的任何一个节点都是它的子树的根，并且，它本身会包含两个更小的子树。当然，None值代表着这个子树为空。有了这样的点子，我们就能够很容易地将插入算法转换为对子树进行操作的递归方法。我们将会按照这个设计，写一个递归的辅助方法，通过调用这个辅助方法来执行插入操作。这样的话，插入方法本身将会非常小：

    def insert_rec(self, item):        """insert item into binary search tree        pre: item is not in self        post: 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就行了。而如果这个树不为空的话，我们递归地把这个元素添加到（相应的）左子树或者右子树里就行了，然后返回这个树的根节点来作为新树的根节点（因为这个节点没有被改变）。下面是完成这些相应工作的代码：

    def _subtreeInsert(self, root, item):        if root is None:            # inserting into empty tree            return TreeNode(item)   # the item becomes the new tree root        if item == root.item:            raise ValueError("Inserting duplicate item")        if item < root.item:        # modify left subtree            root.left = self._subtreeInsert(root.left, item)        else:                       # modify right subtree            root.right = self._subtreeInsert(root.right, item)        return root # original root is root of modified tree

到目前为止，我们可以创建一个BST对象并且添加元素到这个对象里了。因此，我们能够使用某种方法来查找树里的元素了。我们曾经讨论过基本的搜索算法，在这个算法里应该能够很容易地实现。因为它只需要一个循环来从根节点向下遍历整个树，直到找到这个目标元素或者到达整个树的底部：

    def find(self, item):        """ Search for item in BST            post: Returns item from BST if found, None otherwise"""        node = self.root        while node is not None and not(node.item == item):            if item < node.item:                node = node.left            else:                node = node.right        if node is None:            return None        else:            return node.item

你可能会想知道为什么这个方法会从树结构里返回元素，而不是仅仅返回一个布尔值来表示找到了这个元素。这是为了简单起见，目前为止我们所用的所有插图都使用了数字来代表数据值。然而，我们可以在二叉搜索树里存储任意类型的对象，对这个类型唯一的要求是对象具有可比性。一般来说，两个对象可能相等（==），但它们不一定是相同的。稍后，我们将会看到如何利用这个属性，来将我们的BST转换为类似于字典的对象。

为了抽象数据类型的完整，我们还应该在BST类里添加一个用来删除元素的方法。从二叉搜索树中删除特定元素有点麻烦，我们有很多不同的情况需要考虑。让我们从简单的情况开始：如果要删除的节点是叶节点，我们可以简单地通过把它的父节点里的引用设置为None来将这个节点从树结构里删除。但是，如果要删除的节点有子节点应该怎么办？如果这个需要被删除的节点只有一个子节点的话，我们需要做的工作仍然很简单。我们可以简单地在被删除节点的父节点里把用来指向它的引用设置为它的子节点就行了。图7.7所示为被删除节点的左子节点被提升到了它的父节点的左子节点的情况。你可能也希望研究下其他只有单个子节点的情况（还有3个）来向自己证明，这个方式是正确的。

图7.7　从二叉搜索树中删除4

现在，我们继续讨论被删除的节点有两个子节点的情况，这个时候应该怎么做呢？我们不能随便选任意一个子节点来占据被删除节点的位置，因为这可能会让另一个子节点的链接出现问题。这种困境的一个解决方案是：因为我们需要一个节点来维护整个树的结构，所以就简单地把这个节点留在那里就行了。我们可以通过替换节点里的数据，而不是删除这个节点来达到这个目标。因此，我们只需要找到一个可以被方便地删除的节点，然后把这个节点的值传输到目标节点里；与此同时，让这个树还能够保持树的二分查找属性。

让我们来考虑图7.8中左边的这个树。假设我们要从这个树里删除6。这个树里还有什么值可以被放在这个位置呢？可以发现，如果在这个节点里放置5或7的话，这个二叉搜索树将会继续保持二分查找属性。一般来说，将被删除节点里的元素替换为其直接前序节点或者直接后序节点都是正确的操作，这是因为，这些节点里的值都保证了这个节点与树里的其余节点的关系保持相同。假设我们决定使用直接前序，那么，我们将会把这个值放入被删除的节点里，然后从树里删除这个前序节点就行了。这样的操作，将会让我们得到图7.8右边所展示的树。

图7.8　从二叉搜索树中删除6

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

我们将再次使用在子树上的递归来实现这个算法。我们的方法将与之前一样只包含对递归辅助函数的调用：

    def delete(self, item):        """remove item from binary search tree        post: 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 do           return None        if item < root.item:            # modify left            root.left = self._subtreeDelete(root.left, item)        elif item > root.item:          # modify right            root.right = self._subtreeDelete(root.right, item)        else:                           # delete root            if root.left is None:       # promote right subtree                root = root.right            elif root.right is None:    # promote left subtree                root = root.left            else:                # overwrite root with max of left subtree                root.item, root.left = self._subtreeDelMax(root.left)        return root

如果你能够把树结构理解为递归结构的话，这段代码对你来说应该不太难理解。这个算法里，如果需要被删除的元素是在左子树或者右子树里，我们将会递归调用_subtreeDelete方法来生成修改后的子树。当（子）树的根节点是这个需要被删除的节点的时候，我们将需要处理3种可能的情况：提升右子树、提升左子树，或者用前序节点的元素来替换当前元素。最后一种情况实际上可以用另一个递归方法_subtreeDelMax来处理。这个方法将会查找这个树的最大值，然后删除包含这个值的节点。这个方法可以像下面的代码片段这样来实现：

    def _subtreeDelMax(self, root):        if root.right is None:          # root is the max            return root.item, root.left # return max and promote left subtree        else:            # max is in right subtree, recursively find and delete it            maxVal, root.right = self._subtreeDelMax(root.right)            return maxVal, root

7.5.3　遍历整个二叉搜索树（BST）

现在，我们已经对一组元素进行了有用的抽象。我们可以向这个集合里添加元素，查找它们，并且删除它们；缺少的只是一些用来迭代这个集合的简单方法。鉴于二叉搜索树的组织方式，中序遍历会非常实用，因为它将能够按照顺序来输出各个元素。然而，我们的BST类的用户在编写自己的遍历算法的时候，并不需要知道这个数据结构的内部细节。好在，我们有多种可能的方法来实现这一目标。

一种方法是编写简单的遍历算法，将整个树里的元素重新组装成某种序列的形式，比如可以组装成列表或者是队列。我们可以通过编写递归中序遍历这个算法来轻松地生成Python列表。这里的代码为BST类提供了asList方法：

    def asList(self):        """gets item in in-order traversal order        post: returns list of items in tree in orders"""        items = []        self._subtreeAddItems(self.root, items)        return items    def _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 tree        post: calls f with each TreeNode item in an in-order traversal        order"""        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)

可以看到，这段代码里，f代表着客户端想要应用于BST对象里的每一个元素的任意函数。这个函数通过f(root.item)这一行代码来执行。与之前一样，这段代码只是我们的通用递归遍历算法的一个变体而已。

要使用visit方法，我们只需要构造一个适用于每个元素的函数。比如，假设我们仍然想按照顺序来输出整个BST的内容，我们现在可以通过访问者模式来完成：

def prnt(item):    print item...myBST.visit(prnt)

这里需要注意的一件事是，在调用visit方法的时候，prnt后面并没有跟上一对括号。只有在我们真正单独调用这个函数的时候，才需要加上这对括号。而在此刻，调用visit方法的时候，我们实际上并没有直接调用prnt函数，而是将这个函数对象本身传递给了将会实际执行调用的visit方法。

访问者模式为客户端代码提供了一种很好的方式来执行容器的遍历，而且还包含了一个不需要查看细节的抽象屏障。但是编写一个恰当的函数来进行处理，在有些时候会很麻烦，并且这样的代码并不是很像Python的风格。与我们的其他容器类一样，Python里的理想解决方案是：使用Python的生成器机制来为我们的BST类定义一个迭代器。它的基本思路是：我们将只需要编写一个通用的中序遍历，然后一次一个地yield树结构里的元素。在这个时候，你肯定已经非常清楚这段代码应该怎么写了：

    def __iter__(self):        """in-order iterator for binary search tree"""        return self._inorderGen(self.root)    def _inorderGen(self, root):        if root is not None:            # yield all the items in the left subtree            for item in self._inorderGen(root.left):                yield item            yield root.item            # yield all the items from the right subtree            for item in self._inorderGen(root.right):                yield item

这段代码唯一与之前不一样的地方是生成器函数的递归形式。记住，当你调用生成器的时候，你并没有立刻获得这个元素，而是获得了一个按需提供元素的迭代器对象。例如，为了从左子树里实际得到元素，我们必须要遍历self._inorderGen(root.left)提供的迭代器，然后输出每一个元素。

这样一来，就有了一个可以非常方便地迭代我们的BST容器的方法了。我们按照顺序来输出所有元素的代码不能更简单了：

for item in myBST:    print item

顺便说一句，既然我们有一个BST类的迭代器，那么我们就不再需要单独的asList方法了。Python可以通过代码list(myBST)来使用迭代器从BST对象中生成整个元素的列表。如果能够创建包含BST里所有元素的列表，在为BST类编写单元测试的时候将会特别方便，因为它提供了一种在断言里检查树结构的内容的简单方法。当然，从BST对象中获得的有序列表并不能保证树结构具有正确的形式。为了保证树结构的正确，用另一种遍历方法（前置或后置）将会提供不少帮助。通过检查两个不同的遍历序列来推导出二叉树的真实结构是可行的，因此如果两个遍历都正确的话，那么我们就知道树的结构与我们所期望的结构是相同的了。

7.5.4　二叉搜索树（BST）的运行时分析

在这一部分内容的介绍里，我们提到了二叉搜索树可以非常高效地维护有序集合。我们已经展示了二叉搜索树是如何为我们提供有序集合的了，但是我们还没有仔细检查各个操作的运行时效率。由于许多和树结构相关的算法都是通过递归来编写的，因此分析它们可能会看起来比较麻烦。但是，如果我们只考虑底层结构里发生的事情的话，那么，分析起来就很容易了。

让我们先从遍历整个树的操作开始考虑。由于我们在每个节点上必须要完成的工作量是不变的，因此遍历的时间与树里的节点的数量是成正比的，也就是集合中的元素数量。因此，那些操作的时间复杂度将会是Θ (n)，其中n是集合的大小。

对于只会检查树的一部分（例如，搜索、插入以及删除）的算法，我们的分析将会取决于树结构的形状。所有的这些方法的最坏情况都需要走一条从树的根节点到其“底部”的路径。很明显，这样做所需的步骤数量将和树的高度成正比。于是，一个有趣的问题出现了，一个二叉树有多高？显然，这取决于树结构的确切形状。如果我们假设这个树是按照排序的顺序来插入的一组数字的话，这个树将会是一个链表，这是因为每个节点都被添加为前一个数字的右子节点。对于具有n个元素的树结构来说，插入需要n步才能到达树的底部。

如果树结构里的数据分布得很好的话，那么我们可以估计：对于任意给定的子树来说，都有大约一半的元素位于它的左子树，而剩下的大约一半的元素位于右子树。我们称这样的树为“平衡”树。相对平衡的树将具有log2n的近似高度。在这种情况下，必须在树中找到特定的节点的操作将会有Θ (lgn)的复杂度。好在，如果数据是按照随机的方式插入树里的话，那么当我们从根节点向下执行的时候，对于每一个节点来说，这个元素具有同样的可能性进入左子树或者右子树。平均来说，这个结果将会是一个非常平衡的树。

在实践中，只要注意插入和删除数据的顺序，二叉搜索树通常都将会提供非常好的性能。对于特别偏执的人来说，有一些非常有名的技术（见13.3节）可以被用来实现二叉树，从而保证在插入和删除操作之后，树结构依然平衡。

7.6　使用二叉搜索树（BST）来实现映射（选读）

上一节里，我们描述了如何让BST对象实现类似于有序集合的实现。因此，我们可以插入元素、删除元素、检查元素是否存在，以及按照排序顺序来获取里面的元素。树结构通常来说会在类似于数据库的应用程序里被用到。在这样的程序里，我们不仅会想要知道特定的元素是不是在集合里，而且还要能够查找出具有某些特定表征的元素。举一个简单的例子，我们可能会需要维护俱乐部会员的名单。很明显，我们需要能够添加和删除俱乐部的成员，但我们还需要更多的东西。比如，我们需要一种可以用来为俱乐部的特定成员提供记录的方法，例如获取他们的电话号码。

在这一节里，我们将会了解如何扩展二叉搜索树的功能，来实现类似于Python字典那样通用的映射。在我们的成员列表示例中，我们使用了由成员名称构造的特殊“键”值，从而能够查找它的数据记录。假设我们有一个合适的membershipList对象，我们可以通过下面这些代码得到一个人的电话号码：

...info = membershipList["VanRossum, Guido"]print info.home_phone

在这里，我们的membershipList是一个映射对象，它把成员的名称和他的具体信息的相应记录进行了映射。我们可以使用Python字典来完成这项任务，但是字典是一种无序的映射。而且，我们也还希望能够按照一定的顺序来高效地输出我们的（巨大的！）成员列表。

解决这个问题的一种方案是重写整个BST类，从而能够让它的所有方法都有一个额外的参数，这个参数被用来获取键。同时，这些方法还需要在执行的过程中维护这个键值对组成的树结构。虽然，这比我们真正需要做的工作要多得多，我们还是可以通过使用现有的BST类来实现。我们可以通过一个包装这个类的包装器来实现通用映射接口，从而获得类似的效果。这样一来，我们在获得基于树结构的映射对象的优点时，不需要去修改BST类或者复制出另外一个BST类。一般来说，只要有可能，我们都应该扩展现有的代码，它通常会比复制或修改现有代码的效果更好。

那么我们如何将这个BST类从一个集合转变为映射呢？这里的关键是利用BST类里已经包含了的现成的排序和查找功能。我们的BST类可以被用来存储任何可以被比较的对象。我们将会把集合里的元素存储为键值对，但诀窍是这些元素将会根据它的键进行排序。因此，第一步是创建一个新的类来表示这些键值对元素。我们将这个组合元素称为KeyPair。同时，为了使我们的KeyPair类可以被比较，我们还需要实现一些与比较相关的操作。

# KeyPair.pyclass KeyPair(object):    def __init__(self, key, value=None):        self.key = key        self.value = value    def __eq__(self, other):        return self.key == other.key    def __lt__(self, other):        return self.key < other.key    def __gt__(self, other):        return self.key > other.key

在这里，我们只实现了6个比较运算符中的3个，这是因为BST类里的所有方法都只会用到这些比较运算符。当然，为了安全起见，以防将来BST类的代码发生变化，我们还是应该尽量地去实现其他3个比较运算符。我们将会把这部分内容作为练习题留给你。

有了这个KeyPair类之后，我们现在就可以定义一个基于BST类的字典映射了。这是我们的类的构造函数：

# TreeMap.pyfrom BST import BSTfrom KeyPair import KeyPairclass TreeMap(object):    def __init__(self, items=()):        self.items = BST()        for key, value in items:            self.items.insert(KeyPair(key, value))

在这段代码里，我们使用了实例变量items来保存将会被用来储存我们的KeyPair元素的BST对象。正如Python字典可以使用一个序列对其进行初始化一样，我们也允许TreeMap类的构造函数接受一个序列对。对于这个参数，我们只需要遍历这些数据对，然后调用BST类的insert操作来填充我们的树。当然，insert方法将会根据键的数据来保持底层二叉搜索树的顺序，而这正是因为我们为KeyPair类实现了相互比较的方法。

一旦KeyPair对象进入到了我们的BST对象，我们需要能够通过它的键的数据来再次检索它。这时，我们可以使用BST类的find操作来完成这个任务。我们将会提供给find操作的参数是一个新的KeyPair对象，它将会等同于我们正在查找的KeyPair（具有相同的键）。因此，像下面这样的一行代码，就能够解决这个问题：

        result = self.items.find(KeyPair(key))

要记住，find操作会在二叉搜索树中搜索相等（==）的目标元素。这时，KeyPair(key)将会和BST中具有相同键的键值对相“匹配”，从而返回这个匹配的KeyPair对象。因此，我们只需要填写键值对的键这部分数据，就能够检索这个键的实际记录了。

为了使我们的TreeMap类能够像Python字典一样地工作，我们还需要实现Python里用来进行索引操作的常用钩子函数：__getitem__和__setitem__。

    def __getitem__(self, key):        result = self.items.find(KeyPair(key))        if result is None:            raise KeyError()        else:            return result.value    def __setitem__(self, key, item):        partial = KeyPair(key)        actual = self.items.find(partial)        if actual is None:            # no pair yet for this key, add one            actual = partial            self.items.insert(actual)        actual.value = item

当给定的键没有出现在字典里的时候，这些方法都会需要一些额外的工作来处理这个特殊的情况。在这种情况下，__getitem__方法会抛出KeyError异常。但是，当__setitem__得到一个新的键的时候，它需要将一个新的KeyPair对象插入到BST对象里去。然而，由于我们已经在一开始就创建了新的KeyPair对象partial来进行初始搜索，因此把它用来设置一个新条目将会是一件简单的事情。

这些代码就足够让我们的TreeMap类启动并且运行了。当然，这个类仍然缺少允许我们按顺序来访问所有元素的迭代器（如用来输出所有成员的列表）。我们将会把添加这些功能作为练习题留给你来完成。

7.7　小结

我们在这一章里介绍了一些用来实现树结构的基本算法和相应的数据结构。以下是关于这些重要亮点的总结。

• 树是一个非线性的容器类，它可以被用来存储分层数据或者存储有组织的线性数据，从而能够有效地去访问它们。
• 树结构通常使用链式结构来进行存储，但是它也可以被存储在数组里。
• 许多使用树结构的应用程序都使用的是二叉树，它代表着每个节点都有零个、一个或两个子节点。当然，也可以实现具有任意数量子节点的树。
• 二分查找属性是指，对于每一个节点，它的左子树中的每一个节点的值都会小于或等于当前节点的值；它的右子树中的每一个节点的值将会大于当前节点的值。
• 二叉搜索树的搜索、插入和删除操作都支持Θ (lgn)时间复杂度的实现，并且，这些操作还能同时保持每个节点的二分查找属性。
• 树的相关算法通常都会使用递归来编写，这是因为树本身就是一个递归数据结构。
• 3个常见的二叉树遍历顺序为：前序、中序和后序。二叉搜索树的中序遍历将会按照排序的顺序来输出元素。

本文摘自《数据结构和算法（Python和C++语言描述）》

本书使用Python和C++两种编程语言来介绍数据结构。Python的面向对象特性， 让它成为一种非常适合用来学习数据结构课程的语言。C++的语法比Python更复杂，但是在学习了Python并掌握了基本的编程概念之后，学习C++的语法变得更为容易。

本书首先介绍了抽象与算法分析、数据的抽象等数据结构的基本原理和知识， 然后结合Python的特点介绍了容器类、链式结构和迭代器、堆栈和队列、递归、树；随后，简单介绍了C++语言的知识，并进一步讲解了C++类、C++的动态内存、C++的链式结构、C++模板、堆、平衡树和散列表、图等内容；最后对算法技术进行了总结。每章末尾给出了一些练习题和编程练习，帮助读者复习巩固所学的知识。

本书适合作为高等院校计算机相关专业数据结构课程的教材和参考书，也适合对数据结构感兴趣的读者学习参考。