喜获本题最优劣解

思路：建树 -> 遍历

采取指针存二叉树，代码比较非常乱，请原谅（注释放代码里）。

#include <bits/stdc++.h>

using namespace std;

struct Node {

    int val;

    Node *lson, *rson, *fath;//左儿子 右儿子 父亲

    void mest() { //懒人必备

        lson = rson = fath = NULL;
        val = 0;

        return;
    }

} *node, *root, *tra, *null;

string st;

void make_tree (int x) {

    if (x >= st.size()) return;

    if (st[x] == '.') {

        while (node -> lson != NULL && node -> rson != NULL && node -> fath != NULL) //找到儿子不全的一个父亲
            node = node -> fath;

        if (node -> lson == NULL) 
            node -> lson = null;

        else node -> rson = null;//填坑

        while (node -> rson != NULL && node -> fath != NULL) 
            node = node -> fath;//继续找儿子不全的父亲，铺垫后面的操作

        make_tree (x + 1);

        return;
    }

    if (node -> lson == NULL) {//若左儿子空就填左二子的坑

        Node *p = node;

        node = new Node; node -> mest();

        node -> fath = p;
        node -> val = st[x];
        p -> lson = node;

        make_tree (x + 1);

        return;
    }

    while (node -> rson != NULL)//否则往上找到一个没有右儿子的点填右儿子的坑
        node = node -> fath;

    Node *p = node;

    node = new Node; node -> mest();

    node -> fath = p;
    node -> val = st[x];
    p -> rson = node;

    make_tree (x + 1);

    return;
}

void mid_traversal () {//中序遍历

    if (tra -> lson != null) {

        tra = tra -> lson;

        mid_traversal ();
    }

    printf ("%c", tra -> val);

    if (tra -> rson != null) {

        tra = tra -> rson;
        mid_traversal ();
    }

    if (tra -> fath == NULL)
        return;

    else tra = tra -> fath;

    return;
}

void back_traversal () {//后序遍历

    if (tra -> lson != null) {

        tra = tra -> lson;

        back_traversal ();
    }

    if (tra -> rson != null) {

        tra = tra -> rson;

        back_traversal ();
    }

    printf ("%c", tra -> val);

    if (tra -> fath == NULL)
        return;

    else tra = tra -> fath;

    return;
}

signed main() {

    cin >> st;

    node = new Node;
    null = new Node;

    node -> mest();
    node -> val = st[0];

    null -> mest();
    null -> val = '.';

    root = node;

    make_tree (1);

    tra = root;

    mid_traversal ();

    putchar ('\n');

    back_traversal ();

    return 0;
}

事实证明，换行删掉后也就只有 90 行qwq

代码不太严谨，劳烦各位提意见♪(･ω･)ﾉ