Untitled

 avatar
unknown
c_cpp
2 years ago
2.8 kB
1
Indexable
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct _Node
{
    int data;
    struct _Node *parent, *left, *right;
} BTNode;

int n, flag = 0, pos = 0;
int visited[3005];
int route[3005];
BTNode *ptr_arr[3005];

void init();
void Find_Node(int Fr, int To);
void Show();
void Free_Node();

int main(void)
{
    freopen("test.txt", "r", stdin);
    freopen("out.txt", "w", stdout);

    scanf("%d", &n);
    init();

    for (int i = 1; i <= n; ++i)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        ptr_arr[i]->left = ptr_arr[a];
        ptr_arr[i]->right = ptr_arr[b];
        if (a != 0)
            ptr_arr[a]->parent = ptr_arr[i];
        if (b != 0)
            ptr_arr[b]->parent = ptr_arr[i];
    }

    scanf("%d", &n);
    for (int i = 0; i < n; ++i)
    {
        int a, b;

        flag = 0;
        pos = 0;
        scanf("%d %d", &a, &b);
        printf("%d\n", b);
        Find_Node(a, b);
    }
    Free_Node();
}

void init()
{
    visited[0] = 1;

    for (int i = 1; i <= n; ++i)
    {
        BTNode *new = malloc(sizeof(BTNode));
        new->data = i;
        new->parent = NULL;
        new->left = NULL;
        new->right = NULL;
        ptr_arr[i] = new;
    }
}

void Find_Node(int Fr, int To)
{
    int next = 0;
    if (flag)
        return;

    if (Fr == To)
    {
        flag = 1;
        Show();
        return;
    }

    if (ptr_arr[Fr]->left != NULL)
    {
        next = (ptr_arr[Fr]->left)->data;
        if (visited[next] == 0)
        {
            printf("->L; Fr = %d, To = %d\n", next, To);
            visited[Fr] = 1;
            route[pos++] = 1;
            Find_Node(next, To);
            route[pos--] = 0;
        }
    }

    if (ptr_arr[Fr]->right != NULL)
    {
        next = (ptr_arr[Fr]->right)->data;
        if (visited[next] == 0)
        {
            printf("->R; Fr = %d, To = %d\n", next, To);
            visited[Fr] = 1;
            route[pos++] = 2;
            Find_Node(next, To);
            route[pos--] = 0;
        }
    }

    if (ptr_arr[Fr]->parent != NULL)
    {
        next = (ptr_arr[Fr]->parent)->data;
        if (visited[next] == 0)
        {
            printf("->P; Fr = %d, To = %d\n", next, To);
            visited[Fr] = 1;
            route[pos++] = 3;
            Find_Node(next, To);
            route[pos--] = 0;
        }
    }
}

void Show()
{
    for (int i = 0; i < pos; ++i)
    {
        int ans = route[i];
        if (ans == 3)
            putchar('P');
        else if (ans == 2)
            putchar('R');
        else if (ans == 1)
            putchar('L');
    }
    puts("");

    memset(visited, 0, sizeof(visited));
    memset(route, 0, sizeof(route));
    visited[0] = 1;
}

void Free_Node()
{
    for (int i = 1; i <= n; ++i)
        free(ptr_arr[i]);
}