7-2 前序序列创建二叉树 (25 分)
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以二叉链表存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，代表一棵空树。然后再对二叉树进行中序遍历，输出遍历结果。

输入格式:
多组测试数据，每组测试数据一行，该行只有一个字符串，长度不超过100。

输出格式:
对于每组数据，

输出二叉树的中序遍历的序列，每个字符后面都有一个空格。

每组输出一行，对应输入的一行字符串。

输入样例:（及其对应的二叉树）

abc##de#g##f###
结尾无空行
输出样例:
c b e g d f a
结尾无空行

C++：

using namespace std;
#include <algorithm>
#include<cstring>
#include <iostream>
#include<string>
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<string.h>
#include<iomanip>
#include<sstream>
#include<vector>struct TreeNode {char val;TreeNode* left;TreeNode* right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}TreeNode(char x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};TreeNode *build(const string &s,int& i)
{if (i >= s.size()||s[i]=='#')return NULL;TreeNode* root = new TreeNode(s[i]);root->left = build(s, ++i);root->right = build(s, ++i);return root;
}
vector<char>t;
void travel(TreeNode* root)
{if (root){travel(root->left);t.push_back(root->val);travel(root->right);}
}int main()
{string s; cin >> s;int i = 0;TreeNode* root = build(s, i);travel(root);for (int i = 0; i < t.size(); i++){cout << t[i] << " ";}
}