课程咨询 :13623629309

太原PHP培训 > 达内新闻 > 太原php培训班:Python数据结构——二叉搜索树的实现(上一)
  • 太原php培训班:Python数据结构——二叉搜索树的实现(上一)

    发布:太原PHP培训      来源:伯乐在线      时间:2016-06-21

  • 二叉搜索树

    我们已经知道了在一个集合中获取键值对的两种不同的方法。回忆一下这些集合是如何实现ADT(抽象数据类型)MAP的。我们讨论两种ADT MAP的实现方式,基于列表的二分查找和哈希表。在这一节中,我们将要学习二叉搜索树,这是另一种键指向值的Map集合,在这种情况下我们不用考虑元素在树中的实际位置,但要知道使用二叉树来搜索更有效率。

    搜索树操作

    在我们研究这种实现方式之前,让我们回顾一下ADT MAP提供的接口。我们会注意到,这种接口和Python的字典非常相似。

    Map() 创建了一个新的空Map集合。

    put(key,val) 在Map中增加了一个新的键值对。如果这个键已经在这个Map中了,那么就用新的值来代替旧的值。

    get(key) 提供一个键,返回Map中保存的数据,或者返回None。

    del 使用del map[key]这条语句从Map中删除键值对。

    len() 返回Map中保存的键值对的数目

    in 如果所给的键在Map中,使用key in map这条语句返回True。

    搜索树实现

    一个二叉搜索树,如果具有左子树中的键值都小于父节点,而右子树中的键值都大于父节点的属性,我们将这种树称为BST搜索树。如之前所述的,当我们实现Map时,BST方法将引导我们实现这一点。图 1 展示了二叉搜索树的这一特性,显示的键没有关联任何的值。注意这种属性适用于每个父节点和子节点。所有在左子树的键值都小于根节点的键值,所有右子树的键值都大于根节点的键值。

    太原达内PHP培训

    图 1:一个简单的二叉搜索树

    现在你知道什么是二叉搜索树了,我们再来看如何构造一个二叉搜索树,我们在搜索树中按图 1 显示的节点顺序插入这些键值,图 1 搜索树存在的节点:70,31,93,94,14,23,73。因为 70 是第一个被插入到树的值,它是根节点。接下来,31 小于 70,因此是 70 的左子树。接下来,93 大于 70,因此是 70 的右子树。我们现在填充了该树的两层,所以下一个键值,将会是 31 或者 93 的左子树或右子树。由于 94 大于 70 和 93,就变成了 93 的右子树。同样,14 小于 70 和 31,因此成为了 31 的左子树。23 也小于 31,因此必须是 31 的左子树。然而,它大于 14,所以是 14 的右子树。

    为了实现二叉搜索树,我们将使用节点和引用的方法,这类似于我们实现链表和表达式树的过程。因为我们必须能够创建和使用一个空的二叉搜索树,所以我们将使用两个类来实现,第一个类我们称之为 BinarySearchTree,第二个类我们称之为TreeNode。BinarySearchTree类有一个TreeNode类的引用作为二叉搜索树的根,在大多数情况下,外部类定义的外部方法只需检查树是否为空,如果在树上有节点,要求BinarySearchTree类中含有私有方法把根定义为参数。在这种情况下,如果树是空的或者我们想删除树的根,我们就必须采用特殊操作。BinarySearchTree类的构造函数以及一些其他函数的代码如Listing 1 所示。

    Listing 1

    太原达内php培训班

    TreeNode类提供了许多辅助函数,使得BinarySearchTree类的方法更容易实现过程。如Listing 2 所示,一个树节点的结构,是由这些辅助函数实现的。正如你看到的那样,这些辅助函数可以根据自己的位置来划分一个节点作为左或右孩子和该子节点的类型。TreeNode类非常清楚地跟踪了每个父节点的属性。当我们讨论删除操作的实现时,你将明白为什么这很重要。

    对于Listing 2 中的TreeNode实现,另一个有趣的地方是,我们使用Python的可选参数。可选的参数很容易让我们在几种不同的情况下创建一个树节点,有时我们想创建一个新的树节点,即使我们已经有了父节点和子节点。与现有的父节点和子节点一样,我们可以通过父节点和子节点作为参数。有时我们也会创建一个包含键值对的树,我们不会传递父节点或子节点的任何参数。在这种情况下,我们将使用可选参数的默认值。

    Listing 2

    太原达内php培训班

上一篇:太原php培训班:一个小白程序猿打怪与升级的故事(5)

下一篇:太原php培训班:Python数据结构——二叉搜索树的实现(上二)

最新开班日期  |  更多

php高级开发名企定制班(剩2个名额)

php高级开发名企定制班(剩2个名额)

开班日期:12-29

php高级开发周末班(剩5个名额)

php高级开发周末班(剩5个名额)

开班日期:12-29

php高级开发免费试听(剩5个名额)

php高级开发免费试听(剩5个名额)

开班日期:12-29

更多高级开发工程师精品班

更多高级开发工程师精品班

开班日期:12-29

  • 地址:山西省太原市小店区学府街长治路高新国际A座24层
  • 课程培训电话:13623629309     全国服务监督电话:400-827-0010
  • 服务邮箱 ts@tedu.cn
  • 2001-2016 达内国际公司(TARENA INTERNATIONAL,INC.) 版权所有 京ICP证08000853号-56