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] << " "; }}