Construct a Binary Search Tree

Write a function to construct a binary search tree according to the weight or the height.

Task Description

You are given N students’ names, heights and weight. You need to construct a binary search tree according to the compiler flag.

If the flag HEIGHT is defined, you need to construct the binary search tree according to the students’ heights.
If the flag WEIGHT is defined, you need to construct the binary search tree according to the students’ weights.

For example, we are given students’ informations as follows:

Name	Height	Weight
John	175	70
Tom	160	80
Mary	165	45

If we compile with flag -DHEIGHT, we need to construct the binary search tree according to the students’ heights as follows: figure

And, If we compile with flag -DWEIGHT, we need to construct the binary search tree according to the students’ weights as follows: figure

Note

It is guaranteed that all the heights and all the weights are different. Exactly one of the HEIGHT and WEIGHT flag will be defined. All pointers that do not link to any node must be set to NULL.

Please construct the binary search tree in the function, Node *ConstructBSTree( … ), then return the pointer of the root. The main program and the prototype of function ConstructBSTree are as followed:

/* construct.h */
#ifndef CONSTRUCT
#define CONSTRUCT
typedef struct Node{
    char name[16];
    int height;
    int weight;
    struct Node *left, *right;
} Node;

Node *ConstructBSTree(int N, char name[][16], int height[], int weight[]);
#endif

/* main.c */
#include <stdio.h>
#include "construct.h"

#define MAXN 1024
char name[MAXN][16];
int height[MAXN];
int weight[MAXN];

void PrintBSTree( Node *root ){
    if (root == NULL)
        return;
    printf("%s\n", root->name);
    PrintBSTree(root->left);
    PrintBSTree(root->right);
    return;
}

int main(){
    int N;
    scanf("%d", &N);
    for (int i=0; i<N; i++)
        scanf("%s %d %d", name[i], &height[i], &weight[i]);

    Node *tree = ConstructBSTree( N, name, height, weight );

    PrintBSTree( tree );
    return 0;
}

Compile

gcc -std=c99 -O2 -DHEIGHT main.c construct.c -o test1
gcc -std=c99 -O2 -DWEIGHT main.c construct.c -o test2

Subtask

10 points: There is only one student.
20 points: There are no more than three students.
70 points: The is no guaranteed on the number of students.

Input Format

The input contains only one test case. The first line contains an integers N, representing the number of student. For the following N lines, each line contains a string and two integers which are the student’s name, height and weight.
0 < N < 1024
The length of a student’s name is less than 16, and the name doesn't contain any whitespaces.

Output Format

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

Compile with flag -DHEIGHT

Sample Input 1

3
John 175 70
Tom 160 80
Mary 165 45

Sample Output 1

John
Tom
Mary

Sample Input 2

3
John 175 70
Tom 160 80
Mary 165 45

Sample Output 2

John
Mary
Tom

pangfengliu / programmingtasks