二进制搜索树实现和Java

二进制搜索树实现和Java

一些眼前的问题与您的代码：您

treeSuccessor

开始使用

    if (x.right == null){        return treeMinimum(x.right);    }

if (x.right != null)

当然应该是。

您的

insert

代码包含以下内容

    Node tmp = getParent(t,z);    tmp = y;

您分配

tmp

给它的位置，然后立即再次分配给它。在我看来，您根本不需要这些行，因为您将不再使用它们

tmp

。此时，您已经

y

是要

z

插入其子节点的节点，因此只需删除这些行。

同样，在中

delete

，您有

    if (x != null){        Node tmp = getParent(t,x);        tmp = getParent(t,y);    }

您实际上什么都没做的地方，因为

tmp

在此代码段之外不可见。进一步，在中

delete

，您重复表达式

getParent(t,y)

，这可能是一个昂贵的 *** 作，因此您应该只计算一次并将其分配给某个变量。

但总的来说，您的代码虽然看起来是正确的（可能与

delete

，但我不太了解，但看起来很可疑），但它与典型的二叉树代码不太相似。你并不真的需要

getParent

和

treeSuccessor

方法来实现

search

，

insert

和

delete

。您具有的基本结构也

search

适用于其他结构，但进行了以下修改：

• 使用

  insert

  ，当您到达

  null

  链接时，而不是返回

  null

  ，而是将元素插入到该点
• 使用

  delete

  ，当找到元素时，如果它只有一个（或没有）子代，则用该子代替换它；如果有两个子代，则用左子树的最大值或右子树的最小值替换树

这两个条件都要求您在下降到树中时跟踪父节点，但这是您需要做的唯一修改

search

。尤其是，永远不需要在树上向上移动（这样

treeSuccessor

做就可以了）。