首页 > 代码库 > GPTL—练习集—006树的遍历
GPTL—练习集—006树的遍历
#include<bits/stdc++.h> using namespace std; typedef int daTp;//datatype typedef struct BTNode *position; typedef position BTree; const int MAXN=30; struct BTNode { daTp data; position lChild,rChild; }; BTree build(daTp in[],daTp post[],int n)//利用中序和后序遍历生成二叉树 { BTree T=NULL; if(n) { T=new BTNode; T->data=http://www.mamicode.com/post[n-1]; int ln=0,rn=0; bool flag=true; daTp lin[MAXN],lpost[MAXN],rin[MAXN],rpost[MAXN]; for(int i=0;i<n;i++) { if(in[i]==T->data) { flag=false; continue; } if(flag) lin[ln++]=in[i]; else rin[rn++]=in[i]; } for(int i=0,k=0;i<n;i++) { if(i<ln) lpost[i]=post[i]; else rpost[k++]=post[i]; } T->lChild=build(lin,lpost,ln); T->rChild=build(rin,rpost,rn); } return T; } void levelOrder(BTree T)//层序遍历 { if(!T) return; queue<BTree>qu; qu.push(T); BTree tr=T; while(!qu.empty()) { tr=qu.front(); qu.pop(); cout<<(tr==T?"":" ")<<tr->data; if(tr->lChild) qu.push(tr->lChild); if(tr->rChild) qu.push(tr->rChild); } } int main() { int n; daTp inOd[MAXN],postOd[MAXN]; while(cin>>n) { for(int i=0;i<n;i++) cin>>postOd[i]; for(int i=0;i<n;i++) cin>>inOd[i]; BTree T=build(inOd,postOd,n); levelOrder(T); cout<<endl; } return 0; }
GPTL—练习集—006树的遍历
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。