java - 通过插入合并 2 个二叉搜索树

Question

我目前正在实现一个二叉搜索树，并被困在将它与另一个合并。到目前为止，我有：

• head：返回具有最小节点的节点
• tail：返回没有最小节点的树
• insert(value)：传统的插入方法

由于我收到了 StackOverflowError，我认为最好提供所有方法，而不仅仅是合并方法。我很确定错误是由于递归调用的数量造成的。

我会很感激任何帮助！TYVM。

public BinaryTree insert(int newValue) {
    if (newValue < value) {
        if (left == null) {
            return new BinaryTree(value, new BinaryTree(newValue), right);
        } else {
            return new BinaryTree(value, left.insert(newValue), right);
        }
    } else if (newValue > value) {
        if (right == null) {
            return new BinaryTree(value, left, new BinaryTree(newValue));
        } else {
            return new BinaryTree(value, left, right.insert(newValue));
        }
    }
    return this;
}

public int head() {
    if (left != null) {
        return left.head();
    }
    return value;
}

public BinaryTree tail() {
    if (left != null) {
        return new BinaryTree(value, left.tail(), right);
    } else {
        return new BinaryTree(value, left, right.tail());
    }

}

public BinaryTree merge(BinaryTree other) {
    if (other != null) {
        insert(other.head()merge(other.tail()));
    }
    return this;
}

Answer 1

public BinaryTree merge(BinaryTree other) {
    if (other != null) {
        return insert(other.head()).merge(other.tail());
    }
    return this;
}

---

/**
 * Get the tail of a tree.
 * @return the tree without the smallest value.
 */
public BinaryTree tail() {
    if (left != null) {
        return new BinaryTree(value, left.tail(), right);
    }
    return right; // Could make a deep copy.
}