03-树3 Tree Traversals Again

　　这道题我的思路是先根据输入得到先序和中序遍历的序列，最后用递归方式构造好树并进行遍历输出。事实上仅该题要求而言无需构造出二叉树再对树本身进行遍历，只需要知道先序和中序的序列，根据关系递归找出后序序列即可，网上方法也多是这种。而我当时一心想着就要用已知的两个序列把这颗树完全构建出来，才有了如下方法：

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <string.h>
  4 #define MaxSize 30
  5 #define STR_LEN 5
  6 
  7 typedef struct TreeNode *BinTree;
  8 struct TreeNode{
  9     int Data;
 10     BinTree Left;
 11     BinTree Right;
 12 };
 13 
 14 typedef struct SNode *Stack;
 15 struct SNode{
 16     int Data[MaxSize];
 17     int Top;
 18     int Cap;  //capability
 19 };
 20 
 21 int InOrder[MaxSize], PreOrder[MaxSize];
 22 
 23 void Push(int data, Stack PtrS)
 24 {
 25     if(PtrS->Top == PtrS->Cap - 1)
 26         return;
 27     else{
 28         PtrS->Data[++(PtrS->Top)] = data;
 29         return;
 30     }
 31 }
 32 
 33 int Pop(Stack PtrS)
 34 {
 35     if(PtrS->Top == -1)
 36         return -1;
 37     else
 38         return PtrS->Data[(PtrS->Top)--];
 39 }
 40 
 41 void GetTwoOrders(int N)
 42 {
 43     char oper[STR_LEN];
 44     Stack S;
 45     S = (Stack)malloc(sizeof(struct SNode));
 46     S->Top = -1;
 47     S->Cap = MaxSize;
 48     int i, data, j = 0, k = 0;
 49     for(i = 0; i < 2 * N; i++){
 50         scanf("%s", &oper);
 51         if(strcmp(oper, "Push") == 0){
 52             scanf("%d", &data);
 53             PreOrder[k++] = data;
 54             Push(data, S);
 55         }
 56         else{
 57             InOrder[j] = Pop(S);
 58             j++;
 59         }
 60     }
 61     return;
 62 }
 63 
 64 BinTree BuildTree(int *PreOrder, int pl, int pr,
 65                  int *InOrder, int il, int ir)
 66 {
 67     int j, k, nN;
 68     BinTree Root;
 69     Root = (BinTree)malloc(sizeof(struct TreeNode));
 70 //每一层新传进来，都让两个order从0到N，这样就得用两个新的order
 71     nN = ir - il;
 72     int newPreOrder[MaxSize], newInOrder[MaxSize];
 73     for(j = 0; j < nN; j++)
 74         newPreOrder[j] = PreOrder[j + pl];
 75     for(j = 0; j < nN; j++)
 76         newInOrder[j] = InOrder[j + il];
 77     int RootIndex;
 78     for(k = 0; k < nN; k++){
 79         if(newInOrder[k] == newPreOrder[0]){
 80             RootIndex = k;
 81             break;
 82         }
 83     }
 84     Root->Data = newPreOrder[0];
 85     if(nN == 1){
 86         Root->Left = NULL;
 87         Root->Right = NULL;
 88     }else if(nN == 0){
 89         return NULL;
 90     }else{
 91         int lpl, lpr, rpl, rpr, lil, lir, ril, rir;
 92     //means (left or right)side (pre or in)order (left or right)limit Index
 93         lil = 0;
 94         lir = RootIndex;
 95         lpl = 1;
 96         lpr = lpl + (lir - lil);
 97         ril = RootIndex + 1;
 98         rir = nN;
 99         rpl = ril;
100         rpr = nN;
101         Root->Left = BuildTree(newPreOrder, lpl, lpr, newInOrder, lil, lir);
102         Root->Right = BuildTree(newPreOrder, rpl, rpr, newInOrder, ril, rir);
103     }
104     return Root;
105 }
106 
107 int count = 1;
108 
109 int PostOrderTraversal(BinTree BT, int count)
110 {
111     if(BT){
112         count = PostOrderTraversal(BT->Left, count);
113         count = PostOrderTraversal(BT->Right, count);
114         if(count == 1){
115             printf("%d", BT->Data);
116             count++;
117         }
118         else
119             printf(" %d", BT->Data);
120     }
121     return count;
122 }
123 
124 int main(int argc, char const *argv[])
125 {
126     int N, i;
127     BinTree T;
128     T = (BinTree)malloc(sizeof(struct TreeNode));
129     scanf("%d
", &N);
130     int pl, pr, il, ir;
131     GetTwoOrders(N);
132     pl = 0;
133     pr = N;
134     il = 0;
135     ir = N;
136     T = BuildTree(PreOrder, pl, pr, InOrder, il, ir);
137     count = PostOrderTraversal(T, count);
138     printf("
");
139     return 0;
140 }

　　构造树的主要思想是，对传入的已知PreOrder与InOrder序列找到根节点后进行左右子树拆分、链接两边后再递归此过程（101 - 102行），直到链接至叶节点。其中如何正确操作每次传入的两个序列是重点，考虑到树高度较大时找出某一具体子树的元素在序列中的位置情况复杂，我将每次传入的两个序列重新赋值到新的序列上（newPreOrder与newInOrder，70 - 76行），这样之后都可以对新的、只有单一情况（同最原始情况）的序列进行操作，过程更为清晰。

　　另外需要注意对题意的理解，PreOrder的确认并不应该直接顺序赋值，应和InOrder一样借助堆栈进行操作。