我有一个包含节点的二叉搜索树。每个节点都包含一个键值和数据值，节点按键排序。我正在尝试编写一个方法来从我的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节点关联的数据值。我遇到的问题是：在公共对象删除（）方法中，返回的值不总是根节点的数据值吗？我相信这会发生，因为第二个方法的最终返回调用将是对rootPtr（根指针）的引用。如果是这种情况，我如何保存已删除节点的数据？
最简单的解决方案似乎是添加一个输出参数而不是返回结果：
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;
}
如果没有重大更改，返回找到的节点将无法工作，因为返回参数用于根据需要替换节点，并且在找到的节点有两个子节点的情况下，您需要复制或插入一个新节点。处理根节点被删除的情况也是一个问题。
附言：我假设这不是一个“技巧问题”，你不能只返回密钥——毕竟它必须等于找到的密钥：）
您必须返回从递归移除调用接收的值。
p. ex：
if(theKey.compareTo(node.key) < 0) {
// go to left subtree
return remove(theKey, node.leftChild);
}else if ...
现在你将通过树运行，直到你找到正确的节点，该节点将被赋予节点的父节点以删除，父节点将把它交给他的父节点，依此类推，直到根节点将节点返回给他的调用者。
