如何添加一个二进制搜索树的元素排序（在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;