java - 防止将重复项添加到二叉搜索树

Question

这是作业。请不要只给我代码。

任务是实现 BST 使用的几种方法；其中，是 add(T data) 和 remove(T data)。我能够成功实现它们。

以下是这两种方法的指南:

• public void add(T 数据)
  • 如果数据已经在树中，什么都不做(不重复)
  • 必须是递归的(我创建了一个辅助函数)
• public T remove(T data)
  • 如果数据不在树中，throw new java.util.NoSuchElementException()
  • 必须是递归的(我创建了一个辅助函数)

我最初对其进行了编码，因此它使用 contains(T data) 方法来检查如何添加/删除数据。我发现我不能使用 contains() 方法来执行此操作，我必须以其他方式实现它。

从概念上讲，我明白我需要从根本上检查我们是否处于没有叶子的父节点。但是，我不完全确定在哪里或如何实现这些检查。

例如，这是我的add() 方法:

@Override
public void add(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    //FIXME don't use the contains() method
    if (root == null) {
        BSTNode<T> node = new BSTNode<>(data);
        root = node;
    } else {
        addRec(root, data);
    }
    size++;
}

/**
 * Helper method to recursively add data to the BST
 * @param node is the node we're currently at
 * @param data is the data we're adding to the BST
 * @return node that we added
 */
private BSTNode<T> addRec(BSTNode<T> node, T data) {
    //This if-statement isn't correct
    if (compare(data, node.getLeft().getData()) == 0
        || compare(data, node.getRight().getData()) == 0) {
        return node;
    }

    if (node == null) {
        return new BSTNode<T>(data);
    }
    if (compare(data, node.getData()) == 0) {
        return node;
    } else if (compare(data, node.getData()) < 0) {
        node.setLeft(addRec(node.getLeft(), data));
    } else if (compare(data, node.getData()) > 0) {
        node.setRight(addRec(node.getRight(), data));
    }
    return node;
}

@Override
public boolean contains(T data) {
    if (data == null) {
        throw new IllegalArgumentException("Data is null");
    }
    if (root == null) {
        return false;
    } else {
        return containsRec(root, data);
    }
}

/**
 * Helper method to recursively check if the BST contains the data
 * @param  node is the node we're currently at
 * @param  data is the data we're looking for
 * @return boolean if the data was found
 */
private boolean containsRec(BSTNode<T> node, T data) {
    if (node == null) {
        return false;
    } else if (compare(data, node.getData()) == 0) {
        return true;
    } else if (compare(data, node.getData()) < 0) {
        return containsRec(node.getLeft(), data);
    } else if (compare(data, node.getData()) > 0) {
        return containsRec(node.getRight(), data);
    } else {
        return false;
    }
}

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

如果我能弄清楚这一点，我很确定修复 remove() 方法将几乎相同。

失败的测试(有几个)

@Test
public void testAddDuplicate() {
    // setup
    makeTree();

    // add duplicates
    bst.add(bst.getRoot().getData());
    bst.add(bst.getRoot().getLeft().getData());
    bst.add(bst.getRoot().getRight().getData());

    // check size
    assertEquals(9, bst.size());
}

Answer 1

实现三种遍历二叉树的方法中的一种，即按顺序、前顺序或后顺序。

利用此方法确定您的树是否包含给定项目。在添加的情况下，您不需要做任何事情。在删除的情况下，您可以从树中删除该节点。