50029. Tree Construction

I'm a slow walker, but I never walk backwards.

Problem Description

Construct a binary tree in a level-by-level fashion. You will be given an array of n elements, and you will construct a tree with root having array[0] as the level, which has array[1] as it left child, and array[2] as its right child, and so on. Your function should return a pointer to the root of the constructed tree.

Node *construct(int array[], int n);

The definition of a Node is as follows.

tree.h

#ifndef _TREE_H
#define _TREE_H
 
typedef struct Node {
    int label;
    struct Node *left, *right;
} Node;
 
Node* construct(int array[], int n);
 
#endif

Subtasks

  • 5pt. $n = 1$
  • 5pt. $n = 2$
  • 10pt. $n = 3$
  • 30pt. $n$ is no more than $100$.
  • 50pt. $n$ is no more than $1000$.

Hint

It is easy to see that the left child of array[i] is array[2 * i + 1] and the right child is array[2 * i + 2], so it is easy to construct the tree recursively.

p10071p10071

p10071p10071

main.c (test)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include "tree.h"
 
void printAndFree(Node *u) {
    if (u == NULL)    return ;
    printf("%d ", u->label);
    printAndFree(u->left);
    printAndFree(u->right);
    free(u);
}
 
int main() {
    int A[32767], n;
    while (scanf("%d", &n) == 1 && n != 0) {
        for (int i = 0; i < n; i++)
            scanf("%d", &A[i]);
        Node *root = construct(A, n);
        printAndFree(root);
        puts("");
    }
    return 0;
}

Sample Input

1
8
3
1 3 2
8
1 2 3 7 5 1 1 6

Sample Output

8
1 3 2
1 2 7 6 5 3 1 1

Discussion