50106. Construct a Binary Search Tree

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

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:

figurefigure

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

figurefigure

Note

It is guaranteed that all the heights and all the weights are different. You need to construct the binary search tree in the order of the students appear in the input. 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.

The binary search tree sample code from the textbook: bstree.c

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

1
2
3
4
5
6
7
8
9
10
11
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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: There 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 \lt N \lt 1025$
  • 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.

Sample Input 1

Compile with flag -DHEIGHT

3
John 175 70
Tom 160 80
Mary 165 45

Sample Output 1

John
Tom
Mary

Sample Input 2

Compile with flag -DWEIGHT

3
John 175 70
Tom 160 80
Mary 165 45

Sample Output 2

John
Mary
Tom

Discussion