- #include <bits/stdc++.h>
- #include <stdio.h>
- #include <stdlib.h>
- #include <queue>
- using namespace std;
- const int maxn = 50;
- struct node{
- int data;
- node* lchild;
- node* rchild;
- };
- int pre[maxn],in[maxn],post[maxn];
- int n;
- node* create(int preL,int preR,int inL,int inR){
- if(preL> preR){
- return NULL;
- }
- node* root = new node;
- int temp = pre[preL];
- root->data = temp;
- int k;
- for(int i = inL;i<=inR;++i){
- if(in[i] == temp){
- k = i;
- }
- }
- int numLeft = k - inL;
- root->lchild = create(preL+1,preL + numLeft,inL,k - 1);
- root->rchild = create(preL + numLeft + 1,preR,k+1,inR);
- return root;
- }
- int num = 0;
- void postOrder(node *root){
- if(root == NULL){
- return;
- }
- postOrder(root->lchild);
- postOrder(root->rchild);
- printf("%d",root->data);
- num++;
- if(num <n){
- printf(" ");
- }
- }
- int main(){
- scanf("%d",&n);
- char str[5];
- stack<int> st;
- int x,preList,inList;
- preList = 0;
- inList = 0;
- for(int i=0;i< 2*n;++i){
- scanf("%s",str);
- if(strcmp(str,"Push")==0){
- scanf("%d",&x);
- st.push(x);
- pre[preList] = x;
- preList++;
- }else{
- x = st.top();
- st.pop();
- in[inList] = x;
- inList++;
- }
- }
- node* root = create(0,n-1,0,n-1);
- postOrder(root);
- system("pause");
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3393611.html