#include#include #include #include #include #include #define max 500using namespace std;typedef struct node{ char data; struct node *left ,*right;}binode,*bitree;//树结构typedef struct{ bitree num[max]; int top;}sqstack;//栈结构typedef struct kk{ bitree t; struct kk *next;}sqqueue;//typedef struct{ sqqueue *front,*rear;}queue;//层次遍历时用到的队列结构typedef struct post_y{ binode *prt; int flag;}post_type;typedef struct LP{ post_type num[max]; int top1;}Sqstack;int initqueue(queue *Q){ sqqueue *p; p=(sqqueue*)malloc(sizeof(sqqueue)); Q->front=p; Q->rear=p; (Q->front)->next=NULL; return 0;}//初始化队列int queueempty(queue *Q){ if(Q->rear==Q->front) { return 1; } else return 0;}//队列的判空运算int queuepush(queue *Q,bitree T){ sqqueue *p; p=(sqqueue*)malloc(sizeof(sqqueue)); p->t=T; p->next=NULL; (Q->rear)->next=p; Q->rear=p; return 0;}//元素入队bitree GET_top(queue *Q){ sqqueue *p; p=(sqqueue*)malloc(sizeof(sqqueue)); bitree q; q=(bitree)malloc(sizeof(bitree)); q->data='1'; q->left=NULL; q->right=NULL; if(queueempty(Q)) { return q; } else { p=(Q->front)->next; return p->t; }}//获取队首元素int queuepop(queue *Q){ if(queueempty(Q)) { return -1; } else { sqqueue *p; p=(Q->front)->next; (Q->front)->next=p->next; if(p->next==NULL) Q->rear=Q->front; free(p); return 0; } }//元素出队void creattree(bitree &T){ char s; scanf("%c",&s); if(s=='#') { T=NULL; } else { T=(bitree)malloc(sizeof(binode)); T->data=s; creattree(T->left); creattree(T->right); }}//建树void visit(bitree T)访问跟操作{ if(T!=NULL) { printf("%c ",T->data); }}void firstvisit(bitree T)//递归实现先序遍历{ if(NULL!=T) { visit(T); firstvisit(T->left); firstvisit(T->right); }}//递归实现先序遍历void midvisit(bitree T)//递归实现中序遍历{ if(T!=NULL) { midvisit(T->left); visit(T); midvisit(T->right); }}//递归实现中序遍历void lastvisit(bitree T)//递归实现后序遍历{ if(T!=NULL) { lastvisit(T->left); lastvisit(T->right); visit(T); }}//递归实现后序遍历void post_visit(bitree T){ Sqstack S; bitree p=NULL; post_type elem; S.top1=-1; p=T; while(NULL!=p||S.top1>-1) { while(NULL!=p) { elem.prt=p; elem.flag=1; S.num[++S.top1]=elem; p=p->left; } elem=S.num[S.top1--]; if(1==elem.flag) { elem.flag=2; S.num[++S.top1]=elem; p=elem.prt->right; } else if(elem.flag==2) { p=elem.prt; printf("%c ",p->data); p=NULL; } }}//非递归实现后序遍历void previsit(bitree T){ binode *p; p=NULL; sqstack S; S.top=-1; if(NULL!=T) { S.num[++S.top]=T; while(S.top>-1) { p=S.num[S.top--]; printf("%c ",p->data); if(NULL!=p->right) { S.num[++S.top]=p->right; } if(NULL!=p->left) { S.num[++S.top]=p->left; } } }}void inorder(bitree T){ sqstack S; S.top=-1; binode *p=T; while(p||S.top>-1) { while(NULL!=p) { S.num[++S.top]=p; p=p->left; } p=S.num[S.top--]; printf("%c ",p->data); p=p->right; } }void levelvisit(bitree T){ queue *Q; bitree p=T; initqueue(Q); queuepush(Q,T); while(!queueempty(Q)) { p=GET_top(Q); queuepop(Q); printf("%c ",p->data); if(p->left!=NULL) queuepush(Q,p->left); if(p->right!=NULL) queuepush(Q,p->right); } }//层次遍历void menu(){ printf("\t\t选择遍历方式\n"); printf("\t\t1:先序遍历\n"); printf("\t\t2:中序遍历\n"); printf("\t\t3:后序遍历\n"); printf("\t\t4:层次遍历\n");}int main(){ int n; printf("\t\t\t手动输入测试数据\n"); printf("输入节点，其中#表示空子树\n"); bitree T; creattree(T); menu(); while(scanf("%d",&n)!=EOF) { switch(n) { case 1: system("cls"); printf("非递归先序遍历得到的序列\n"); previsit(T); printf("\n"); printf("递归先序遍历得到的序列\n"); firstvisit(T) ; printf("\n"); Sleep(10000); system("cls"); menu(); break; case 2: system("cls"); printf("非递归中序遍历得到的结果\n"); inorder(T); printf("\n"); printf("递归中序遍历得到的序列\n"); midvisit(T); printf("\n"); Sleep(100000); system("cls"); menu(); break; case 3: system("cls"); printf("递归后序遍历得到的序列\n"); lastvisit(T); printf("\n"); printf("非递归后序遍历的到的序列\n"); post_visit(T); printf("\n"); Sleep(10000); system("cls"); menu(); break; case 4: system("cls"); printf("层次遍历得到的序列\n"); levelvisit(T); printf("\n"); Sleep(10000); system("cls"); menu(); break; } } return 0; }本次测试使用的数据ABC##DE#G##F###树的形态根据先序遍历和中序遍历的结果得到后序遍历结果== 我们知道先序遍历的序列是根+左子树的先序遍历的结果+右子树先序遍历的结果，而中序遍历的结果=左子树的中序遍历结果+根+右子树的中序遍历结果。这样我们就可以根据先序遍历和中序遍历的结果还原这颗二叉树 例如一个二叉树的的先序遍历是ABDECF 后序遍历的结果是DBEAFC 根据遍历的特点我们可知A是整课二叉树的根，那么DBE则是左子树，FC是右子树，然后根据子树的先序遍历和中序遍历的长度相同，左子树的先BDE，左子树的中是DBE，我们又可知B是子树的根....一直这样分下去，直至只有一个节点。。。
#include#include #include #include using namespace std;void previs(char *pre , char *in,int len){ if(len<1) return; int i=0; while(in[i]!=pre[0]) i++; previs(pre+1,in,i);//递归求解左子树 previs(pre+1+i,in+1+i,len-i-1);//递归求解右子树 cout<<*(pre);} int main(){ string s,ch; cin>>s>>ch; int len=s.size(); previs(s.c_str(),ch.c_str(),len); printf("\n"); return 0;}
版权声明：本文为博主原创文章，未经博主允许不得转载。