將一個數組轉換成深度最低的二叉樹

問題定義：

Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height.

思路：

這題還是比較簡單的，從已排序的數組和高度最低的二叉樹這兩個關鍵詞中就可以得到一些啟發，類似與二分查找，將最中間的元素作為根節點，左邊的元素插入到左子樹，右邊的元素插入到右子樹即可，最後實現了一個二叉查找樹。

代碼如下：

1. #include <algorithm>   
2. #include <stdio.h>   
3. #include <time.h>   
4.   
5. struct node   
6. {  
7.         int data;  
8.         struct node * lchild;  
9.         struct node * rchild;  
10. };  
11.   
12. //將數組轉換為深度最低的二叉樹，采用了二分查找的思想   
13. struct node* ConvertArrayToTree(int data[], int first, int last)  
14. {  
15.         if (last < first)   
16.         {  
17.                 return NULL;  
18.         }  
19.         else  
20.         {  
21.                 int mid = ( last + first ) / 2;  
22.                 struct node * newNode = NULL;  
23.                 newNode = (struct node *)malloc(sizeof(struct node));  
24.                 newNode->data = data[mid];  
25.                 newNode->lchild = ConvertArrayToTree(data, first, mid - 1);  
26.                 newNode->rchild = ConvertArrayToTree(data, mid + 1, last);  
27.                 return newNode;  
28.         }  
29. }  
30.   
31. //中序遍歷   
32. void Traverse(struct node *root)  
33. {  
34.         if (root == NULL)   
35.         {  
36.                 return;  
37.         }  
38.         Traverse(root->lchild);  
39.         printf("%d\t", root->data);  
40.         Traverse(root->rchild);  
41.           
42. }  
43. int main(int argc, char* argv[])  
44. {  
45.         const int SIZE = 100;  
46.         int data[SIZE];  
47.         int i, j;  
48.         int flag = 1;  
49.         struct node *head = NULL;  
50.         srand(time(0));  
51.         for (i = 0; i < SIZE; i++)   
52.         {  
53.                 data[i] = rand() % SIZE;  
54.                 flag *= -1;  
55.                 data[i] *= flag;  
56.         }  
57.   
58.         std::sort(data, data + SIZE);  
59.         for (i = 0; i < SIZE; i++)   
60.         {  
61.                 printf("%d\t", data[i]);  
62.         }  
63.         printf("\n");  
64.   
65.         head = ConvertArrayToTree(data, 0, SIZE - 1);  
66.         Traverse(head);  
67.         printf("\n");  
68.   
69.         return 0;  
70. }