03-树2 Tree Traversals Again

这题是第二次做了，两次都不是独立完成，不过我发现我第一次参考的程序，也是参考老师（陈越）的范例做出来的。我对老师给的做了小幅修改，因为我不想有全局变量的的存在，所以我多传了三个参数进去。正序遍历每次都是从1到N吗？看题目我认为应该是，结果我错了，我是对比正确的程序一点点修改才发现的，不容易啊。下面是题目及程序

 1 #include <stdio.h>
 2 #include <stdlib.h>
 3 #include <string.h>
 4 
 5 typedef struct
 6 {
 7     int * a;
 8     int top;
 9 }SeqStack;
10 
11 void push(SeqStack * pS, int X);
12 int pop(SeqStack * pS);
13 void solve(int * pre, int * in, int * post, int preL, int inL, int postL, int n);
14 
15 int main()
16 {
17 //    freopen("in.txt", "r", stdin); // for test
18     int i, N;
19     scanf("%d", &N);
20     
21     SeqStack S;
22     S.a = (int *)malloc(N * sizeof(int));
23     S.top = -1;
24     int pre[N], in[N], post[N];
25     
26     char chars[5];
27     char * str = chars;
28     int X, pre_index, in_index;
29     pre_index = in_index = 0;
30     for(i = 0; i < 2 * N; i++)
31     {
32         scanf("%s", str);
33         if(strcmp(str, "Push") == 0)
34         {
35             scanf("%d", &X);
36             pre[pre_index++] = X;
37             push(&S, X);
38         }
39         else
40             in[in_index++] = pop(&S);
41     }
42     
43     solve(pre, in, post, 0, 0, 0, N);
44     for(i = 0; i < N; i++)
45     {
46         printf("%d", post[i]);
47         if(i < N - 1)
48             printf(" ");
49         else
50             printf("
");
51     }
52 //    fclose(stdin); // for test
53     return 0;
54 }
55 
56 void push(SeqStack * pS, int X)
57 {
58     pS->a[++(pS->top)] = X;
59 }
60 
61 int pop(SeqStack * pS)
62 {
63     return pS->a[pS->top--];
64 }
65 
66 void solve(int * pre, int * in, int * post, int preL, int inL, int postL, int n)
67 {
68     int i, root, L, R;
69     
70     if(n == 0)
71         return;
72     if(n == 1)
73     {
74         post[postL] = pre[preL];
75         return;
76     }
77     root = pre[preL];
78     post[postL + n - 1] = root;
79     for(i = 0; i < n; i++)
80         if(in[inL + i] == root)
81             break;
82     L = i;
83     R = n - L - 1;
84     solve(pre, in, post, preL + 1, inL, postL, L);
85     solve(pre, in, post, preL + L + 1, inL + L + 1, postL + L, R);
86 }

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.

Figure 1

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