Skip to content

11530: 【原1530】字符二叉树

题目

题目描述

author: 金耀楠 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1530 ## Description

Stephen最近学习了二叉树的有关内容，他创造了一种树“字符二叉树”。字符二叉树是这样的：

  1. 该二叉树是完全二叉树。
  2. 每个节点下面有0~2个孩子。

为了简单化，我们按照层序方式插入。比如说：HEADSHOT，H作为根节点，EA作为H的两个孩子结点。而DS作为E的孩子，HO作为A的孩子。T是D的左孩子。

Stephen想向TX们炫耀，无奈他只会插入操作，TX们要支持编码，解码，还要支持三种方式的遍历。Stephen请你编程解决问题。

Input Format

第一行是一个数字t代表测试数据个数。

接下来t行，每行描述了一组测试数据。每组数据如下格式：

数据的第一行为一个数n，和两个字符串，分别代表所操作字符串长度和两个命令。（第一个命令为：“INORDER”、“PREORDER”或“POSTORDER”，第二个为“ENCODE”或“DECODE”）

第二行为一个长度为n的字符串S，即所操作字符串。（由‘A’到‘Z’组成）

Output Format

输出t行，每行一个字符串。

当第二个命令为“ENCODE”时，即“编码”：将S作为HS08TTC的层序遍历，输出其中序遍历（“INORDER”），前序遍历（“PREORDER”）或后序遍历（“POSTORDER”）。

当第二个命令为“DECODE”时，即“解码”：S作为中序遍历（“INORDER”），前序遍历（“PREORDER”）或后序遍历（“POSTORDER”），求层序遍历。

Sample Input

8
10 INORDER ENCODE
ENCODETHIS
8 INORDER DECODE
FDEBDEAE
8 INORDER ENCODE
DEADBEEF
8 POSTORDER ENCODE
DEADBEEF
8 POSTORDER DECODE
DEADBEEF
8 PREORDER ENCODE
DEADBEEF
8 PREORDER DECODE
DEDFBAEE
14 POSTORDER DECODE
VENSAYONNLAOHJ
EEEEEE..

Sample Output

HOINSDEECT
DEADBEEF
FDEBDEAE
FDBEEEAD
FDEEABED
DEDFBAEE
DEADBEEF
JOHNYLOVESANNA

Limit

对于30%的数据：t<=10，n<=1000。

对于100%的数据：t<=10，n<=1000000。

ligongzzz's solution 

#include "iostream"
#include "cstdio"
#include "queue"
#include "cmath"
#include "stack"
#include "cstring"
using namespace std;

//二叉树类
template <class T>
class myBinaryTree {
public:
    class node {
    public:
        T data;
        node *lchild = nullptr, *rchild = nullptr;
    };
    node *root = nullptr;
    node **nodeList = nullptr;
    long long sizeOfTree = 0;

    //创建一个相应大小的树
    void createTree(int num) {
        nodeList = new node*[num + 1]{ nullptr };
        sizeOfTree = num;
    }
    //创建结点（全部完成后需要CheckRoot进行根节点识别）
    void createNode(int nodeNum, int lchild, int rchild, T data) {
        if (nodeList[nodeNum] == nullptr)
            nodeList[nodeNum] = new node;

        nodeList[nodeNum]->data = data;

        if (lchild != 0) {
            if (nodeList[lchild] == nullptr)
                nodeList[lchild] = new node;
            nodeList[nodeNum]->lchild = nodeList[lchild];
        }

        if (rchild != 0) {
            if (nodeList[rchild] == nullptr)
                nodeList[rchild] = new node;
            nodeList[nodeNum]->rchild = nodeList[rchild];
        }
    }
    //创建一个num大小的树，数据为treeData
    void createTree(T* treeData, int num) {
        createTree(num);
        for (int i = 1; i <= num; i++) {
            int lchild = i * 2 <= num ? i * 2 : 0,
                rchild = i * 2 + 1 <= num ? i * 2 + 1 : 0;
            createNode(i, lchild, rchild, treeData[i - 1]);
        }
        root = nodeList[1];
    }
    //创建一个空的完全二叉树
    void createNullTree(int num) {
        createTree(num);
        nodeList[1] = new node;
        for (int i = 1; i <= num; i++) {
            if (i * 2 <= num) {
                nodeList[i * 2] = new node;
                nodeList[i]->lchild = nodeList[i * 2];
            }
            if (i * 2 + 1 <= num) {
                nodeList[i * 2 + 1] = new node;
                nodeList[i]->rchild = nodeList[i * 2 + 1];
            }
        }
        root = nodeList[1];
    }
    void checkRoot() {
        for (int i = 1; i <= sizeOfTree; i++) {
            if (nodeList[i]->parent == nullptr) {
                root = nodeList[i];
                break;
            }
        }
    }

    //清空
    void clear() {
        clear(root);
    }

    void clear(node *p) {
        if (p == nullptr)
            return;
        clear(p->lchild);
        clear(p->rchild);
        delete p;
        p = nullptr;
    }

    //构造
    myBinaryTree() {}

    //析构
    ~myBinaryTree() {
        clear(root);
    }

    //判断是否非空
    bool empty() {
        return root == nullptr;
    }


    //返回大小
    long long size() {
        return sizeOfTree;
    }

    //迭代器
    class preorderIterator {
    public:
        stack<node*> myStack;
        node* currentData = nullptr;
        friend preorderIterator myBinaryTree::preorderBegin();
        T& get() {
            return currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr&&myStack.empty();
        }

        preorderIterator& operator++() {
            if (finish())
                return *this;
            if (myStack.empty()) {
                currentData = nullptr;
                return *this;
            }
            currentData = myStack.top();
            myStack.pop();
            if (currentData->rchild != nullptr)
                myStack.push(currentData->rchild);
            if (currentData->lchild != nullptr)
                myStack.push(currentData->lchild);
            return *this;
        }
    };

    preorderIterator preorderBegin() {
        preorderIterator result;
        result.myStack.push(root);
        ++result;
        return result;
    }

    class inorderIterator {
    public:
        stack<node*> myStack;
        node* currentData = nullptr;
        friend inorderIterator myBinaryTree::inorderBegin();

        T& get() {
            return currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr&&myStack.empty();
        }

        inorderIterator& operator++() {
            if (finish())
                return *this;
            if (myStack.empty()) {
                currentData = nullptr;
                return *this;
            }
            currentData = myStack.top();
            myStack.pop();
            for (node* p = currentData->rchild; p != nullptr; p = p->lchild)
                myStack.push(p);
            return *this;
        }
    };

    inorderIterator inorderBegin() {
        inorderIterator result;
        for (node* p = root; p != nullptr; p = p->lchild)
            result.myStack.push(p);
        ++result;
        return result;
    }

    class postorderIterator {
    public:
        stack<node*> myStack;
        node* currentData = nullptr;
        friend postorderIterator myBinaryTree::postorderBegin();
        T& get() {
            return currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr&&myStack.empty();
        }

        postorderIterator& operator++() {
            if (finish())
                return *this;
            if (myStack.empty()) {
                currentData = nullptr;
                return *this;
            }
            currentData = myStack.top();
            myStack.pop();
            if (myStack.empty() || myStack.top()->rchild == currentData)
                return *this;
            for (node* p = myStack.top()->rchild; p != nullptr;) {
                myStack.push(p);
                if (p->lchild != nullptr)
                    p = p->lchild;
                else if (p->rchild != nullptr)
                    p = p->rchild;
                else
                    break;
            }
            return *this;
        }
    };

    postorderIterator postorderBegin() {
        postorderIterator result;
        for (node* p = root; p != nullptr;) {
            result.myStack.push(p);
            if (p->lchild != nullptr)
                p = p->lchild;
            else if (p->rchild != nullptr)
                p = p->rchild;
            else
                break;
        }
        ++result;
        return result;
    }

    //层序遍历迭代器
    class levelIterator {
    public:
        queue<node*> myQueue;
        node* currentData = nullptr;
        friend levelIterator myBinaryTree::levelBegin();
        T& get() {
            return currentData->data;
        }
        //遍历结束或内容为空
        bool finish() {
            return currentData == nullptr&&myQueue.empty();
        }

        levelIterator& operator++() {
            if (finish())
                return *this;
            if (myQueue.empty()) {
                currentData = nullptr;
                return *this;
            }
            currentData = myQueue.front();
            myQueue.pop();
            if (currentData->lchild != nullptr)
                myQueue.push(currentData->lchild);
            if (currentData->rchild != nullptr)
                myQueue.push(currentData->rchild);
            return *this;
        }
    };

    levelIterator levelBegin() {
        levelIterator result;
        result.myQueue.push(root);
        ++result;
        return result;
    }



    //层次遍历
    vector<T*> levelTraversal() {
        if (sizeOfTree == 0)
            return *new vector<T*>;

        vector<T*> result;
        queue<node*> treeQueue;

        //根结点入队
        treeQueue.push(root);

        //层次遍历
        while (!treeQueue.empty()) {
            //出队
            node* temp = treeQueue.front();
            treeQueue.pop();

            //入队
            if (temp->lchild != nullptr)
                treeQueue.push(temp->lchild);
            if (temp->rchild != nullptr)
                treeQueue.push(temp->rchild);

            //写入
            result.push_back(&temp->data);
        }

        //返回
        return result;
    }

    //前序遍历
    vector<T*> preorderTraversal() {
        vector<T*> result;
        preorderTraversal(root, result);
        return result;
    }

    void preorderTraversal(node* treeRoot, vector<T*> &result) {
        //显示当前
        result.push_back(&treeRoot->data);

        if (treeRoot->lchild != nullptr)
            preorderTraversal(treeRoot->lchild, result);
        if (treeRoot->rchild != nullptr)
            preorderTraversal(treeRoot->rchild, result);
    }

    //中序遍历
    vector<T*> inorderTraversal() {
        vector<T*> result;
        inorderTraversal(root, result);
        return result;
    }

    void inorderTraversal(node* treeRoot, vector<T*> &result) {
        if (treeRoot->lchild != nullptr)
            inorderTraversal(treeRoot->lchild, result);
        //显示当前
        result.push_back(&treeRoot->data);
        if (treeRoot->rchild != nullptr)
            inorderTraversal(treeRoot->rchild, result);
    }

    //后序遍历
    vector<T*> postorderTraversal() {
        vector<T*> result;
        postorderTraversal(root, result);
        return result;
    }

    void postorderTraversal(node* treeRoot, vector<T*> &result) {
        if (treeRoot->lchild != nullptr)
            postorderTraversal(treeRoot->lchild, result);
        if (treeRoot->rchild != nullptr)
            postorderTraversal(treeRoot->rchild, result);
        //显示当前
        result.push_back(&treeRoot->data);
    }
};

int main() {
    int num;
    cin >> num;

    for (; num > 0; num--) {
        int n;
        scanf("%d", &n);
        char order[100], op[100], *str = new char[n + 1];
        scanf("%s %s\n%s", order, op, str);
        //建树
        myBinaryTree<char> bTree;
        if (strcmp(op, "ENCODE") == 0) {
            bTree.createTree(str, n);
            delete str;
            if (strcmp(order, "PREORDER") == 0)
                for (auto p = bTree.preorderBegin(); !p.finish(); ++p)
                    printf("%c", p.currentData->data);
            else if (strcmp(order, "INORDER") == 0)
                for (auto p = bTree.inorderBegin(); !p.finish(); ++p)
                    printf("%c", p.currentData->data);
            else if (strcmp(order, "POSTORDER") == 0)
                for (auto p = bTree.postorderBegin(); !p.finish(); ++p)
                    printf("%c", p.currentData->data);
        }
        else if (strcmp(op, "DECODE") == 0) {
            int i = 0;
            bTree.createTree(str, n);
            if (strcmp(order, "PREORDER") == 0)
                for (auto p = bTree.preorderBegin(); !p.finish(); ++p, ++i)
                    p.currentData->data = str[i];
            else if (strcmp(order, "INORDER") == 0)
                for (auto p = bTree.inorderBegin(); !p.finish(); ++p, ++i)
                    p.currentData->data = str[i];
            else if (strcmp(order, "POSTORDER") == 0)
                for (auto p = bTree.postorderBegin(); !p.finish(); ++p, ++i)
                    p.currentData->data = str[i];
            delete str;
            for (auto p = bTree.levelBegin(); !p.finish(); ++p)
                printf("%c", p.currentData->data);
        }
        printf("\n");
    }

    return 0;
}

Neight99's solution 

#include <cstring>
#include <iostream>

using namespace std;

void eInOrder(char *, int, int);
void ePreOrder(char *, int, int);
void ePostOrder(char *, int, int);
void dInOrder(char *, int, int);
void dPreOrder(char *, int, int);
void dPostOrder(char *, int, int);

char *ans;
int index1;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int N, length;
    char order1[10], order2[10], *S;

    cin >> N;
    for (int i = 0; i < N; i++) {
        cin >> length >> order1 >> order2;

        S = new char[length + 10];
        cin >> S;
        if (strcmp(order1, "INORDER") == 0) {
            if (strcmp(order2, "ENCODE") == 0) {
                eInOrder(S, length, 1);
                cout << '\n';
            } else {
                ans = new char[length + 10];
                index1 = 0;
                dInOrder(S, length, 1);
                ans[length] = 0;
                cout << ans << '\n';
                delete[] ans;
            }
        } else if (strcmp(order1, "PREORDER") == 0) {
            if (strcmp(order2, "ENCODE") == 0) {
                ePreOrder(S, length, 1);
                cout << '\n';
            } else {
                ans = new char[length + 10];
                index1 = 0;
                dPreOrder(S, length, 1);
                ans[length] = 0;
                cout << ans << '\n';
                delete[] ans;
            }
        } else if (strcmp(order1, "POSTORDER") == 0) {
            if (strcmp(order2, "ENCODE") == 0) {
                ePostOrder(S, length, 1);
                cout << '\n';
            } else {
                ans = new char[length + 10];
                index1 = 0;
                dPostOrder(S, length, 1);
                ans[length] = 0;
                cout << ans << '\n';
                delete[] ans;
            }
        }
    }
}

void eInOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    eInOrder(str, len, 2 * pos);
    cout << str[pos - 1];
    eInOrder(str, len, 2 * pos + 1);
}

void ePreOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    cout << str[pos - 1];
    ePreOrder(str, len, 2 * pos);
    ePreOrder(str, len, 2 * pos + 1);
}

void ePostOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    ePostOrder(str, len, 2 * pos);
    ePostOrder(str, len, 2 * pos + 1);
    cout << str[pos - 1];
}

void dInOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    dInOrder(str, len, 2 * pos);
    ans[pos - 1] = str[index1];
    index1++;
    dInOrder(str, len, 2 * pos + 1);
}

void dPreOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    ans[pos - 1] = str[index1];
    index1++;
    dPreOrder(str, len, 2 * pos);
    dPreOrder(str, len, 2 * pos + 1);
}

void dPostOrder(char *str, int len, int pos) {
    if (pos > len) {
        return;
    }

    dPostOrder(str, len, 2 * pos);
    dPostOrder(str, len, 2 * pos + 1);
    ans[pos - 1] = str[index1];
    index1++;
}

q4x3's solution 

/**
 * 完全二叉树
 * 前序/中序/后序和层序互相转化
 * 递归 + bfs
 **/
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <cmath>
#define debug putchar('\n')

using namespace std;

const int MAXN = 1000233;
int t, num, cnt;
char code[MAXN];

int bpow(int a, int b) {
    int ans = 1;
    while(b > 0) {
        if(b & 1) ans *= a;
        a *= a;
        b >>= 1;
    }
    return ans;
}

void in_e(int self, int left, int right) {
    if(left >= num) {
        if(self < num)
            putchar(code[self]);
        //debug;
        return;
    }
    else {
        in_e(left, left << 1 | 1, (left << 1 | 1) + 1);
        putchar(code[self]);
        //debug;
        in_e(right, right << 1 | 1, (right << 1 | 1) + 1);
    }
}

void po_e(int self, int left, int right) {
    if(left >= num) {
        if(self < num)
            putchar(code[self]);
        //debug;
        return;
    }
    else {
        po_e(left, left << 1 | 1, (left << 1 | 1) + 1);
        po_e(right, right << 1 | 1, (right << 1 | 1) + 1);
        putchar(code[self]);
        //debug;
    }
}

void pr_e(int self, int left, int right) {
    if(left >= num) {
        if(self < num)
            putchar(code[self]);
        //debug;
        return;
    }
    else {
        putchar(code[self]);
        //debug;
        pr_e(left, left << 1 | 1, (left << 1 | 1) + 1);
        pr_e(right, right << 1 | 1, (right << 1 | 1) + 1);
    }
}

void in_d() {
    int ql[MAXN], qr[MAXN];
    int h, head = 0, rear = 0;
    ql[rear] = 0, qr[rear] = num - 1, ++ rear;
    while(head != rear) {
        int topl = ql[head], topr = qr[head];
        h = log2(double(topr - topl + 1)) + 1;
        ++ head;
        if(h == 1) {
            putchar(code[topl]);
            //debug;
            continue;
        } else {
            int tmp = bpow(2, h - 2);
            if(topr - topl + 2 - (tmp << 1) >= tmp) {
                ql[rear] = topl;
                qr[rear] = topl + (tmp << 1) - 2;
                ++ rear;
                putchar(code[topl + (tmp << 1) - 1]);
                //debug;
                ql[rear] = topl + (tmp << 1);
                qr[rear] = topr;
                if(ql[rear] <= qr[rear])
                    ++ rear;
            } else {
                ql[rear] = topl;
                qr[rear] = topr - tmp;
                ++ rear;
                putchar(code[topr - tmp + 1]);
                //debug;
                ql[rear] = topr - tmp + 2;
                qr[rear] = topr;
                ++ rear;
            }
        }
    }
}

void po_d() {
    int ql[MAXN], qr[MAXN];
    int h, head = 0, rear = 0;
    ql[rear] = 0, qr[rear] = num - 1, ++ rear;
    while(head != rear) {
        int topl = ql[head], topr = qr[head];
        putchar(code[topr]);
        //debug;
        h = log2(double(topr - topl + 1)) + 1;
        ++ head;
        if(h == 1) {
            continue;
        } else {
            int tmp = bpow(2, h - 2);
            if(topr - topl + 2 - (tmp << 1) >= tmp) {
                ql[rear] = topl;
                qr[rear] = topl + (tmp << 1) - 2;
                ++ rear;
                ql[rear] = topl + (tmp << 1) - 1;
                qr[rear] = topr - 1;
                if(ql[rear] <= qr[rear])
                    ++ rear;
            } else {
                ql[rear] = topl;
                qr[rear] = topr - tmp;
                ++ rear;
                ql[rear] = topr - tmp + 1;
                qr[rear] = topr - 1;
                ++ rear;
            }
        }
    }
}

void pr_d() {
    int ql[MAXN], qr[MAXN];
    int h, head = 0, rear = 0;
    ql[rear] = 0, qr[rear] = num - 1, ++ rear;
    while(head != rear) {
        int topl = ql[head], topr = qr[head];
        putchar(code[topl]);
        //debug;
        h = log2(double(topr - topl + 1)) + 1;
        ++ head;
        if(h == 1) {
            continue;
        } else {
            int tmp = bpow(2, h - 2);
            if(topr - topl + 2 - (tmp << 1) >= tmp) {
                ql[rear] = topl + 1;
                qr[rear] = topl + (tmp << 1) - 1;
                ++ rear;
                ql[rear] = topl + (tmp << 1);
                qr[rear] = topr;
                if(ql[rear] <= qr[rear])
                    ++ rear;
            } else {
                ql[rear] = topl + 1;
                qr[rear] = topr - tmp + 1;
                ++ rear;
                ql[rear] = topr - tmp + 2;
                qr[rear] = topr;
                ++ rear;
            }
        }
    }
}

int main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);
    char tmp1[15], tmp2[15];
    scanf("%d", &t);
    for(int i = 0;i < t;++ i) {
        scanf("%d", &num);
        scanf("%s", tmp1);
        scanf("%s", tmp2);
        scanf("%s", code);
        if(tmp2[0] == 'E') {
            if(tmp1[0] == 'I') {
                in_e(0, 1, 2);
                putchar('\n');
            }
            else if(tmp1[0] == 'P' && tmp1[1] == 'O') {
                po_e(0, 1, 2);
                putchar('\n');
            }
            else {
                pr_e(0, 1, 2);
                putchar('\n');
            }
        } else {
            if(tmp1[0] == 'I') {
                in_d();
                putchar('\n');
            }
            else if(tmp1[0] == 'P' && tmp1[1] == 'O') {
                po_d();
                putchar('\n');
            }
            else {
                pr_d();
                putchar('\n');
            }
        }
    }
    return 0;
}

victrid's solution 

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
//听说要用cin，👴服🌶
char input[1000001]  = {'\0'};
char input2[1000001] = {'\0'};
int indexa;
void printpreorder(int current, int total) {
    if (current >= total)
        return;
    cout << (char)input[current];
    printpreorder((current << 1) + 1, total);
    printpreorder((current << 1) + 2, total);
    return;
}
void printinorder(int current, int total) {
    if (current >= total)
        return;
    printinorder((current << 1) + 1, total);
    cout << (char)input[current];
    printinorder((current << 1) + 2, total);
    return;
}
void printpostorder(int current, int total) {
    if (current >= total)
        return;
    printpostorder((current << 1) + 1, total);
    printpostorder((current << 1) + 2, total);
    cout << (char)input[current];
    return;
}
void estkpreorder(int current, int total) {
    if (current >= total)
        return;
    input[current] = input2[indexa++];
    estkpreorder((current << 1) + 1, total);
    estkpreorder((current << 1) + 2, total);
    return;
}
void estkinorder(int current, int total) {
    if (current >= total)
        return;
    estkinorder((current << 1) + 1, total);
    input[current] = input2[indexa++];
    estkinorder((current << 1) + 2, total);
    return;
}
void estkpostorder(int current, int total) {
    if (current >= total)
        return;
    estkpostorder((current << 1) + 1, total);
    estkpostorder((current << 1) + 2, total);
    input[current] = input2[indexa++];
    return;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t, total;
    char chr[10];
    int ordf;
    cin >> t;
    while (t--) {
        cin >> total;
        cin >> chr;
        ordf = 0;
        if (!strcmp(chr, "INORDER"))
            ordf += 1;
        if (!strcmp(chr, "POSTORDER"))
            ordf += 2;
        cin >> chr;
        if (!strcmp(chr, "DECODE"))
            ;
        if (!strcmp(chr, "ENCODE"))
            ordf += 10;

        switch (ordf) {
        case 0:
            //PREORDER DECODE
            cin >> input2;
            indexa = 0;
            estkpreorder(0, total);
            input[total] = '\0';
            cout << input;
            break;
        case 1:
            //INORDER DECODE
            cin >> input2;
            indexa = 0;
            estkinorder(0, total);
            input[total] = '\0';
            cout << input;
            break;
        case 2:
            //POSTORDER DECODE
            cin >> input2;
            indexa = 0;
            estkpostorder(0, total);
            input[total] = '\0';
            cout << input;
            break;
        case 10:
            //PREORDER ENCODE
            cin >> input;
            printpreorder(0, total);
            break;
        case 11:
            //INORDER ENCODE
            cin >> input;
            printinorder(0, total);
            break;
        case 12:
            //POSTORDER ENCODE
            cin >> input;
            printpostorder(0, total);
            break;
        }
        cout << endl;
    }
    return 0;
}

WashSwang's solution 

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
char cmd1[10],cmd2[10],s[1010000],ans[1010000];
int t,n,top,stack[1050000],vis[1010000];
inline int ls(int x){return x<<1;}
inline int rs(int x){return x<<1|1;}
inline void inorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            top--;
            ans[i++]=s[now-1];
            if (rs(now)<=n) stack[top++]=rs(now);
        }
    }
}
inline void preorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            ans[i++]=s[now-1];
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
            top--;
    }
}
inline void postorderEncode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
        {
            ans[i++]=s[now-1];
            top--;
        }
    }
}
inline void inorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            top--;
            ans[now-1]=s[i++];
            if (rs(now)<=n) stack[top++]=rs(now);
        }
    }
}
inline void preorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            ans[now-1]=s[i++];
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
            top--;
    }
}
inline void postorderDecode(const char* s,int n){
    int i=0,now;
    stack[top++]=1;
    while (top!=0){
        now=stack[top-1];
        if (vis[now]==0){
            vis[now]++;
            if (ls(now)<=n) stack[top++]=ls(now);
        }
        else
        if (vis[now]==1){
            vis[now]++;
            if (rs(now)<=n) stack[top++]=rs(now);
        }
        else
        {
            ans[now-1]=s[i++];
            top--;
        }
    }
}
int main() {
    cin>>t;
    ios::sync_with_stdio(false);
    for (int i=0;i<t;++i){
        top=0;
        memset(ans,0,sizeof(ans));
        memset(vis,0,sizeof(vis));
        cin>>n>>cmd1>>cmd2>>s;
        if (strcmp(cmd1,"INORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                inorderEncode(s,n);
            else
                inorderDecode(s,n);
        }
        if (strcmp(cmd1,"PREORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                preorderEncode(s,n);
            else
                preorderDecode(s,n);
        }
        if (strcmp(cmd1,"POSTORDER")==0){
            if (strcmp(cmd2,"ENCODE")==0)
                postorderEncode(s,n);
            else
                postorderDecode(s,n);
        }
        cout<<ans<<endl;
    }
    return 0;
}