java - 如何向二叉标准树java添加重复条目

Question

我编写了一种方法，将非重复条目添加到 bst，但现在我想将重复节点添加到原始节点的右子节点。我已经列出了添加非重复节点的方法，但我不知道如何更新我的方法以添加重复节点。感谢您的帮助。

private T addEntry(T newEntry) {
    BinaryNodeInterface<T> currentNode = getRootNode();
    assert currentNode != null;
    T result = null;
    boolean found = false;

    while (!found) {
        T currentEntry = currentNode.getData();
        int comparison = newEntry.compareTo(currentEntry);

        if (comparison == 0) { // newEntry matches currentEntry;
                                // return and replace currentEntry
            found = true;
            currentNode.setData(newEntry);
        } else if (comparison < 0) {
            if (currentNode.hasLeftChild())
                currentNode = currentNode.getLeftChild();
            else {
                found = true;
                currentNode.setLeftChild(new BinaryNode<T>(newEntry));
            } // end if
        } else {
            assert comparison > 0;

            if (currentNode.hasRightChild())
                currentNode = currentNode.getRightChild();
            else {
                found = true;
                currentNode.setRightChild(new BinaryNode<T>(newEntry));
            }
        }
    }

    return result;
}

Answer 1

在这里进行比较

if (comparison == 0) { // newEntry matches currentEntry;
// return and replace currentEntry
    found = true;
    currentNode.setData(newEntry);

并在另一个比较中添加 >=

assert comparison >= 0;
        if (currentNode.hasRightChild())
            currentNode = currentNode.getRightChild();
        else {
            found = true;
            currentNode.setRightChild(new BinaryNode<T>(newEntry));
        }

但是，除非您对代码进行更多更改，否则重复项将出现在列表底部或下一行，而不是当前节点的右子节点。您可以检查它们是否相同，创建一个新节点并将其设置为右子节点，然后将新节点的右子节点设置为旧的右子节点。然而这样做会导致 BST 不平衡。