太原PHP培训
达内太原php培训中心

0351-5608878

热门课程

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

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

现在,我们拥有了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

<a style='color:blue' href='http://ty.php.tedu.cn'>太原php培训</a>班

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

Listing 6

太原达内php培训机构

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

太原达内php培训班

上一篇:太原php培训班:Python数据结构——二叉搜索树的实现(上一)
下一篇:太原php培训机构:你有认真对待自己吗?

太原php培训:软件项目免坑指南(一)

太原php培训:一个女程序员的职场自述

太原php培训:ML 工程师需了解的 10 大算法(二)

太原php培训:ML 工程师需了解的 10 大算法(一)

选择城市和中心
贵州省

广西省

海南省