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

Question

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

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

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

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

我最初对其进行了编码，因此它使用 contains(T data) 方法来检查如何 add/remove 数据。我发现我不能使用 contains() 方法来做到这一点，我必须以其他方式实现它。

从概念上讲，我明白我需要从根本上检查我们是否在没有叶子的父节点上。但是，我不完全确定 where 或 how 来实施这些检查。

例如，这是我的 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

实现一种遍历二叉树的三种方式，即有序、预序或Post顺序.

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

Answer 2

if (root == null) {
    BSTNode<T> node = new BSTNode<>(data);
    root = node;
} else {
    addRec(root, data);
}
size++;

在此代码中，无论是否找到重复元素或树是否实际更改，您都递增 size。因此，单元测试（正确地）识别树的 size 已经改变，即使树只有正确数量的元素。

您应该只在实际向树中添加新节点时递增 size。

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

Prevent duplicates from being added to Binary Search Tree

java

recursion

nodes

binary-search-tree