Sequence to Binary Tree

[littlehug]

Write a function to convert an integer sequence to a binary tree.

Task Description

You are given an unsorted sequence of N integers. Each integer value is unique, and it has an index from 0 to N-1. You need to convert the sequence to a binary tree according the preprocessing flag MAXLENGTH. When MAXLENGTH is set as k, the k-th largest integer will be picked as the root of the binary tree. Assume its index is t. All integers with indices less than t will be placed into the left subtree and all integers with indices larger than t will be placed into the right subtree. This recursion then goes on the left and right subtrees. Note that if there are less than k integers in the sequence, the binary tree has a sequence of nodes linked by the left pointer as a linked list. And you link the nodes according their indices in descending order.

For example, the integer sequence is {2, 0, 1, 7, 12, 21, 8, 33} and MAXLENGTH is set as 3. The third largest integer in the sequence is 12, so 12 is picked as root and we partition the sequence into two sequences -- {2, 0, 1, 7} and {21, 8, 33}. Then we recursively find the fourth largest integer from them. After finding 1 for the partition on the left subtree and 8 for the right subtree, all remaining sequences have less than four integers, so we link them as a linked list.The final tree is as follows.

figure

When the integer sequence is {2, 0, 1, 7, 12, 21, 8, 33} and MAXLENGTH is set as 5, the binary tree you construct is as followed.

figure

We define tree node as followed. Note that all pointers that do not link to any node must be set as NULL.

typedef struct node{
    int value;
    struct node*left;
    struct node*right;
}Node;

Please write a function to construct the binary tree. The prototype of the function is as followed.

Node*ConstructTree(int sequence[],int N);

You may use the following main function to test your program.

#include <stdio.h>
#include "construct.h"
#define MAXN 16384

int sequence[MAXN];

void PrintTree( Node *root ){
    if (root == NULL)
        return;
    printf("%d\n", root->value);
    PrintTree(root->left);
    PrintTree(root->right);
    return;
}
int main(){
    int N;
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        scanf("%d", &sequence[i]);
    Node *tree = ConstructTree( sequence, N );
    PrintTree( tree );
    return 0;
}

The construct.h is as followed.

#ifndef CONSTRUCT
#define CONSTRUCT
typedef struct node{
    int value;
    struct node *left, *right;
} Node;
Node *ConstructTree(int sequence[], int N);
#endif

Subtask

• 10 points: It is guaranteed you can find the root at the top level of the binary tree, and none at the second level.

• 20 points: It is guaranteed you can find the root at the top level and the second level of the binary tree, but none at the third level.

• 70 points: Nothing is guaranteed.

  Input Format

  The input contains only one test case. The first line contains one integers N, representing the number of sequence. The second line contains N integers, s0, s1, … , sn-1, representing the value of index.

• 0 < N < 16384

  Output Format

  Print all the values of nodes in the tree by pre-ordering, and each node in a line.

• When you compile the program with the command in the next line, the I/O is as followed.

  gcc -std=c99 -O2 main.c construct.c -DMAXLENGTH=5

  Sample Input 1

  8
  2 0 1 7 12 21 8 33

  Sample Output 1

  7
  1
  0
  2
  33
  8
  21
  12

• When you compile the program with the command in the next line, the I/O is as followed.

  gcc -std=c99 -O2 main.c construct.c -DMAXLENGTH=3

  Sample Input 2

  8
  2 0 1 7 12 21 8 33

  Sample Output 2

  12
  1
  0
  2
  7
  8
  21
  33

• When you compile the program with the command in the next line, the I/O is as followed.

  gcc -std=c99 -O2 main.c construct.c -DMAXLENGTH=2

  Sample Input 3

  8
  2 0 1 7 12 21 8 33

  Sample Output 3

  21
  7
  1
  0
  2
  12
  8
  33

  Note

  Please use the following algorithm to find the k-th largest element in an array A. First we copy the first k elements of A into another array B and sort them. Then we compare each of the rest of elements in A with the last element in B. If it is larger than the last element of A then we place it into the end of B, then compare it with the element to its right. That is, we keep moving to its left and swap with elements that are smaller than it. Eventually we will stop because we will either encounter a larger element, or we have reached the beginning of B. After processing all elements of A then we know the k-th largest element in A because it will be at the end of array B.