50144. Tree Construction and Queries

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

Task Description

Write functions to construct/query a binary tree. We use a string to construct the tree. The string consists of the characters ‘L’ and ‘R’, indicating that we will add a new node (if it is not already in the tree) to the left or right from the current tree node. Each node of the binary tree also stores the number of times this node was visited during the construction. After we construct the tree we do a preorder traversal and an inorder traversal of the tree to check for correctness.

LRLL
LRRR

In the example above the first string is "LRLL", so we generate a tree accordingly. Since each node has been visited once the counter for each node is one.

The second string is "LRRR". Because we already have a tree, we will add nodes only if they are not in the tree already. We start from the root and follow the string to visit the tree nodes, and add node if necessary. Note that we also increase the counters by one along the path.
The second function queries the counter value of a tree node. Given a direction string as before we want to return the counter value of the node that the string leads to. Note that if the node does not exist, we return 0. The Sample Input 4 is shown in the following figure.
The tree node structure and function prototype is defined in the following header file tree.h.

#ifndef TREE_H_INCLUDED
#define TREE_H_INCLUDED
#define MAXN 128
typedef struct Node{
    int data;
    struct Node *left;
    struct Node *right;
}Node;
Node *construct(Node *root, char instruction[MAXN]);
int query(Node *root, char instruction[MAXN]);
#endif // TREE_H_INCLUDED

The prototype of the function you need to implement is as follows.

Node *construct(Node *root, char instruction[]){
}
int query(Node *root, char instruction[]){
}

You have to use the following main function 1 to test your construct function.

Main function 1

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
void preorder(Node *root) {
    if (root == NULL)
        return ;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}
void inorder(Node *root) {
    if (root == NULL)
        return ;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
int main()
{
    char instruction[MAXN];
    Node *root = NULL;
    while (scanf("%s", instruction) != EOF) {
        root = construct(root, instruction);
        preorder(root);
        printf("\n");
        inorder(root);
        printf("\n");
    }
    return 0;
}

You have to use the following main function 2 to test your query function.

Main function 2

#include <stdio.h>
#include <stdlib.h>
#include "tree.h"
int main()
{
    char instruction[MAXN];
    Node node[7];
    for(int i = 0; i < 7; i++){
        node[i].left = NULL;
        node[i].right = NULL;
    }
    node[0].data = 2;
    node[0].left = &node[1];
    node[1].data = 2;
    node[1].right = &node[2];
    node[2].data = 2;
    node[2].left = &node[3];
    node[2].right = &node[4];
    node[3].data = 1;
    node[3].left = &node[5];
    node[4].data = 1;
    node[4].right = &node[6];
    node[5].data = 1;
    node[6].data = 1;
    Node *root = &node[0];
    while (scanf("%s", instruction) != EOF) {
        printf("%d\n", query(root, instruction));
    }
    return 0;
}

Input Format of main.c

The input has multiple lines and you must process them until EOF. Each line has one string. The length of the string is less than 100.

Output Format of main.c

In subtask 1 and subtask 2, we print the result of a preorder traversal and a inorder traversal of the tree. In subtask 3 and subtask 4, we print the counter value of the node we queried.

Subtasks

  • 10 points : construct a binary tree. The length of each instruction is 1.
  • 40 points : construct a binary tree. The length of each instruction may be greater than 1.
  • 10 points : Query the counter value of a node and the node must exist.
  • 40 points : Query the counter value of a node and the node may not exist.

Sample Input 1 with main function 1

R
L

Sample Output 1 with main function 1

1 1
1 1
2 1 1
1 2 1

Sample Input 2 with main function 1

LRLL
LRRR

Sample Output 2 with main function 1

1 1 1 1 1
1 1 1 1 1
2 2 2 1 1 1 1
2 1 1 2 1 1 2

Sample Input 3 with main function 2

L
LRLL
LRR

Sample Output 3 with main function 2

2
1
1

Sample Input 4 with main function 2

LR
LLL

Sample Output 4 with main function 2

2
0

Attention

tree.c must contain construct and query functions. If you only complete one of them, the other still has to be written but it can be empty. An example is as follows.

Node *construct(Node *root, char instruction[]){
    ...
}
int query(Node *root, char instruction[]){
}

Discussion