03-树3 Tree Traversals Again (25分)

03-树3 Tree Traversals Again (25分)

思路分析：给出的样例就是说如果按照堆栈操作那么，出来的就是这个二叉树的中序遍历的结果，然后push操作的值就是二叉树前序遍历的结果，所以题目的意思就是，已知一个二叉树的中序遍历和前序遍历求得这个二叉树的后序遍历

每次在前序遍历中寻找根节点，然后从中序遍历中获取左子树和右子树的个数，然后再构造后序遍历数组，后序遍历数组的最后一位是根节点，然后每一次划分子树以后，那么该序列的最后一位也是 该子树的根， 采用递归逐渐将前序和中序遍历的结果划小，注意每一个划小数列的小标

值得注意的是：
C语言没有string类型，所以比较字符串的时候要用到 strcmp()的函数，但是C++有string类，而且string类重载了关系运算符，可以直接进行比较
记得包含堆栈的头文件：

(1). push(x) 将x入栈
(2). top() 获得栈顶元素
(3). pop() 用以弹出栈顶元素
(4). empty() 可以检测stack内是否为空，返回true为空，返回false为非空
(5). size() 返回stack内元素的个数

#include<iostream>#include<stack>#include<string>#define Maxsize 30using namespace std;int preorder[Maxsize], inorder[Maxsize], postorder[Maxsize];void createPostorder (int preN, int inN, int postN, int N){int L,R;if(N == 0) return;if(N == 1){postorder[postN] = preorder[preN];return;}int i =0;int root = preorder[preN];postorder[postN +N-1] = root; //这里很关键，如果知识N-1，那么在中间的右子树的序列将会发生错误for( i = 0; i<N; i++)//找到根在中序中的位置{if(inorder[inN+i]==root) break;}L = i;//左子树结点点数R = N-(i+1);//右子树结点数createPostorder(preN+1,inN,postN,L);//建立左子树createPostorder(preN+L+1,inN+L+1,postN+L,R);//建立右子树}int main(){stack<int> s;int num;cin  >> num;string ch;int i = 0, j = 0,z = 0;for( i=0; i<2*num;i++){cin >>ch;if(ch == \"Push\"){int num1;cin >> num1;preorder[j++] = num1;s.push(num1);}else if(ch == \"Pop\"){inorder[z++] = s.top();s.pop();}}createPostorder(0,0,0,num);for(i = 0;i<num;i++){cout << postorder[i];if(i!=num-1) cout<<\" \";}return 0;}