已知先序和中序 求后序
可以有两种方式输出
一种是建好树按照树输出
一种是不建树 在遍历的过程中存入 vector 再倒叙输出
- #include<bits/stdc++.h>
- using namespace std;
- int ri[1000];int le[1000];
- char xian[30],zhong[30];vector<char>ans;
- int built(int x1,int y1,int x2,int y2)
- {
- if(x2>y2||x1>y1)return 0;
- char root=xian[x1];
- ans.push_back(root);
- int p=x2;
- while(zhong[p]!=root)p++;
- int cnt=p-x2;
- ri[root]=built(x1+cnt+1,y1,x2+cnt+1,y2);
- le[root]=built(x1+1,x1+cnt,x2,x2+cnt-1);
- return root;
- }
- void dfs(int root)
- {
- if(le[root]){dfs(le[root]);}
- if(ri[root]){dfs(ri[root]);}
- printf("%c",root);
- return;
- }
- int main()
- {
- while(scanf("%s %s",xian+1,zhong+1)==2)
- { ans.clear();
- int n=strlen(xian+1);
- int root=built(1,n,1,n);
- //for(int i=ans.size()-1;i>=0;i--)
- // cout<<ans[i];
- dfs(root);
- cout<<endl;
- }
- return 0;
- }
- View Code
来源: http://www.bubuko.com/infodetail-2933049.html