java - 从递归删除Java中获取对象

Question

我有一个包含节点的二叉搜索树。每个节点包含一个键值和数据值，节点按键排序。我正在尝试编写一个方法来从提供 key 的 BST 中删除对象。这是代码:

public Object remove(Comparable theKey) {
        return remove(theKey, rootPtr).data;
    }

public Node remove(Comparable theKey, Node node) {
    Object o;
    if(node == null)
        return node;

    if(theKey.compareTo(node.key) < 0) {
        // go to left subtree
        node.leftChild = remove(theKey, node.leftChild);
    }else if(theKey.compareTo(node.key) > 0) {
        //go to the right subtree
        node.rightChild = remove(theKey, node.rightChild);
    }else if(theKey.compareTo(node.key) == 0) {

        if(node.leftChild != null && node.rightChild != null){
            Node foundNode = findMin(node.rightChild);
            node.key = foundNode.key;
            node.data = foundNode.data;
            node.rightChild = remove(node.key, node.rightChild);
        }else{
            if(node.leftChild != null){
                node = node.leftChild;
            }else{
                node = node.rightChild;
            }
        }
    }
    numNodes--;
    return node;

 }

我想返回与 DELETED 节点关联的数据值。我遇到的问题是:在public Object的remove()方法中，返回的值不是总是根节点的数据值吗？我相信会发生这种情况，因为第二个方法的最终返回调用将是对 rootPtr (根指针)的引用。如果是这种情况，如何保存已删除节点的数据？

Answer 1

最简单的解决方案似乎是添加一个输出参数，而不是返回结果:

public Object remove(Comparable theKey) {
  Object[] result = new Object[1];
  rootPtr = remove(theKey, rootPtr, result);   // fix for deletion from a one-node tree
  return result[0];
}

public Node remove(Comparable theKey, Node node, Object[] result) {
  if(node == null) {
    return node;
  }
  int diff = theKey.compareTo(node.key);
  if (diff < 0) {
    node.leftChild = remove(theKey, node.leftChild, result);
  } else if (diff > 0) {
    node.rightChild = remove(theKey, node.rightChild, result);
  } else {
    result[0] = node.key;
    if (node.rightChild == null) {
      node = node.leftChild;
    } else if (node.leftChild == null) {
      node = node.rightChild;
    } else {
      Node foundNode = findMin(node.rightChild);
      node.key = foundNode.key;
      node.data = foundNode.data;
      node.rightChild = remove(node.key, node.rightChild, new Object[1]);
    }
    numNodes--;
  }
  return node;
}

如果没有重大更改，返回找到的节点将无法工作，因为返回参数用于根据需要替换节点，并且在找到的节点有两个子节点的情况下，您需要复制或插入新的节点节点。处理根节点被删除的情况也是一个问题。

附:我假设这不是一个“欺骗问题”，你不能只返回 theKey —— 毕竟它必须等于找到的键:)