【題目來源】
https://www.acwing.com/problem/content/3387/

【題目描述】
編寫一個程序，讀入用戶輸入的一串先序遍歷字符串，根據此字符串建立一個二叉樹（以指針方式存儲）。
例如如下的先序遍歷字符串：abc##de#g##f###，其中 # 表示的是空格，空格字符代表空樹。
建立起此二叉樹以后，再對二叉樹進行中序遍歷，輸出遍歷結果。

【輸入格式】
共一行，包含一個字符串，表示先序遍歷字符串。

【輸出格式】
共一行，輸出將輸入字符串建立二叉樹后中序遍歷的序列，字符之間用空格隔開。
注意，輸出中不用包含 #。

【數據范圍】
輸入字符串長度不超過 100，且只包含小寫字母和 #。

【輸入樣例】
abc##de#g##f###

【輸出樣例】
c b e g d f a

【算法分析】
本題是按輸入的先序遍歷序列建樹，然后輸出對應的中序遍歷序列。
若調整如下“大犇代碼”中的如下三句代碼的順序，便可輸出對應的先序遍歷序列、中序遍歷序列、后序遍歷序列。

//PreOrder
cout<<ch<<" ";
dfs();
dfs();//InOrder
dfs();
cout<<ch<<" ";
dfs();//PostOrder
dfs();
dfs();
cout<<ch<<" ";

【大犇代碼】

#include <bits/stdc++.h>
using namespace std;void dfs(){char ch=getchar();if(ch=='#') return;dfs();cout<<ch<<" ";dfs();
}int main() {dfs();return 0;
}/*
in:
abc##de#g##f###out:
c b e g d f a
*/

【傳統代碼】

#include <bits/stdc++.h>
using namespace std;struct BiTNode {char data;BiTNode *lchild,*rchild;
};
typedef struct BiTNode *BiTree;void CreateBiTree(BiTree &T) {//按先序遍歷的順序建立二叉鏈表char ch;cin>>ch;if(ch=='#') T=NULL;else {T=new BiTNode;T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}
}void InOrderTraverse(BiTree T) {//中序遍歷if(T) {InOrderTraverse(T->lchild);cout<<T->data<<" ";InOrderTraverse(T->rchild);}
}int main() {BiTree tree;CreateBiTree(tree);InOrderTraverse(tree);cout<<endl;return 0;
}/*
in:
ABD#G###CE##F##out:
D G B A E C F
*/

【參考文獻】
https://blog.csdn.net/hnjzsyjyj/article/details/127290036
https://www.acwing.com/solution/content/183211/
https://www.acwing.com/solution/content/64837/


?