课程咨询 :13623629309

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

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

  • 现在,我们拥有了BinarySearchTree和TreeNode类,是时候写一个put方法使我们能够建立二叉搜索树。put方法是BinarySearchTree类的一个方法。这个方法将检查这棵树是否已经有根。如果没有,我们将创建一个新的树节点并把它设置为树的根。如果已经有一个根节点,我们就调用它自己,进行递归,用辅助函数_put按下列算法来搜索树:

    从树的根节点开始,通过搜索二叉树来比较新的键值和当前节点的键值,如果新的键值小于当前节点,则搜索左子树。如果新的关键大于当前节点,则搜索右子树。

    当搜索不到左(或右)子树,我们在树中所处的位置就是设置新节点的位置。

    向树中添加一个节点,创建一个新的TreeNode对象并在这个点的上一个节点中插入这个对象。

    Listing 3 显示了在树中插入新节点的Python代码。_put函数要按照上述的步骤编写递归算法。注意,当一个新的子树插入时,当前节点(CurrentNode)作为父节点传递给新的树。

    我们执行插入的一个重要问题是重复的键值不能被正确的处理,我们的树实现了键值的复制,它将在右子树创建一个与原来节点键值相同的新节点。这样做的后果是,新的节点将不会在搜索过程中被发现。我们用一个更好的方式来处理插入重复的键值,旧的值被新键关联的值替换。我们把这个错误的修复,作为练习留给你。

    Listing 3

    太原达内php培训

    随着put方法的实现,我们可以很容易地通过__setitem__方法重载[]作为操作符来调用put方法(参见Listing 4)。这使我们能够编写像myZipTree['Plymouth'] = 55446一样的python语句,这看上去就像Python的字典。

    Listing 4

    太原达内php培训班

    图 2 说明了将新节点插入到一个二叉搜索树的过程。灰色节点显示了插入过程中遍历树节点顺序。

    太原达内php培训班

    图 2: 插入一个键值 = 19 的节点

    一旦树被构造,接下来的任务就是为一个给定的键值实现检索。get方法比put方法更容易因为它只需递归搜索树,直到发现不匹配的叶节点或找到一个匹配的键值。当找到一个匹配的键值后,就会返回节点中的值。

    Listing 5 显示了get,_get和__getitem__的代码。用_get方法搜索的代码与put方法具有相同的选择左或右子树的逻辑。请注意,_get方法返回TreeNode中get的值,_get就可以作为一个灵活有效的方式,为BinarySearchTree的其他可能需要使用TreeNode里的数据的方法提供参数。

    通过实现__getitem__方法,我们可以写一个看起来就像我们访问字典一样的Python语句,而事实上我们只是操作二叉搜索树,例如Z = myziptree ['fargo']。正如你所看到的,__getitem__方法都是在调用get。

    Listing 5

    太原php培训班

    使用get,我们可以通过写一个BinarySearchTree的__contains__方法来实现操作,__contains__方法简单地调用了get方法,如果它有返回值就返回True,如果它是None就返回False。如Listing 6 所示。

    Listing 6

    太原达内php培训机构

    回顾一下__contains__重载的操作符,这允许我们写这样的语句:

    太原达内php培训班

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

下一篇:太原php培训机构:你有认真对待自己吗?

最新开班日期  |  更多

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

    在线客服系统