algorithm - 将排序后的数组插入二叉搜索树

Question

我想实现一种算法，将排序后的数组插入二叉搜索树，但我不想最终得到一棵只长到一侧的树。

你有什么想法？

谢谢。

Answer 1

这应该给你一个平衡的树（在 O(n) 中）：

1. 为数组中的中间元素构造一个节点并返回它
   （这将是基本情况下的根）。
2. 从 1. 在数组的左半部分重复，将返回值分配给根的左孩子。
3. 从 1. 在数组的右半部分重复，将返回值分配给根的右孩子。

类 Java 代码：

TreeNode sortedArrayToBST(int arr[], int start, int end) {
  if (start > end) return null;
  // same as (start+end)/2, avoids overflow.
  int mid = start + (end - start) / 2;
  TreeNode node = new TreeNode(arr[mid]);
  node.left = sortedArrayToBST(arr, start, mid-1);
  node.right = sortedArrayToBST(arr, mid+1, end);
  return node;
}

TreeNode sortedArrayToBST(int arr[]) {
  return sortedArrayToBST(arr, 0, arr.length-1);
}

代码来源于这里。

Answer 2

public class SortedArrayToBST {
    public TreeNode sortedArrayToBST(int[] num) {
        if (num == null) {
            return null;
        }
        return buildBST(num, 0, num.length - 1);
    }

    private TreeNode buildBST(int[] num, int start, int end) {
        if (start > end) {
            return null;
        }
        int mid = start + (end - start) / 2;
        TreeNode root = new TreeNode(num[mid]);
        TreeNode left = buildBST(num, start, mid - 1);
        TreeNode right = buildBST(num, mid + 1, end);
        root.left = left;
        root.right = right;
        return root;
    }
}

Answer 3

以伪随机顺序插入它们，如下所示：

#include <stdio.h>

int array[] = {1,2,3,4,5,6,7,8,9,10};

#define COUNT 10
#define STEP 7  /* must be relatively prime wrt COUNT */
#define START 5 /* not important */

int main(void)
{
unsigned idx;

idx=START;
while(1) {
        printf("[%u] = %u\n", idx, array[idx] );
        // do_insert(array[idx] );
        idx = (idx + STEP ) % COUNT;
        if (idx == START) break;
        }
return 0;
}