这是功课;请不要随便给我code

我有两种方法：删除（T数据）和 removeRec（节点＆lt; T＆gt;节点，T数据）。

在当前状态下，看来我的code只删除根的BST的节点。

In its current state, it seems my code only removes the root node of the BST.

@Override
public T remove(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (root == null) {
        throw new java.util.NoSuchElementException("BST is empty");
    } else {
        size--;
        BSTNode<T> dummy = new BSTNode<T>(null);
        return removeRec(root, data, dummy).getData(); //This is probably wrong too
    }
}

/**
 * Helper method to recursively search for, and remove the BSTNode with
 * the given data in it
 * @param  node is the node we're currently at
 * @param  data is the data we're looking for
 * @param  temp I have no idea why
 * @return node that was removed
 */
private BSTNode<T> removeRec(BSTNode<T> node, T data, BSTNode<T> temp) {
    if (compare(data, node.getData()) < 0) {
        temp.setLeft(removeRec(node.getLeft(), data, temp));
    } else if (compare(data, node.getData()) > 0) {
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else if (node.getLeft() != null && node.getRight() != null) {
        temp.setData(findMin(node.getRight()).getData());
        temp.setRight(removeRec(node.getRight(), data, temp));
    } else {
        if (node.getLeft() != null) {
            temp = node.getLeft();
        } else {
            temp = node.getRight();
        }
    }
    return temp;
}

private int compare(T a, T b) {
    return a.compareTo(b);
}

我的教练告诉我（作为提示），我应该看什么传递第三个参数到方法，在这种情况下， BSTNode＆LT; T＆GT;温度。我不知道如何帮助虽然，或如何利用它。我不知道怎样使用第三个参数帮助;我找不到任何在线，为什么你应该这样做无论是。

My instructor has told me (as a hint) that I should see what passing in a third argument into the method, in this case, BSTNode<T> temp. I don't understand how that helps though, or how to utilize it. I don't see how using a third argument helps; and I can't find anything online as to why you'd do this either.

推荐答案

有三种主要的可能性，当你试图删除数据从二叉搜索树：

There are three main possibilities when you try to remove data from your Binary Search Tree:

数据小于当前节点值：调用卸下左子树或 NoSuchElementException异常，如果把它为null。 数据大于当前节点值：调用卸下右子树或 NoSuchElementException异常，如果把它为null。 数据等于当前节点值。 data is less than the current node value: Call remove on the left subtree or throw a NoSuchElementException if it is null. data is greater than the current node value: Call remove on the right subtree or throw a NoSuchElementException if it is null. data is equal to the current node value.

1和2是pretty的简单，但3有四个以上情况来考虑：

1 and 2 are pretty straightforward, but 3 has four more cases to consider:

3.1。 当前节点是叶：左，右子树为空。只需更换由空引用了当前节点在它的父。

3.1. current node is a leaf: Both left and right subtrees are null. Just replace the reference to the current node in its parent by null.

3.2。 当前节点只有左子：你需要使当前节点点的父以左子树，从而消除当前点。要做到这一点，你可以实现一个功能，将检查当前点是在父的左或右子树，并相应地更换。称它是这样的：

3.2. current node has only the left child: You need to make the parent of the current node point to the left subtree, thus removing the current point. To do this, you can implement a function that will check if the current point was on the left or right subtree of the parent and replace it accordingly. Calling it would look like this:

replaceNodeInParent(node, node.getLeft(), parent);

3.3。 当前节点只有右子：类似于3.4，但使用 GetRight时（）而不是 getLeft（）。

3.3. current node has only the right child: Similar to 3.4, but using getRight() instead of getLeft().

3.4。的当前节点具有左和右的儿童：您应该保持为BST的属性，在左侧的所有节点都小于当前节点和右侧的所有节点都大于当前节点。要做到这一点，你会发现右边的最小值，将其复制到当前的节点，然后从右子树删除。事情是这样的：

3.4. current node has both the left and right children: You should maintain the property of the BST that all nodes on the left are less than the current node and all nodes on the right are greater than the current node. To do so, you should find the smallest value on the right, copy it to the current node, and delete it from the right subtree. Something like this:

BSTNode<T> successor = findMin(node.getRight());
node.setData(successor.getData());
removeRec(node.getRight(), successor.getData(), node);

它看起来像你的 BSTNode 不成立的引用，在父节点。如果是这样，我认为这就是在第三个参数的 removeRec 应。你会在每次更换当前节点时需要引用父，所以你可以设置父左或根据需要右子树。

It looks like your BSTNode doesn't hold a reference to the parent node. If so, I believe that's what the third argument for removeRec should be. You will need a reference to the parent every time you replace the current node, so you can set the parent left or right subtree as needed.

有关进一步的阅读，您可以检查二叉搜索树从维基百科这个文章。

For further reading, you can check this article on Binary Search Trees from Wikipedia.