二叉树遍历应用
读入用户输入的一串字符串，将字符串按照先序遍历建立一个二叉树。 其中“#”表示的是空链，代表空树。再对建立好的二叉树进行中序遍历，输出遍历结果。
输入格式:
输入1行字符串，长度小于等于100。
输出格式:
输出中序遍历的结果，每个字符后面有一个空格。
输入样例:
在这里给出一组输入。例如：
abc##de#g##f###
输出样例:
在这里给出相应的输出。例如：
c b e g d f a
#include<iostream>
#include<cstdio>
using namespace std;
typedef struct node{
char ch;
node* lc,*rc;
}node,*Node;
string s;
Node build(Node p,int& k){
if(s[k]=='#'){
k++;
return NULL;
}
p=new node();
p->ch=s[k++];
p->lc=build(p->lc,k);
p->rc=build(p->rc,k);
return p;
}
void show(Node p){
if(p==NULL) return;
show(p->lc);
cout<<p->ch<<' ';
show(p->rc);
}
int main(){
cin>>s;
Node p=NULL;
int k=0;
p=build(p,k);
show(p);
return 0;
}