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

0351-5608878

热门课程

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

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

搜索树实现(续)

最后,我们把注意力转向二叉搜索树中最具挑战性的方法,删除一个键值(参见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培训:软件项目免坑指南(一)

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

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

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

选择城市和中心
贵州省

广西省

海南省

台湾