java - 递归构建二叉搜索树

Question

我在理解从哪里开始编写此方法时遇到问题。该方法使用从数组（这是一个全局变量）中获取的数据构建一棵树。该方法采用两个参数，即 ints、size 和 start。

我已经递归地编写了插入和删除方法，但我什至不知道如何开始考虑构建它。不确定应该做什么大小和开始，以及添加节点时，我将如何移动到数组中的下一个索引而不将其作为参数包含在内。

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

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

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。（如果所有剩余元素都小于 index 处的元素，则为start数组end长度。）
4. 将在步骤 2 中创建的二叉搜索树的左子树设置end - start - 1为使用新大小和start+1新起点的参数递归调用方法的结果。
5. 将二叉搜索树的右子树设置start + size - end为使用新大小和end新开始的参数递归调用方法的结果。