給定一個先序序列，要根據這個序列建立二叉樹，然后中序輸出，這一題關鍵是遞歸的思想，當然非遞歸也可以，遞歸的話，這一題給我的啟示那就是，可以讓最后遞歸的返回值傳給根，以便于最后的輸出！
#include<iostream>
using namespace std;
//根據先序遍歷遞歸建立二叉樹，然后中序輸出即可
struct Tree
{
Tree *lnode;
Tree *rnode;
char data;
}tree;
Tree *root;
Tree *Root;
char str[103];
int id;
Tree *work()
{
Tree *root;
if(str[id++]=='#') root=NULL;
else
{
root=new Tree;
root->data=str[id-1];
root->lnode=work();
root->rnode=work();
}
return root;
}
void middisp(Tree *p) //遞歸的形式都忘了
{
if(p!=NULL)
{ middisp(p->lnode);
cout<<p->data<<" ";
middisp(p->rnode);
}
}
int main()
{
Tree *Root;
while(cin>>str)
{
id=0;
Root=work();
middisp(Root);
cout<<endl;
}
system("pause");
return 0;
}