递归构建二叉搜索树

Question

我在理解从何处开始编写此方法时遇到问题。该方法使用从数组获得的数据（这是一个全局变量）构建树。该方法需要两个参数，它们是整数，大小和开始。

我已经写入插入和删除方法递归，但我不知道如何开始思考如何构建这个。不知道应该做什么样的大小和开始，并且当添加节点时，我将如何转移到数组中的下一个索引而不将其作为参数。

算法或任何帮助将不胜感激。谢谢！

编辑：我无法在构建树时使用插入和删除方法。构建必须是自己的。并且该阵列仅存储要放入树中的预购值

Answer 1

我的猜测是size和start是允许调用代码从全局数据数组的子数组构建二进制搜索树的参数。如果这是班级任务，你应该向老师确认。

如果我的猜测是正确的，那么通过构建您已完成的工作来编写该方法非常简单。创建一个空的二叉树，然后从全局数据数组中的偏移量start开始，插入连续的元素，直到您插入size为止。

你不需要数组作为参数，因为它是一个全局变量。

编辑（基于编辑质疑）：

如果全球阵列已经在预购的，那么它的结构将是：

index: 
start   start+1     end (see below)   start+size 
+--------------+--------------------------+-------------------------+ 
| array[start] | ... smaller elements ... | ... larger elements ... | 
+--------------+--------------------------+-------------------------+ 

array[start]后，每个部分也将具有相同的结构。

要从此构建BST，第一个元素将进入搜索树的根目录。然后，所有跟第一个元素相比较小的元素进入左边的子树，第一个更大的元素直到数组的末尾进入右边的子树。因此，该算法是：

1. 如果size是0，返回null。
2. 在根上创建一个包含array[start]的BST。
3. 从start+1扫描到数组的末尾，第一个元素的索引大于start处的元素。请拨打此号码end。 （如果所有其余元素小于索引start处的元素，则end将是数组长度。）
4. 将步骤2中创建的二叉搜索树的左子树设置为递归调用具有参数的方法的结果end - start - 1为新的尺寸，start+1为新的开始。
5. 将二叉查找树的右子树设置为递归调用方法的结果，该方法的参数为新尺寸start + size - end，新尺寸为end。