PAT A1020
之前總結過相應的東西。。。但是又給忘了,果然還是需要多次重複;
本題主要考慮兩個點:四種遍歷和遍歷序列生成樹;
後序序列+中序序列可以確定出唯一一顆子樹,並且通過觀察我們也可以發現兩序列的判別點:
1.後續序列的其中一顆子樹序列的最後一個節點必定是該子樹的根節點;
2.通過該根節點可以將中序序列分為左右兩個子樹,通過子樹序列再去第一步進行子樹序列的判斷;
之前學習的構建方法都是採用遞迴對陣列索引進行操作;
如下程式碼所示:
node* create(int postl,int postr,int inl,int inr){ if(postl>postr){ return NULL; } node* root=new node; root->data=post[postr]; int k; for(k=inl;k<inr;k++){ //尋找根節點 if(in[k]==post[postr]){ break; } } int numleft=k-inl; root->lchild=create(postl,postl+numleft-1,inl,k-1); root->rchild=create(postl+numleft,postr-1,k+1,inr); return root; }
其中需要注意的是遞迴邊界,能夠到達遞迴邊界的是子樹序列為1的情況,此時,如果對該節點進行構造,左右子樹進入遞迴函式時,必定有postl>postr的情況出現;
並且注意左右子樹遞迴的索引計算,後序序列左子樹右子樹序列的個數是根據中序序列中的左右子樹個數來進行界定的;
層序也很簡單,說到底就是BFS遍歷;
總體程式碼如下所示:
#include<iostream> #include<stdlib.h> #include<stdio.h> #include<queue> using namespace std; const int maxn=50; struct node{ int data; node* lchild; node* rchild; }; int pre[maxn];//先序 int in[maxn];//中序 int post[maxn];//後續 int n; node* create(int postl,int postr,int inl,int inr){ if(postl>postr){ return NULL; } node* root=new node; root->data=post[postr]; int k; for(k=inl;k<inr;k++){ //尋找根節點 if(in[k]==post[postr]){ break; } } int numleft=k-inl; root->lchild=create(postl,postl+numleft-1,inl,k-1); root->rchild=create(postl+numleft,postr-1,k+1,inr); return root; } int num=0; void BFS(node* root){ queue<node*>q; q.push(root); while(!q.empty()){ node* now=q.front(); q.pop(); printf("%d",now->data); num++; if(num<n) printf(" "); if(now->lchild!=NULL) q.push(now->lchild); if(now->rchild!=NULL) q.push(now->rchild); } } int main(){ scanf("%d",&n); for(int i=0;i<n;i++){ scanf("%d",&post[i]); } for(int i=0;i<n;i++){ scanf("%d",∈[i]); } node* root=create(0,n-1,0,n-1); BFS(root); system("pause"); return 0; }