二叉树删除实现

Question

我正在尝试在 Dart 中实现一个简单的二叉树。我的插入和搜索似乎工作得很好，但我的删除/删除却不行。

void delete(int targetData) {
BinarySearchTreeNode? target = find(targetData);
if (target == null) {
  return;
}
if (target.left == null && target.right == null) {
  target = null;
} else {
  //This means the target has at least one child.
  //Let's take care of the one child case first.
  if (target.left == null) {
    target = target.right;
  } else if (target.right == null) {
    target = target.left;
  } else {
    //This means both children are present.
    BinarySearchTreeNode? current = target.right;
    if (current!.left == null) {
      BinarySearchTreeNode newTarget =
          BinarySearchTreeNode(current.nodeData);
      newTarget.left = target.left;
      newTarget.right = target.right;
      target = newTarget;
    } else {
      BinarySearchTreeNode? previous;
      while (current != null) {
        previous = current;
        current = current.left;
      }
      BinarySearchTreeNode newTarget =
          BinarySearchTreeNode(previous!.nodeData);
      newTarget.left = target.left;
      newTarget.right = target.right;
      target = newTarget;
      delete(previous.nodeData);
    }
  }
}

}

在现有节点上运行删除后，树似乎保持不变。我还尝试使用 find 方法中的相同代码而不是传递目标。该代码没有显示运行时错误。这是我在 DartPad 中的完整代码，以防有人认为问题出在方法之外。

Answer 1

问题就在这里：

  print('Deleting $targetData');
  if (target.left == null && target.right == null) {
    //print('    $targetData has no children. Setting node to null');
    target = null;

target

是一个局部变量，因此将其设置为 null 不会执行任何操作。特别是，它不会修改树。

如果您考虑以下过程：

insert(10)

紧接着

delete(10)

，您希望最终得到一棵空树。实现这一目标的唯一方法就是以某种方式写下

_root = null;

。这意味着您需要将

target

与

_root

进行比较，并在删除最后一个节点时采取特殊操作（就像您在示例的前几个步骤中所做的那样）。

重复一遍，此代码不会清空树：

var target = _root;
target = null; // this does *not* set _root to null

一般来说，当您在树中查找要删除的内容时，您必须保留另一个指向您来自何处（即父级）的局部变量。然后，当您想要删除其子级之一时，您仍然可以引用父级，并且可以说，例如，

parent.left = null;

再次：

var target = someNode.left;
target = null; // this does *not* set someNode.left to null

对

var parent = someNode;
var target = parent.left;
parent.left = null; // this *does* set someNode.left to null