首页 > 代码库 > 03-3. Tree Traversals Again (25)
03-3. Tree Traversals Again (25)
03-3. Tree Traversals Again (25)
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:6Push 1Push 2Push 3PopPopPush 4PopPopPush 5Push 6PopPopSample Output:
3 4 2 6 5 1
#include <stdio.h>#define MaxSize 35#define EMPTY_TOS (-1)#define PUSH 1#define POP 2typedef struct stack_record{ int top_of_stack; int stack_array[MaxSize];} Stack;void init_stack(Stack *S){ S->top_of_stack=EMPTY_TOS;}intis_empty(Stack *S){ return (S->top_of_stack==EMPTY_TOS);}intis_full(Stack *S){ return (S->top_of_stack==MaxSize-1); }voidpush(int x,Stack *S){ if(is_full(S)) return; else S->stack_array[++S->top_of_stack]=x;}inttop(Stack *S){ if(!is_empty(S)) return S->stack_array[S->top_of_stack];}intpop(Stack *S){ if(is_empty(S)) return; else return S->stack_array[S->top_of_stack--]; }intmain (){ Stack S1,S2; int OpArray[2*MaxSize+1][2]={-1}; char tmpstr[30],tmp[30],tmp1[30]; init_stack(&S1); init_stack(&S2); int i,NodeNum,tmppop,tmppop1; int PrintTag=0; scanf("%d",&NodeNum); getchar(); for (i=0;i<2*NodeNum;i++){ gets(tmpstr); if(tmpstr[1]==‘u‘){ sscanf(tmpstr,"%s%s",tmp,tmp1); OpArray[i][0]=PUSH; OpArray[i][1]=atoi(tmp1); }else { OpArray[i][0]=POP; } } for (i=0;i<2*NodeNum;i++){ if(OpArray[i][0]==PUSH) push(OpArray[i][1],&S1); else{ if(OpArray[i+1][0]==PUSH){ if(top(&S1)==-1){ push(OpArray[i+1][1],&S2); }else{ push(-1,&S2); push(pop(&S1),&S2); push(-1,&S1); push(OpArray[i+1][1],&S2); } i++; } else{ tmppop=pop(&S1); if(tmppop==-1){ while((tmppop1=pop(&S2))!=-1) printf(" %d",tmppop1); }else{ if (!PrintTag){ printf("%d",tmppop); PrintTag++; }else printf(" %d",tmppop); } } } } return 0;}
03-3. Tree Traversals Again (25)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。