洛谷【p1305】新二叉树（c++）

https://www.luogu.com.cn/problem/P1305

题目描述
输入一串二叉树，输出其前序遍历。

输入格式
第一行为二叉树的节点数 n。(1≤n≤26)
后面 n 行，每一个字母为节点，后两个字母分别为其左右儿子。
空节点用 * 表示

输出格式
二叉树的前序遍历。

输入输出样例
输入 #1

6
abc
bdi
cj*
d**
i**
j**

输出 #1

abdicj

解释：
这题一开始我是想建立一棵树的 然后在利用前序遍历，但是我太辣鸡 了，实在想不到其他的方法了，没办法，就只能用 这个了 就根据题目的意思 建立一课树。

• 先单独输入第一行，本来可以放在循环里的，但是要传入一个头节点， 就得先输入
• 先输入一个头节点，然后就连接它的左孩子和右孩子
• 然后在从2循环到n， 输入下个节点和左孩子和右孩子
• 最后就把头节点传过去，进行前序遍历， 边界条件就是碰到 ’ * ‘ 就退出

下面附上我的代码：

// 其实我是真的不想用结构体的， 不过没办法， 唉

#include
using namespace std;
char h, h1;
struct treeNode {
    char left;
    char right;
}tree[30];

void pre(char x) {  // 前序遍历
    if (x == '*')
        return ;
    cout << x;
    pre(tree[x].left);
    pre(tree[x].right);
}

int main()
{
    int n;
    cin >> n;
    cin >> h;  // 本来 这个也可以写在下面的循环里的， 但是要保存第一个节点就不能写在下面的循环里了
    cin >> tree[h].left;
    cin >> tree[h].right;
    for (int i = 2; i <= n; i ++) {  // 建立二叉树
        cin >> h1;
        cin >> tree[h1].left;
        cin >> tree[h1].right;
    }
    pre(h);
    return 0;
}

哈哈哈 其实是骗你们的啦 我还有一种方法哦， 不过这个也是看了其他大佬的思路才想到的
这个就不详细写过程了， 你们自己看看吧， 应该是可以看懂的 思想不难

#include
#include
using namespace std;
string s, ss;
int n;
int main()
{
    cin >> n;
    cin >> s;
    for (int i = 2; i <= n; i ++) {
        cin >> ss;
        int idx = s.find(ss[0]);  // 找出 这个节点在原节点的哪个地方
        s.erase(idx, 1);  // 只能到1, 因为到2的话就是 右孩子了 
        s.insert(idx, ss);  // 在原来的那个地方插入 这个新输入的一些节点
    }
    for (int i = 0; i < s.size(); i ++)
        if (s[i] != '*')
            cout << s[i];
    return 0;
}

以上仅供参考（防抄袭哦 ）嘻嘻來