利用二叉树中序及先序遍历确定该二叉树的后序序列

1000(ms) 10000(kb) 2754 / 5599 已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历，但已知先序和后序，却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果，要求输出其后序遍历结果。

输入

输入数据占2行，其中第一行表示中序遍历结果，第二行为先序遍历结果。

输出

对测试数据，输出后序遍历结果。

样例输入

BFDAEGC
ABDFCEG

样例输出

FDBGECA 

 

  1 #include<iostream>
  2 #include<algorithm>
  3 #include<cstring>
  4 #include<cstdlib>
  5 #include<cstdio>
  6 typedef char Datetype;
  7 using namespace std;
  8 int x;
  9 
 10 typedef struct link{
 11     Datetype date;
 12     struct link *lchild;
 13     struct link *rchild;
 14 }tree;
 15 
 16 typedef struct queue{
 17     tree *data;
 18     struct queue *next;
 19 }que;
 20 
 21 typedef struct {
 22     que *front;
 23     que *rear;
 24 }lin;
 25 
 26 void Initqueue(lin *&L)
 27 {
 28     L=(lin *)malloc(sizeof(lin));
 29     L->front=L->rear=NULL;
 30 }
 31 
 32 void destroyed(lin *&L)
 33 {
 34     que *p=NULL,*r=NULL;
 35     p=L->front;
 36     while(p!=NULL)
 37     {
 38         r=p;
 39         p=p->next;
 40         free(r);
 41     }
 42     free(L);
 43 }
 44 
 45 bool pop(lin *&L, tree *&e)
 46 {
 47     que *p;
 48     if(L->rear==NULL)
 49         return false;
 50     p=L->front;
 51     if(L->rear==L->front)
 52         L->front=L->rear=NULL;
 53     else
 54         L->front=p->next;
 55     e=p->data;
 56     free(p);
 57     return true;
 58 }
 59 
 60 int empty(lin *&L)
 61 {
 62     return (L->rear==NULL);
 63 }
 64 
 65 void push(lin *&L,tree *e)
 66 {
 67     que *p;
 68     p = (que *)malloc(sizeof(que));
 69     p->data=e;
 70     p->next=NULL;
 71     if(L->rear==NULL)
 72     {
 73         L->front=p;
 74         L->rear=p;
 75     }
 76     else
 77     {
 78         L->rear->next=p;
 79         L->rear=p;
 80     }
 81 }
 82 
 83 void creattree(tree *&L)
 84 {
 85     char c;
 86     cin>>c;
 87     if(c=='#')
 88         L=NULL;
 89     else
 90     {
 91         L = (tree *)malloc(sizeof(tree)) ;
 92         L->date=c;
 93         creattree(L->lchild);
 94         creattree(L->rchild);
 95     }
 96 }
 97 
 98 void find(tree *L)
 99 {
100     if(L!=NULL)
101     {
102         x++;
103         find(L->rchild);
104     }
105 }
106 
107 void destroytree(tree *&L)
108 {
109     if(L!=NULL)
110     {
111         destroytree(L->lchild);
112         destroytree(L->rchild);
113         free(L);
114     }
115 }
116 
117 int deep(tree *L)
118 {
119     int ldep,rdep,max;
120     if(L!=NULL)
121     {
122         ldep=deep(L->lchild);
123         rdep=deep(L->rchild);
124         max=ldep>rdep?ldep+1:rdep+1;
125         return max;
126     }
127     else
128         return 0;
129 }
130 
131 void finddegree(tree *&L, int n)
132 {
133     if(L!=NULL)
134     {
135         if(x<n)
136             x=n;
137         finddegree(L->lchild,n);
138         finddegree(L->rchild,n+1);
139     }
140 
141 }
142 
143 void run(tree *L)
144 {
145     tree *p=L;
146     lin *qu;
147     Initqueue(qu);
148     if(L!=NULL)
149         push(qu,p);
150     while(!empty(qu))
151     {
152         pop(qu,p);
153         cout<<p->date;
154         if(p->lchild!=NULL)
155             push(qu,p->lchild);
156         if(p->rchild!=NULL)
157             push(qu,p->rchild);
158     }
159     destroyed(qu);
160 }
161 
162 void display(tree *&L)
163 {
164     if(L!=NULL)
165     {
166         display(L->lchild);
167         display(L->rchild);
168         cout<<L->date;
169     }
170 }
171 
172 void creat(tree *&L ,char *in,char *pre,int x)
173 {
174     int k=0;
175     char *p;
176     if(x<=0)
177     {
178         L=NULL;
179         return ;
180     }
181     L=(tree *)malloc(sizeof(tree));
182     L->date = *pre;
183     for(p=in ; p<in+x; p++)
184     {
185         if(*p==*pre)
186             break;
187     }
188     k=p-in;
189     creat(L->lchild,in,pre+1,k);
190     creat(L->rchild,p+1,pre+k+1,x-k-1);
191 }
192 
193 int main()
194 {
195     tree *L = NULL;
196     x=0;
197     char in[100],pre[100];
198     cin>>in;
199     cin>>pre;
200     x=strlen(in);
201     creat(L,in,pre,x);
202     display(L);
203     destroytree(L);
204     return 0;
205 }