하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다

문제 정의:
        Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height.
생각:
이 문제는 비교적 간단하다. 이미 정렬된 수조와 높이가 가장 낮은 두 갈래 나무라는 두 키워드에서 깨우침을 얻을 수 있다. 이분 찾기와 유사하게 가장 중간 요소를 뿌리 노드로 하고 왼쪽 요소를 왼쪽 나무에 삽입하고 오른쪽 요소를 오른쪽 나무에 꽂으면 된다. 마지막으로 두 갈래 찾기 나무를 실현했다.
코드는 다음과 같습니다.

#include <algorithm>
#include <stdio.h>
#include <time.h>

struct node 
{
        int data;
        struct node * lchild;
        struct node * rchild;
};

// ， 
struct node* ConvertArrayToTree(int data[], int first, int last)
{
        if (last < first) 
        {
                return NULL;
        }
        else
        {
                int mid = ( last + first ) / 2;
                struct node * newNode = NULL;
                newNode = (struct node *)malloc(sizeof(struct node));
                newNode->data = data[mid];
                newNode->lchild = ConvertArrayToTree(data, first, mid - 1);
                newNode->rchild = ConvertArrayToTree(data, mid + 1, last);
                return newNode;
        }
}

// 
void Traverse(struct node *root)
{
        if (root == NULL) 
        {
                return;
        }
        Traverse(root->lchild);
        printf("%d\t", root->data);
        Traverse(root->rchild);
        
}
int main(int argc, char* argv[])
{
        const int SIZE = 100;
        int data[SIZE];
        int i, j;
        int flag = 1;
        struct node *head = NULL;
        srand(time(0));
        for (i = 0; i < SIZE; i++) 
        {
                data[i] = rand() % SIZE;
                flag *= -1;
                data[i] *= flag;
        }

        std::sort(data, data + SIZE);
        for (i = 0; i < SIZE; i++) 
        {
                printf("%d\t", data[i]);
        }
        printf("
");

        head = ConvertArrayToTree(data, 0, SIZE - 1);
        Traverse(head);
        printf("
");

        return 0;
}