给定一个先序序列，要根据这个序列建立二叉树，然后中序输出，这一题关键是递归的思想，当然非递归也可以，递归的话，这一题给我的启示那就是，可以让最后递归的返回值传给根，以便于最后的输出！
#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;
}