#include<iostream> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #include<queue> #include<string> using namespace std; vector<int>postorder(31); vector<int>inorder(31); vector<vector<int>>levels(31); void buildTree(int postl,int postr,int inl,int inr,int level){ if(postl>postr || inl>inr) return; int root=postorder[postr];//root为根结点，在后序遍历最后一个位置上 int i=0; while(inorder[inl+i] !=root)//在中序遍历序列中查找根结点位置 i++;//跳出while时得到i，左子树结点个数为i levels[level].push_back(root);//把根结点存入对应层的vector中 buildTree(postl, postl+i-1, inl, inl+i-1, level+1);//建立左子树 buildTree(postl+i, postr-1, inl+i+1, inr, level+1);//建立右子树 //后序遍历： 左子树(postl ...postl+i-1) 右子树(post+i ... postr-1) root=postr-1 //中序遍历 ： 左子树(inl...inl+i-1) root=inl+i 右子树(inl+i+1...inr) } void zigzag(){//Z型的层序遍历 cout<<levels[0][0]; bool zigzag=false; for(int i=1;i<levels.size()&& !levels[i].empty();i++){ //注意levels.size()为树的层数 并且判断了当前层的结点数不为空的时候 if(zigzag){ for(int j=levels[i].size()-1;j>=0;j--){ cout<<" "<<levels[i][j]; } } else{ for(int j=0;j<levels[i].size();j++){ cout<<" "<<levels[i][j]; } } zigzag=!zigzag; } } int main(){ int N; while(cin>>N){ for(int i=0;i<N;i++){ cin>>inorder[i];//存入中序遍历序列 } for(int i=0;i<N;i++){ cin>>postorder[i];//存入后序遍历序列 } buildTree(0,N-1,0,N-1,0); zigzag(); } system("pause"); return 0; }
和晴神差不多的版本
#include<iostream> #include<stdio.h> #include<stdlib.h> #include<math.h> #include<string.h> #include<algorithm> #include<map> #include<vector> #include<queue> using namespace std; int n; int in[40],post[40]; struct node{ int data; int level; node* left; node* right; node():left(NULL),right(NULL){} }; node* create(int inL,int inR,int postL,int postR){ if(inL>inR) return NULL; node* root=new node; //新建一个新的结点，用来存放当前二叉树的根结点 root->data=post[postR]; //新结点的数据域为根结点的值 int k; for(k=inL;k<=inR;k++){ if(in[k]==post[postR]){//在中序序列中找到in[k]==post[postR]的结点 break; } } int num_Left=k-inL;//左子树的结点个数 //返回左子树的根结点地址，赋值给root的左指针 root->left=create(inL,k-1,postL,postL+num_Left-1); root->right=create(k+1,inR,postL+num_Left,postR-1); //返回右子树的根结点地址，赋值给root的右指针 return root; } int max_level=0; vector<int> ve[40]; void BFS(node* root){ queue<node*>q; root->level=1;//一开始漏了这句，导致跳出读取位置 xxx时发生访问冲突 的报错 q.push(root); while(!q.empty()){ node* now=q.front(); q.pop(); ve[now->level].push_back(now->data); if(now->level>max_level) max_level=now->level; if(now->left!=NULL){ now->left->level=now->level+1; q.push(now->left); } if(now->right!=NULL){ now->right->level=now->level+1; q.push(now->right); } } } int main(){ int i,j,total=0; scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&in[i]); } for(int i=0;i<n;i++){ scanf("%d",&post[i]); } node* root=create(0,n-1,0,n-1); BFS(root); for(int i=1;i<=max_level;i++){ if(i==1||i%2==0){ for(int j=0;j<ve[i].size();j++){ printf("%d",ve[i][j]); total++; if(total<n) printf(" "); } }else{ for(int j=ve[i].size()-1;j>=0;j--){ printf("%d",ve[i][j]); total++; if(total<n) printf(" "); } } } system("pause"); return 0; }
