將排序後的數組插入到二叉查找樹中

Question

我想實現一種將排序後的數組插入到二叉搜索樹中的算法，但是我不想結束只能增長到一側的樹。

你有什麼想法嗎？

謝謝。

Answer 1

這應該給你一個平衡樹（在爲O（n））：

1. 構建一個節點中間元素在數組中並返回它
   （這將是基本情況下的根）。
2. 從數組左半部分重複1.將返回值分配給根的左子元素。
3. 從數組的右半部分重複1.將返回值分配給根的右側子節點。

類似Java的代碼：從here衍生

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

插入他們的僞隨機順序，就像這裏：

#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; 
} 

Answer 3

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; 
    } 
}