1086 Tree Traversals Again (25 分)

祖国母亲生日快乐

前中后序遍历的路径是相同的，只是结点输出的顺序不同，这个深度遍历依次走过的节点与先序遍历相同，因此push顺序就是先序遍历顺序，再根据push和pop得到中序序列，就可以创建树。

//
// Created by dgm on 2019/9/30.
//
#include 
#include 
using namespace std;
#define maxn 50
typedef struct node{int data;node*left;node*right;
}*tree;
void createTree(tree &t,int pre[],int in[],int spre,int epre,int sin,int ein){if(spre>epre)return;int pos=sin;for (; pos < ein; ++pos) {if(in[pos]==pre[spre])break;}t=new node();t->data=pre[spre];int length=pos-sin;createTree(t->left,pre,in,spre+1,spre+length,sin,sin+length-1);createTree(t->right,pre,in,spre+length+1,epre,sin+length+1,ein);
}
void postTraverse(tree t,int &index,int n){if(t==NULL)return ;postTraverse(t->left,index,n);postTraverse(t->right,index,n);if(index!=n-1)cout<<t->data<<" ";elsecout<<t->data;index+=1;
}
int main(){int n;int pre[maxn];int cPre=0;int in[maxn];int cIn=0;tree t=NULL;stack<int>temp;cin>>n;for (int i = 0; i < 2*n; ++i) {string oper;int num;cin>>oper;if(oper.compare("Push")==0){cin>>num;temp.push(num);pre[cPre++]=num;}if(oper.compare("Pop")==0){in[cIn++]=temp.top();temp.pop();}}createTree(t,pre,in,0,n-1,0,n-1);int index=0;postTraverse(t,index,n);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！