如何在二叉搜索树中添加一个已排序的元素数组(c#)

本文关键字：一个 排序 数组 元素 搜索树 添加 | 更新日期: 2023-09-27 18:15:16

所以我正在实现一个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]的数组中，它会在数组的0位置添加1，然后不会在左子树的0位置添加1(因为当我们进行递归调用时，start = 0, end = -1)，然后将另一个1放入右子树(这是错误的!)。

这是我能看到的唯一不工作的情况。

有什么好办法吗?(我认为这很可能是一个数学错误)

谢谢!

如何在二叉搜索树中添加一个已排序的元素数组(c#)

为什么不重用相同的分割索引?比如:

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;
相关文章：