将一个数组转换成深度最低的二叉树

将一个数组转换成深度最低的二叉树

问题定义：

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