描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述：
输入包括1行字符串，长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。
示例1
输入：abc##de#g##f###输出：c b e g d f a 思路一：
运用一个重要的结论：二叉树的先序遍历入栈，那么出栈顺序就是他的中序遍历
#include <iostream>
#include <string>
#include <stack>
using namespace std;
//这个实际上就是树的遍历的非递归实现，入栈时访问 = 前序， 出栈时访问 = 中序
int main()
{
string tmp;
cin >> tmp;
stack<char> st;
for(auto c : tmp)
{
if(c != '#')
{
st.push(c);
}
else
{
if(!st.empty())
{
cout << st.top() << " ";
st.pop();
}
}
}
return 0;
}思路二：
与思路一不同，我们这次要先创建一棵二叉树出来！
通过前序遍历我们是可以创建一棵二叉树的，然后通过中序遍历打印出来！（比较复杂）
#include <iostream>
#include <string>
using namespace std;
struct TreeNode //需要自己声明结构体
{
TreeNode* left;
TreeNode* right;
char val;
};
//这里的i要传引用接收，每次改变才会影响到下一次的接收
TreeNode* Create(string tmp, int& i)
{
//如果为#说明是空的，则让i++然后直接返回空即可
if(tmp[i] == '#')
{
i++;
return nullptr;
}
//走到这里这个时候说明不为空，则为该节点开辟空间，然后把tmp的i位置处的值放进去，记得i++
TreeNode* root = new TreeNode;
root->val = tmp[i++];
//然后继续递归到左右子树完成构建
root->left = Create(tmp, i);
root->right = Create(tmp, i);
return root;
}
//中序遍历函数
void inorder(TreeNode* root)
{
if(root == nullptr)
return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
int main()
{
string tmp;
cin >> tmp;
// i用于指定tmp位置到达的下标
int i = 0;
TreeNode* root = Create(tmp, i);
inorder(root);
return 0;
}