#include <iostream>

using namespace std;

typedef struct ThBTNode {
    char data;
    ThBTNode *l_child;
    ThBTNode *r_child;
    int l_tag, r_tag;
    //l_tag=1表示指向前驱，l_tag=0表示指向左孩子
    //r_tag=1表示指向后继，r_tag=0表示指向右孩子
} ThBTNode;

ThBTNode *pre = nullptr;//指向当前访问节点的前驱

void PreThread(ThBTNode *t);

ThBTNode *CreateBTree(ThBTNode *t);//创建二叉树

void CreatePreThBTree(ThBTNode *t);

void vision(ThBTNode *q);

int main() {
    ThBTNode *T = nullptr;
    CreateBTree(T);
    CreatePreThBTree(T);
    return 0;
}

void CreatePreThBTree(ThBTNode *t) {
    PreThread(t);
    //为了处理最后一个节点
    if (pre->r_child == nullptr)
        pre->r_tag = 1;
}

void PreThread(ThBTNode *t) {
    //先序遍历创建线索
    if (t != nullptr) {
        vision(t);
        //因为线索化的时候会将t所指向节点的l_child指向前一个节点
        //结果就会导致进行无限循环
        if (t->l_tag == 0)
            PreThread(t->l_child);
        PreThread(t->r_child);
    }
}

void vision(ThBTNode *q) {
    if (q->l_child == nullptr) {
        q->l_child = pre;
        q->l_tag = 1;
    }
    if (pre != nullptr && pre->r_child == nullptr) {
        pre->r_child = q;
        pre->r_tag = 1;
    }
    pre = q;
}

ThBTNode *CreateBTree(ThBTNode *t) {
    //采用先序遍历创建二叉树
    char data;
    cin >> data;
    if (data == '#')
        t = nullptr; //创建空树
    else {
        t = new ThBTNode;
        t->data = data;
        //将所有标志都初始化为0
        t->l_tag = 0;
        t->r_tag = 0;

        t->l_child = CreateBTree(t->l_child);
        t->r_child = CreateBTree(t->r_child);
    }
    return t;
}