java - 未排序数组到二叉搜索树

Question

所以我确信这非常简单，我只是错过了它，但我需要为 BST 创建一个未排序的数组。我有一个数组 int[] data = { 50, 30, 60, 10, 80, 55, 40 };无论我将其更改为什么，我都需要将其转换为以第一个数字为根的不平衡二叉搜索树，其他数字遵循左右规则。我有这段代码适用于该数组，但如果我将数字更改为不在中间的数字，则无效。

 public Node arraytoBinary(int [] array, int start, int end) {
    if (start > end){
        return null;
    }
    int mid = (start + end) / 2;
    Node node = new Node(array[mid]);
   node.left = arraytoBinary(array, start, mid - 1);
   node.right = arraytoBinary(array, mid + 1, end);

    return node;
}    

Answer 1

我真的不明白为什么你尝试分割数组，看起来你正在对值及其顺序做出一些假设。 (虽然说实话我还没有运行你的代码)你不能想当然地认为你将要走的方向(左，右)。它取决于当前元素的值和当前节点持有的值。

我的方法是定义一个 insert(Node node, int value) 方法，并让 arrayToBinary 简单地迭代数组并调用 insert。这将为您提供一个具有最小界面的干净树。另外，它基于 BST 的定义和插入逻辑，因此应该很直观。

(伪为您高兴)
插入

<小时/>

Node insert(node, value)
    if node is null
        // Create a leaf.
        // It might be the root...
        return new Node(value)

    // It's occupied, see which way to
    // go based on its value

    // right? ...
    if value > node.value
        node.right = insert(node.right, value)

    // or left?
    else if value < node.value
        node.left = insert(node.left, value)

    // Code is not handling dups.
    return node

<小时/>

转化

<小时/>

Node arrayToBinary(array, root)
    for e in array
        root = insert(root, e)
    return root

<小时/>

这会将第一个元素保留为根，并按预期插入数组的其余部分。