课程咨询 :13623629309

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

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

  • 搜索树实现(续)

    最后,我们把注意力转向二叉搜索树中最具挑战性的方法,删除一个键值(参见Listing 7)。首要任务是要找到搜索树中要删除的节点。如果树有一个以上的节点,我们使用_get方法找到需要删除的节点。如果树只有一个节点,这意味着我们要删除树的根,但是我们仍然要检查根的键值是否与要删除的键值匹配。在以上两种情况下,如果没有找到该键,del操作就会报错。

    Listing 7

    太原达内php

    一旦我们找到包含要删除的节点,我们必须考虑三种情况:

    要删除的节点没有孩子(见图3).

    要删除的节点只有一个孩子(见图4).

    要删除的节点有两个孩子(见图5).

    第一种情况是最简单的(参见Listing 8)。如果当前节点没有孩子,所有我们需要做的是引用删除该节点并删除父节点的引用。本例的代码显示在如下。

    Listing 8

    太原达内php培训机构

    太原达内PHP培训机构

    图 3:删除键值为16的节点,这个节点没有孩子

    第二种情况只是稍微复杂(参见Listing 9)。如果节点只有一个孩子,那我们可以简单地让孩子替换它父母的位置。此案例的代码如下所示。看到这段代码,就会发现有六种情况要考虑。由于是具有左子树还是右子树的情况,我们只讨论当前节点只有左子树的情况。具体过程如下:

    如果当前节点是左子树,那我们只需要更新左子树的引用指向当前节点的父节点,然后更新父节点的左子树引用指向当前节点的左子树。

    如果当前节点是右子树,那我们只需要更新右子树的引用指向当前节点的父节点,然后更新父节点的右子树引用指向当前节点的右子树。

    如果当前节点没有父节点,它一定是根。这种情况下,我们只需通过调用replaceNodeData方法把键替换为左子树和右子树里的数据。

    Listing 9

    太原达内php培训机构

    太原达内php培训班

    图 4:删除键值为25的节点,它是只有一个孩子的节点

    第三种情况是最难处理的情况(参见Listing 10)。如果一个节点有两个孩子,我们就不可能简单地让其中一个替换节点的位置,我们需要寻找一个节点,用来替换这个将要删除的节点,我们需要的这个节点能够保持现有二叉搜索树的左、右子树的关系。这个节点在树中具有第二大的键值。我们称这个节点为后继节点,我们将一路寻找这个后继节点,后继节点必须保证没有一个以上的孩子,所以既然我们已经知道如何处理这两种情况,我们就可以实现它了。一旦后继结点被删除,我们把它放在树中将被删除的树节点处。

    太原达内php培训班

    图 5:删除键值为5的节点,它有两个孩子节点

    第三种情况的处理代码如下所示。注意我们是用findSuccessor和findMin方法来辅助找到后继节点的。要删除后继节点,我们利用spliceOut方法。我们用spliceOut的原因是它能直接使我们想移除的节点,做出正确的变化。我们也可以调用递归删除,但那样我们就会浪费时间反复寻找关键节点。

    Listing 10

    太原达内php培训

    找到后继节点的代码如下所示(参见Listing 11),你可以看到TreeNode类的一个方法。这个代码利用二叉搜索树中序遍历的性质,从最小到最大打印出树中的节点。当寻找后继节点时需要考虑三种情况:

    如果节点有右子节点,那么后继节点是右子树中最小的关键节点。

    如果节点没有右子节点,是其父节点的左子树,那么父节点是后继节点。

    如果节点是其父节点的右子节点,而本身无右子节点,那么这个节点的后继节点是其父节点的后继节点,但不包括这个节点。

    现在对我们来说首要的问题是从二叉搜索树中删除一个节点。而findSuccessor方法的其他用途,我们将在本章最后的练习中作探讨。

    findMin方法是用来找到子树中的最小的节点。你要了解,最小值在任何二叉搜索树中都是树最左边的孩子节点。因此findMin方法只需要简单地追踪左子树,直到找到没有左子树的叶节点。

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

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

最新开班日期  |  更多

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

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

开班日期:12-30

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

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

开班日期:12-30

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

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

开班日期:12-30

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

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

开班日期:12-30

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

    在线客服系统