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
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:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
6 Push 1 Push 2 Push 3 Pop Pop Push 4 Pop Pop Push 5 Push 6 Pop Pop |
Sample Output:
|
1 |
3 4 2 6 5 1 |
模拟一下过程即可
代码如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 |
#include<stdio.h> #include<stdlib.h> typedef struct tree_ { int number; struct tree_ *left; struct tree_ *right; } tree; typedef struct stack_ { int size; int capacity; int top; void **data; } stack; #define is_stack_empty(X) (!((X)->size)) #define ptr_top(X) ((X)->data[(X)->top]) stack *inti_stack(int n) { stack *temp; temp=(stack *)malloc(sizeof(stack)); temp->size=0; temp->capacity=n; temp->top=-1; temp->data=(void **)malloc(n*sizeof(void *)); return temp; } int push(stack *s,void *data) { if(s->size==s->capacity) { return 1; } (s->top)++; (s->size)++; s->data[s->top]=data; return 0; } int pop(stack *s,void **data) { if(s->size==0) { *data=NULL; return 1; } *data=s->data[s->top]; (s->size)--; (s->top)--; return 0; } void post_order(tree *t,int *flag) { if(t==NULL) { return ; } post_order(t->left,flag); post_order(t->right,flag); if(*flag==0) { printf("%d",t->number); *flag=1; } else { printf(" %d",t->number); } } int main() { int n,i,index,parent,last_push,flag=0; tree *t,*temp; stack *s; char buf[7],action[5]; scanf("%d",&n); getchar();//注意回车 s=inti_stack(n); t=(tree *)malloc((n+1)*sizeof(tree)); parent=0;//dummy root last_push=1; for(i=0;i<n*2;i++) { gets(buf); if(buf[1]=='u') { sscanf(buf,"%s%d",action,&index); t[index].number=index; if(last_push) { t[parent].left=t+index; } else { t[parent].right=t+index; } parent=index; push(s,t+index); last_push=1; } else { if(last_push) { t[parent].left=NULL; } else { t[parent].right=NULL; } pop(s,(void **)&temp); parent=temp->number; last_push=0; } } post_order(t[0].left,&flag); } |