通過插入合併2個二叉搜索樹

Question

我目前正在實現一個二叉搜索樹，並被困在合併與另一個。 到目前爲止，我已經有了：

• 頭：用最小的節點返回節點
• 尾：返回樹W/O最小節點
• 插入（值）：傳統的插入法

由於我得到一個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. 
}