江苏龙网

  1. 主页 > 生活百科 > >

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

算法树结构


当然，通常来说，我们并不希望像这样通过直接操作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 。于是，有了我们的类的构造函数：


推荐阅读


上一篇：新手淘宝开店需要多少钱可以做起来 新手开淘宝店需要多少资金

下一篇：记一次CPU使用率低负载高的排查过程