PAT练习题03-树3 Tree Traversals Again

An inorder binary tree traversal can be implemented in a non-recursive way with a stack. For example, suppose that when a 6-node binary tree (with the keys numbered from 1 to 6) is traversed, the stack operations are: push(1); push(2); push(3); pop(); pop(); push(4); pop(); pop(); push(5); push(6); pop(); pop(). Then a unique binary tree (shown in Figure 1) can be generated from this sequence of operations. Your task is to give the postorder traversal sequence of this tree.

Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤30) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2N lines follow, each describes a stack operation in the format: "Push X" where X is the index of the node being pushed onto the stack; or "Pop" meaning to pop one node from the stack.
Output Specification:
For each test case, print the postorder traversal sequence of the corresponding tree in one line. A solution is guaranteed to exist. All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input:

6
Push 1
Push 2
Push 3
Pop
Pop
Push 4
Pop
Pop
Push 5
Push 6
Pop
Pop

Sample Output:

3 4 2 6 5 1

解题：
这道题的关键在于生成一棵树，因为如果有树，后序遍历代码就非常简单了
根据pop出来的元素，我们很容易知道这是中序遍历的结果，那么要生成一棵树，必须知道两个组合
前序+中序或者中序+后序；这样才能确定一棵树。显然这里我们要知道前序遍历。
回头看输入过程，push的过程正好就是前序遍历
于是乎本道题的关键在于根据前序和中序确定树
核心代码

void post_travel(int preL,int inL,int postL,int N){/**preL,inL,postL分别代表着当前数组的最左端**/ /***pre,in,post分别代表着前，中，后序遍历的数组***/ 
    int root,i,Left,Right;
    if(N==0){  /**没有个数的时候直接返回**/ 
        return;
    }
    if(N==1){  /**当递归只剩一个数时，前序遍历的就是中序遍历的结果**/ 
        post[postL]=pre[preL];
        return;
    }
    root=pre[preL]; /**前序遍历的最左端就是每次递归的根节点***/ 
    post[postL+N-1]=root;/**在后序遍历的结果中，根节点是最后访问的***/ 
    for(i=0;i<N;i++){   /**在中序遍历中找到根节点**/ 
        if(root==in[inL+i]){
            break;
        }
    }
    Left=i;
    Right=N-Left-1;
    post_travel(preL+1,inL,postL,Left);  //递归解决左子树 
    post_travel(preL+Left+1,inL+Left+1,postL+Left,Right); //递归解决右子树 

} 

最后其余的只是解决输入问题，构造一个栈的问题，附上完整代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAXSIZE 30

typedef struct SNode* Stack;
struct SNode{
    int top;
    int element[MAXSIZE];
};
Stack init();
void push(Stack s,int data);
int pop(Stack s);
int pre[MAXSIZE],in[MAXSIZE],post[MAXSIZE];
void post_travel(int preL,int inL,int postL,int N);

int main(){
    int N,data;
    int k=0,j=0;
    scanf("%d",&N);
    char c[10];
    Stack s=init();
    for(int i=0;i<2*N;i++){
        scanf("%s",&c);
        getchar();
        if(strcmp(c,"Push")==0){
            scanf("%d",&data);
            push(s,data);
            pre[k++]=data;
        }else{
            in[j++]=pop(s);
        }
    }
    post_travel(0,0,0,N);
    int first=1;
    for(int i=0;i<N;i++){
        if(first){
            printf("%d",post[i]);
            first=0;
        }else{
            printf(" %d",post[i]);
        }
    }

    return 0;    
}



Stack init(){
    Stack s=(Stack)malloc(sizeof(struct SNode));
    s->top=-1;
    return s;
}

//入栈
void push(Stack s,int data){
    if(s->top==MAXSIZE-1){
        return;
    }else{
        s->element[++s->top]=data;
    }
}
int pop(Stack s){
    if(s->top==-1){
        return -1;
    }
    return s->element[s->top--];
}

void post_travel(int preL,int inL,int postL,int N){/**preL,inL,postL分别代表着当前数组的最左端**/ /***pre,in,post分别代表着前，中，后序遍历的数组***/ 
    int root,i,Left,Right;
    if(N==0){  /**没有个数的时候直接返回**/ 
        return;
    }
    if(N==1){  /**当递归只剩一个数时，前序遍历的就是中序遍历的结果**/ 
        post[postL]=pre[preL];
        return;
    }
    root=pre[preL]; /**前序遍历的最左端就是每次递归的根节点***/ 
    post[postL+N-1]=root;/**在后序遍历的结果中，根节点是最后访问的***/ 
    for(i=0;i<N;i++){   /**在中序遍历中找到根节点**/ 
        if(root==in[inL+i]){
            break;
        }
    }
    Left=i;
    Right=N-Left-1;
    post_travel(preL+1,inL,postL,Left);  //递归解决左子树 
    post_travel(preL+Left+1,inL+Left+1,postL+Left,Right); //递归解决右子树 

}