即使将节点分配为空,也不会从 BST 中删除该节点

Node not being deleted from BST even if it is assigned null

我在 as3 中构建了一个 BST,它包含一个函数,用于从具有提供值的树中删除一个节点。

这是代码。这里pull其实就是"delete"的意思。我只给出有问题的代码。

public function pull(k:int)
{
    //find the node in BST
    t = search(k);
    //if the node was found with value k
    if (t) 
    {
        //the node did not have any children
        if (t.none())
        {
            //simply set it to null
            t = null;
        }
        else if (t.one())
        {

        }
        else if (t.two())
        {

        }
    }
}

我已经在树 12 和 10 中插入了两个值。 树是这样的

  12
 /
10

然后我调用了函数

 pull(10);

但是当我尝试跟踪(bst.root.leftChild)时它仍然给出输出

 [Object Node]

我不知道如何解决它。

我不熟悉 AS3,但我会尝试回答这个问题。 基本上当你做 t = search(k) 时你正在做的是搜索函数 returns t 中引用的副本,换句话说,t 被设置为引用结果共 search(k).

当您执行 t = null 时,您只是在删除 t 与您要删除的树节点之间的连接。但这不会删除节点。它只是将 t 设置为引用 null.

来自C背景,我会建议2种方法来解决它:

  1. 使用类似于指向指针的指针(如果它存在于 AS3 中,抱歉我不知道)。
  2. 使用所需节点的父节点删除它。例如,如果你想删除一个节点 b,它是 a 的左子节点,执行 a.left = null 将删除所需的节点,因为它有效地充当指向指针的指针。

对于我回答中的任何事实错误,我深表歉意,如果我错了,请指正。

将对象设置为 null 并不是即时删除它的有效方法,事实上,它很可能会保留一段时间,直到最终被 GC 处理。但是当然,只有在该对象的每个引用都被取消时才会发生这种情况。如果该对象仍在其他地方引用,则使一个变量无效将没有任何效果。

因此,即使在取消所有引用时,该对象仍将存在一段时间,因此最好的方法是实现一个将对象设置为非活动状态的方法,以便可以跳过它。之后,您可以开始删除对它的所有引用。

您正在跟踪的简单事实 "trace(bst.root.leftChild)" 意味着变量 "leftChild" 仍然具有对节点对象的引用,如果您不取消该对象,则该对象将仍然存在。如果您不取消对该对象的所有引用,则该对象将保持存在。