java - 挿入による2つの二分探索木のマージ

Question

私は現在、バイナリ検索ツリーを実装していますが、別のツリーとのマージで行き詰まりました。これまでのところ私は持っています：

• head：ノードが最小のノードを返します
• テール：最小ノードのないツリーを返します
• insert（value）：従来のinsert-method

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.
}