【PTA】Tree Traversals Again
题目如下：
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.
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
Figure 1
Input Specification:
Each input file contains one test case. For each case, the first line contains a positive integer N (≤) which is the total number of nodes in a tree (and hence the nodes are numbered from 1 to N). Then 2 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
分析：
题意很简单，给你一个用栈遍历某棵树的顺序。并给出这个树的后序遍历。
不妨看一下例子：Push进栈的有：1 2 3 4 5 6
而对应Pop出栈的是：3 2 4 1 6 5
发现很眼熟，如果对树的遍历很敏感的话。你会发现进栈的顺序是树的先序遍历。而出栈的顺序是中序遍历。
暂且不讨论原因何在，就按这个思路，把树建起来，后序遍历输出即可。
关键是，怎么建树？
我的思路如下：按照题意，建立一个栈，两个数组pre，middle：用来保留先序遍历序列与中序遍历序列。
处理Push和Pop的接受输入。当Push时，把对应数据计入先序遍历序列的对应下标。并把数据压栈。
当Pop是，把栈顶元素计入中序遍历序列的对应下标。并弹栈。
这样输入结束后，我们就有了先序与中序序列。接下来的问题就变为：利用先序序列和中序序列还原二叉树，并后序输出。
教材例题了，方法不多述了。关键步骤在注释中有提到。
代码如下：
#include <bits/stdc++.h> #define MAX 101 typedef struct TNode { int data; struct TNode *left; struct TNode *right; }TNode; int pre[MAX]={0}; int middle[MAX]={0}; int ps,pe,ms,me; int total=0; int count=0; TNode* CreateTree(int ps,int pe,int ms,int me) { int i; if(ps>pe) return NULL; //查找根节点在中序序列中位置 for( i=ms;i<=me;i++) { if(middle[i]==pre[ps]) break; } TNode *r = new TNode; //若第i个位置为根节点，则i-起始位置=左子树个数 int num1=i-ms; r->data=pre[ps]; //左子树对应：先序序列：根节点往后一个~根节点+左子树个数 // 中序序列：起始位置（中序：左根右）~根节点位置（即i） r->left=CreateTree(ps+1,ps+num1,ms,i-1); //右子树对应：先序序列：左子树位置+1~ 列尾 // 中序序列：根节点+1~列尾 r->right=CreateTree(ps+num1+1,pe,i+1,me); return r; } //后序遍历输出 void PostOrder(TNode *r) { if(r==NULL) return; PostOrder(r->left); PostOrder(r->right); printf("%d",r->data); count++; if(count <total) printf(" "); } int main(void) { scanf("%d",&total); std::stack<int> a; int tmp; char tmps[20]; int pn=0; //前序序列下标 int mn=0; //中序序列下标 for(int i=0;i<2*total;i++) { scanf("%s",tmps); if(strcmp(tmps,"Push")==0) { scanf("%d",&tmp); pre[pn]=tmp; pn++; a.push(tmp); } else { middle[mn]=a.top(); mn++; a.pop(); } } TNode* root = CreateTree(0, total-1, 0, total-1); PostOrder(root); return 0; }
