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

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

输入

第一行为中序序列  
第二行为后续序列

输出

输出为遍历二叉树得到的先序序列

样例输入

BFDAEGC
FDBGECA

样例输出

ABDFCEG 

 

 

  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 displayhou(tree *&L)
163 {
164     if(L!=NULL)
165     {
166         displayhou(L->lchild);
167         displayhou(L->rchild);
168         cout<<L->date;
169     }
170 }
171 
172 void displaypre(tree *&L)
173 {
174     if(L!=NULL)
175     {
176         cout<<L->date;
177         displaypre(L->lchild);
178         displaypre(L->rchild);
179     }
180 }
181 
182 void creatinpre(tree *&L ,char *in,char *pre,int x)
183 {
184     int k=0;
185     char *p;
186     if(x<=0)
187     {
188         L=NULL;
189         return ;
190     }
191     L=(tree *)malloc(sizeof(tree));
192     L->date = *pre;
193     for(p=in ; p<in+x; p++)
194     {
195         if(*p==*pre)
196             break;
197     }
198     k=p-in;
199     creatinpre(L->lchild,in,pre+1,k);
200     creatinpre(L->rchild,p+1,pre+k+1,x-k-1);
201 }
202 
203 void creatinhou(tree *&L ,char *in,char *pre,int x)
204 {
205     int k=0;
206     char *p;
207     if(x<=0)
208     {
209         L=NULL;
210         return ;
211     }
212     L=(tree *)malloc(sizeof(tree));
213     L->date = *pre;
214     for(p=in ; p>in-x; p--)
215     {
216         if(*p==*pre)
217             break;
218     }
219     k=in-p;
220     creatinhou(L->rchild,in,pre-1,k);
221     creatinhou(L->lchild,p-1,pre-k-1,x-k-1);
222 }
223 
224 int main()
225 {
226     tree *L = NULL;
227     x=0;
228     char in[100],hou[100];
229     cin>>in;
230     cin>>hou;
231     x=strlen(in);
232     creatinhou(L,in+x-1,hou+x-1,x);
233     displaypre(L);
234     destroytree(L);
235     return 0;
236 }