数据结构实验之二叉树二：遍历二叉树
Time Limit:1000MSMemory Limit:65536KProblem Description
已知二叉树的一个按先序遍历输入的字符序列，如abc,,de,g,,f,,,(其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。
Input
连续输入多组数据，每组数据输入一个长度小于50个字符的字符串。
Output
每组输入数据对应输出2行：
第1行输出中序遍历序列；
第2行输出后序遍历序列。
Example Input
abc,,de,g,,f,,,
Example Output
cbegdfacgefdba
Hint
非递归：#include <iostream>#include <stdio.h>#include <stack>#include <malloc.h>using namespace std;typedef struct btree{char date;struct btree *lchild,*rchild;}btree;char ch[51];int i;void createbtree(btree *&b)//引用{char c;c=ch[i++];if(c==',')b=NULL;else{b=(btree *)malloc(sizeof(btree));b->date=c;createbtree(b->lchild);createbtree(b->rchild);}}void inorder(btree *&b){btree *p=b;stack<btree*> Stack;while(p!=NULL||!Stack.empty()){while(p!=NULL){Stack.push(p);p=p->lchild;}if(!Stack.empty()){p=Stack.top();cout<<p->date;Stack.pop();//没有返回值不能写成p=Stack.pop();p=p->rchild;}}cout<<endl;}void postorder(btree *b){btree *p=b;stack<btree*>Stack;do{while(p!=NULL){Stack.push(p);p=p->lchild;}bool flag=true;btree *r=NULL;while(!Stack.empty()&&flag){p=Stack.top();if(p->rchild==r){cout<<p->date;Stack.pop();r=p;}else{flag=false;p=p->rchild;}}}while(!Stack.empty());cout<<endl;}int main(){while(cin>>ch){i=0;btree *root;root=(btree *)malloc(sizeof(btree));createbtree(root);inorder(root);postorder(root);}return 0;}
递归：
#include <iostream>#include <stdio.h>#include <stack>#include <malloc.h>using namespace std;typedef struct btree{char date;struct btree *lchild,*rchild;}btree;char ch[51];int i;void createbtree(btree *&b){char c;c=ch[i++];if(c==',')b=NULL;else{b=(btree *)malloc(sizeof(btree));b->date=c;createbtree(b->lchild);createbtree(b->rchild);}}void inorder(btree *&b){ if(b!=NULL){inorder(b->lchild);cout<<b->date;inorder(b->rchild);}}void postorder(btree *b){if(b!=NULL){postorder(b->lchild);postorder(b->rchild);cout<<b->date;}}int main(){while(cin>>ch){i=0;btree *root;root=(btree *)malloc(sizeof(btree));createbtree(root);inorder(root);cout<<endl;postorder(root);cout<<endl;}return 0;}/***************************************************User name: YT1658506207邵雪源Result: AcceptedTake time: 0msTake Memory: 204KBSubmit time: -11-02 15:21:31****************************************************/
