BST（二叉搜索树）的 removeAll 方法

Question

下面有这段代码，我正在尝试为二叉搜索树创建一个 removeAll 方法。我认为即使没有所有外部代码和上下文，下面的代码也很可能是可读的，但如果不是，我很乐意提供更多信息。但是，这段代码根本不起作用，我无法弄清楚它的原因。我只是尝试使用中序遍历遍历二叉搜索树，计算 targetElement 存在的次数，然后调用 remove 方法的次数。

public void removeAllOccurrences(T targetElement) throws ElementNotFoundException 
   {
    removeElement(targetElement);

    Comparable<T> comparableElement = (Comparable<T>) targetElement;
    Iterator<T> iter = iteratorInOrder();
    int n = 0; 


    while(iter.hasNext())
    {
        if (((Comparable<T>) comparableElement).equals(iter.next())) 
        {
            n++;
        }
    }

    for(int i=0; i<n; i++)
    {
        removeElement(targetElement);
    }


}

class 的名称是 LinkedBinarySearchTree。我们正在使用 BinaryTreeNode。我们有一个 getRootNode() 方法。

Answer 1

由于您假设 T 实现了 Comparable<T>（通过强制转换 targetElement），您应该使用此功能。您用于比较 comparableElement 和 iter.next() 的 equals 方法是从 Object class 继承的方法，可能未被 [=11= 覆盖]. equals 方法的默认实现只是比较调用者的内存地址和可能不是您想要的参数。

Comparable<T> 的 compareTo 方法实际上将由 T 实现，因此您应该改用它。 compareTo returns 一个 int 如果它是负数则表示调用者小于参数，如果是正数则表示调用者大于参数，或者调用者等于参数如果它是零。因此，您应该将表达式 ((Comparable<T>) comparableElement).equals(iter.next()) 更改为 comparableElement.compareTo(iter.next()) == 0。 comparableElement 的转换不是必需的，因为变量已经是 Comparable<T>.

类型

以下是更改在您的代码中的样子。

public void removeAllOccurrences(T targetElement) throws ElementNotFoundException {
    removeElement(targetElement);

    Comparable<T> comparableElement = (Comparable<T>) targetElement;
    Iterator<T> iter = iteratorInOrder();
    int n = 0;

    while(iter.hasNext()) {
        if (comparableElement.compareTo(iter.next()) == 0) {
            n++;
        }
    }

    for (int i = 0; i < n; i++) {
        removeElement(targetElement);
    }
}

如果我误解了你的问题，请告诉我。

BST（二叉搜索树）的 removeAll 方法

removeAll method for BST (Binary Search Tree)

java

binary-tree

binary-search-tree

removeall