从递归删除中获取对象Java

我有一个包含节点的二叉搜索树。每个节点包含一个键值和数据值，并且节点按键排序。我正在尝试编写一个方法从我的BST中删除一个对象提供了一个密钥。这里是代码：从递归删除中获取对象Java

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节点相关的数据值。我遇到的问题是：在公共对象remove（）方法中，返回的值是不是始终是根节点的数据值？我相信会发生这种情况，因为从第二个方法返回的最终调用将是对rootPtr（根指针）的引用。如果是这种情况，我怎样才能从被删除的节点保存数据？

来源

2014-10-17 Jeremy Fisher

我认为你会好得多重组这个。如果算法不是递归的，它会更清晰和更容易理解。您可以迭代搜索树中的右键，存储该值，删除节点并替换其左侧或右侧子节点，然后返回存储的值。 – 2014-10-17 20:11:17

最简单的方法似乎是增加动口不动手的输出参数回结果：

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.s.我假设这不是一个“技巧问题”，你不能只是返回键 - 它必须等于找到的关键毕竟:)

来源

2014-10-17 20:04:24

如果我想返回密钥，那么我将无法返回该节点，因此我的删除代码将无法正确重构树，对吗？ – 2014-10-18 02:30:19

是的。你可以在一些容器中返回两者，但这可能会造成更多的对象创建和管理开销 – 2014-10-18 12:28:57

您必须返回您从递归移除调用接收到的值。

p.ex：

if(theKey.compareTo(node.key) < 0) { 
    // go to left subtree 
    return remove(theKey, node.leftChild); 
}else if ...

现在您将运行throught树，直到找到正确的节点，该节点将给予这是去除节点的父节点，和父母将会把它交给他的父母等等，直到根节点将节点返回给他的主叫者。

来源

2014-10-17 20:02:46

由于返回值用于更新树（按照需要替换已移除的节点），因此这将不起作用（至少不会显着更改代码）。 – 2014-10-17 20:31:11

从递归删除中获取对象Java

回答

相关问题