如何添加一個二進制搜索樹的元素排序（在C＃中）

Question

因此，我正在實施一個BST，現在我正試圖從一個已排序的數組中添加項目。

我有一個遞歸函數Dup的：

private BNode Dup(T[] arr, int start, int end) { 

    if (start > end) return null; 

    BNode sub_root = new BNode(arr[(int)Math.Ceiling((double)((start + end)/2))]); 
    sub_root.Left = Dup(arr, start, (start + end)/2 - 1); 
    sub_root.Right = Dup(arr, (start + end)/2 + 1, end); 
    return sub_root; 

} 

但是，如果我通過它在陣列中，看起來像[1,1]，它增加了1在陣列的0的位置，然後添加犯規在左子樹的位置0處的1（因爲當我們進行遞歸調用時，start = 0，end = -1），然後將另一個1放到右子樹中（這是錯誤的！）。

這是我所看到的是不工作的唯一情況..

任何想法如何解決呢？ （我認爲這很可能是一個數學錯誤）

謝謝！

Answer 1

爲什麼不重用相同的拆分索引？例如：

int splitIndex = (int)Math.Ceiling((double)(start + end)/2); 
BNode sub_root = new BNode(arr[splitIndex]); 
sub_root.Left = Dup(arr, start, splitIndex - 1); 
sub_root.Right = Dup(arr, splitIndex + 1, end); 
return sub_root;