Tree Traversals Again

第一次用了建树的方法，比较繁琐，《数据结构》课程中又介绍了不用建树的思路，根据先序和中序直接得到后序遍历的结果，代码如下：

 1 void solve( int preL, int inL, int postL, int n)    //当前处理树的三种遍历的第一个元素和树的规模
 2 {
 3     if(n==0)   return;                                 //边界条件
 4     if(n==1) {
 5         post[postL] = pre[preL];
 6         return;
 7     }    
 8     root = pre[preL];                                 //当前树的根为先序的第一个元素
 9     post[postL+n-1] = root;                    //将根节点的值填到后序遍历的数组中的最后一个
10     for(i = 0; i < n; i++)                    
11         if( in[inL+i] ==root)  break;           //找到根节点在中序遍历中的位置
12     L = i; R = n - L - 1;                               //计算左子树的规模和右子树的规模
13     solve(preL+1,inL,postL,L);                  //递归
14     solve(preL+L+1,intL+L+1,postL+L,R);    
15 }

=========================================== 我是分割线 ===========================================================

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

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

AC代码

 1 #include<stdio.h>
 2 #include<stdlib.h>
 3 #include<string.h>
 4 
 5 typedef struct BTNode{
 6 
 7   int Data;
 8   struct BTNode *Right;
 9   struct BTNode *Left;
10 
11 }*BT;
12 void InputData(int preorder[],int inorder[]);
13 BT CreatBinaryTree(int preorder[],int inorder[],int N,int *pre_index);
14 void PostTravelofBT(BT T,int *k);
15 int main(){
16 
17   int N;
18   BT T;
19   int k = 1;
20   int pre_index = 0;
21   scanf("%d
",&N);
22   int preorder[N],inorder[N];
23   InputData(preorder,inorder);
24   T = CreatBinaryTree(preorder,inorder,N,&pre_index);
25   PostTravelofBT(T,&k);
26 
27   return 0;
28 }
29 
30 void InputData(int preorder[],int inorder[]){
31   int temp[30];
32   int top = -1;
33   char inputstring[20];
34   int indexforpre = 0;
35   int indexforin = 0;
36   while(gets(inputstring)){
37     if(strcmp(inputstring,"Pop")==0){
38       inorder[indexforin] = temp[top];
39       indexforin ++;
40       top --;
41     }else{
42       int data_tem;
43       sscanf(inputstring,"%*c%*c%*c%*c %d",&data_tem);
44       preorder[indexforpre] = data_tem;
45       indexforpre++;
46       top++;
47       temp[top] = data_tem;
48     }
49 
50   }
51 }
52 
53 BT CreatBinaryTree(int preorder[],int inorder[],int N,int *Ppre_index){
54   BT T;
55   int i;
56   T = (BT)malloc(sizeof(struct BTNode));
57   T->Data = preorder[*Ppre_index];
58   (*Ppre_index)++;
59   T->Left = NULL;
60   T->Right = NULL;
61   for( i = 0; i <N; i++){
62     if(inorder[i]== T->Data){
63       inorder[i] = -1;
64       if(i!=0&&inorder[i-1]!=-1){
65         T->Left = CreatBinaryTree(preorder,inorder,N,Ppre_index);
66       }
67       if(i!=N-1&&inorder[i+1]!=-1){
68         T->Right = CreatBinaryTree(preorder,inorder,N,Ppre_index);
69       }
70     }
71   }
72 
73   return T;
74 }
75 
76 
77 void PostTravelofBT(BT T,int *k){
78   if(T){
79     PostTravelofBT(T->Left,k);
80     PostTravelofBT(T->Right,k);
81       if(*k ==1){
82         printf("%d",T->Data);
83         *k = 0;
84       }else{
85         printf(" %d",T->Data);
86       }
87   }
88   return ;
89 }