[数据结构与算法]1086 Tree Traversals Again (25 分)

1086 Tree Traversals Again (25 分)

题目大意

用栈的形式给出一棵二叉树的建立的顺序，求这棵二叉树的后序遍历

基本思路

数据结构：
定义数组value，值就是先序序列。（题目并没有说所有结点的值互不相同。因此，可以用这个数组保存真正的先序序列(结点值)，前、中、后序中只保存这个数组的索引）
定义数组pre、in、post存储先序、中序、后序序列，数组中的值只是数组value的索引。
定义一个栈s模拟出结点值出入栈的顺序，栈中的元素也是数组value的索引值
基本思路：
入栈的序列就是先序遍历的序列，出栈的序列就是中序遍历的序列，因此在读入数据的同时，给数组pre、in、value赋值。
通过先序和中序序列求出后序序列。
输出。

代码

具体数据结构和详细思路请看代码注释：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <cstring>
using namespace std;
vector<int> pre,in,post;//存储先序、中序、后序序列。值只是数组value的索引，要想获得真正的结点值还要进行转化
vector<int> value;//值为真正的结点值（其实它才是真正的先序序列）
//通过先序和中序序列求出后序序列的函数
void postorder(int pre_l,int in_l,int in_r){//形参分别为当前先序序列的左边界（当前根结点在先序序列中的下标），当前中序序列的左、右边界
    //递归边界
    if(in_l>in_r) return;
    //找到当前二叉树的根结点在中序序列中的下标
    int pos;//当前二叉树的根结点在中序序列中的下标
    for(int i=0;i<in.size();i++){
        if(pre[pre_l]==in[i]){
            pos=i;
            break;
        }
    }
    //对当前树的左右子树进行dfs
    postorder(pre_l+1,in_l,pos-1);
    postorder(pre_l+1+pos-in_l,pos+1,in_r);
    //把结点in[pos]加入后序序列
    post.push_back(in[pos]);
}
int main(){
    int n;//结点数量
    cin>>n;
    //用栈s模拟出入栈的过程，可以同时给数组pre、in、value赋值
    //入栈的序列就是先序遍历的序列，出栈的序列就是中序遍历的序列
    stack<int> s;//用来模拟先序遍历出入栈过程，栈中存放的都是数组value的索引
    int index=0;//数组value的索引。初始化为0
    char str[5];
    while(scanf("%s",str)==1){
        if(strlen(str)==4){
            int temp;
            cin>>temp;
            value.push_back(temp);
            pre.push_back(index);
            s.push(index++);
        }else{
            in.push_back(s.top());
            s.pop();
        }
    }
    //通过先序和中序序列求出后序序列
    //先遍历当前树的左右子树，再处理根结点，这样访问结点值的顺序就是中序序列中结点值的顺序
    postorder(0,0,n-1);//从先序序列的左边界（根结点在先序序列的下标），中序序列的左、右边界开始dfs
    //输出
    cout<<value[post[0]]<<"";
    for(int i=1;i<n;i++){
        cout<<" "<<value[post[i]];
    }
    cout<<endl;
}