50113. Ternary Search Tree

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

Build a ternary search tree with an array of distinct positive integers.

Task Description

You are given an array of $N$ unique and positive integers. Please convert the array into a ternary search tree.

Each node of a ternary search tree stores at most two integers -- the smaller $S$ and the larger $L$. Each node has three pointers, left, mid, and right, and each pointer points to a subtree. All integers in the left subtree are smaller than $S$, all integers in the mid subtree are larger than S and smaller than L, and all integers in the right subtree are larger than L. Note that if a node stores only one integer k, you need to store it as the larger one, and set the small one to -1.

When the integer sequence is {9, 5, 2, 7}, we build the ternary tree as follows. Note that all pointers that do not link to any node must be set to NULL.

exampleexample

We define a tree node as follows.

1
2
3
4
typedef struct node{
    int small,large;
    struct node *left,*mid,*right;
} Node;

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

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

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

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 "construct.h"
#define MAXN 32768
int sequence[MAXN];
void PrintTree( Node *root ){
    if (root == NULL)
        return;
    printf("%d %d\n", root->small, root->large);
    PrintTree(root->left);
    PrintTree(root->mid);
    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.

1
2
3
4
5
6
7
8
#ifndef CONSTRUCT
#define CONSTRUCT
typedef struct node{
    int small,large;
    struct node *left,*mid,*right;
}Node;
Node*ConstructTree(int sequence[],int N);
#endif

Subtask

  • 10 points: $N = 1$.
  • 10 points: $N = 2$.
  • 20 points: $N = 4$.
  • 60 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, $s_{0}$, $s_{1}$, … , $s_{n-1}$, representing the value of index.

  • $0 \lt N \lt 32768$.

Output Format

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

Compile

gcc -std=c99 -O2 -c construct.c
gcc -std=c99 -O2 -c main.c -lm
gcc -std=c99 -O2 main.o construct.o

Sample Input 1

1
9

Sample Output 1

-1 9

Sample Input 2

2
9 5

Sample Output 2

5 9

Sample Input 3

4
9 5 2 7

Sample Output 3

5 9
-1 2
-1 7

Sample Input 4

6
5 1 18 20 42 22

Sample Output 4

1 5
18 20
22 42

Discussion