1 //递归实现 2 #include<iostream> 3 #include<string> 4 using namespace std; 5  6 typedef struct BiTNode{ 7     char data; 8     struct BiTNode *lchild,*rchild; 9 }BiTNode,*BiTree;10 11 void InitBiTree(BiTree &T)//构造空二叉树12 {13     T=NULL;14 }15 void CreateBiTree(BiTree &T)//生成二叉树16 {17     char ch;18     cin>>ch;19     if(ch==‘0‘)//0代表空20         T=NULL;21     else22     {23         T=(BiTree)malloc(sizeof(BiTNode));//生成根结点24         if(!T)25         {26             cout<<"生成结点错误！"<<endl;27             return;28         }29         T->data=http://www.mamicode.com/ch;30         CreateBiTree(T->lchild);31         CreateBiTree(T->rchild);32     }33 }34 35 void PreOrder(BiTree T)//先序递归遍历36 {37     if(T!=NULL)38     {39         cout<<T->data<<" ";40         PreOrder(T->lchild);41         PreOrder(T->rchild);42     }43 }44 45 void InOrder(BiTree T)//中序递归遍历46 {47     if(T!=NULL)48     {49         InOrder(T->lchild);50         cout<<T->data<<" ";51         InOrder(T->rchild);52     }53 }54 55 void PostOrder(BiTree T)//后序递归遍历56 {57     if(T!=NULL)58     {59         PostOrder(T->lchild);60         PostOrder(T->rchild);61         cout<<T->data<<" ";62     }63 }64 int main()65 {66     BiTree T;67     InitBiTree(T);68     cout<<"请输入二叉树结点"<<endl;69     CreateBiTree(T);70     string str="";71     cout<<"请输入遍历要求（先序,中序,后序）";72     cin>>str;73     if(str=="先序")74     {75         cout<<endl<<"先序递归遍历树"<<endl;76         PreOrder(T);77     }78     else if(str=="中序")79     {80         cout<<endl<<"中序递归遍历树"<<endl;81         InOrder(T);82     }83     else if(str=="后序")84     {85         cout<<endl<<"后序递归遍历树"<<endl;86         PostOrder(T);87     }88     cout<<endl;89     system("pause");90     return 0;91 }