給中序前序求后序遍歷

根據前序和中序求后序遍歷序列 根據前序和中序的特性分析 1 首先從前序序列確定當前子樹的根節點 2 然后可以根據根節點到中序序列中找到左右子樹的個數 分析左右子樹 3 如果左右子樹數量大于零 相當于我們分別知道了左右子樹在前序和中序的子序列 4 通過確立根節點的過程 我們依次確立根的左孩子左子樹 以及右孩子 右子樹 遞歸求解 回到1 根據以上步驟 可以逐步以深搜遞歸樹的方式 把整顆樹創建出來 然后再后序打印即可 #include <bits/stdc++.h> using namespace std; typedef struct node{char v;node* l,*r; }*T; /*前序遍歷: GDAFEMHZ中序遍歷: ADEFGHMZ后序序列: AEFDHZMG */ char pre[20],in[20];T ana(int s1,int e1,int s2,int e2){T p;p = (node*)malloc(sizeof(node));p->l = p->r = NULL;p->v = pre[s1];char f = pre[s1];int rt;for(rt=s2;rt<=e2;rt++)if(in[rt]==f)break;//注意這里找的是中序序列分割左右子樹 int l = rt-s2,r = e2-rt;//注意找到后用rt計算左右子樹的元素數量 if(l>0)p->l = ana(s1+1,s1+l,s2,rt-1);if(r>0)p->r = ana(s1+l+1,e1,rt+1,e2);return p; } void postOrder(T rt){if(rt){postOrder(rt->l);postOrder(rt->r);printf("%c",rt->v);} } int main() {gets(pre);gets(in);T rt;rt = ana(0,strlen(pre)-1,0,strlen(in)-1);postOrder(rt);return 0; }

給后序中序求前序序列

還是相似的步驟 這次就是后序的最后一個結點為根節點
然后還是依靠中序序列劃分左右子樹 然后遞歸分治求解

#include<bits/stdc++.h> using namespace std; typedef struct node{char v;node *l,*r; }*T; char in[20],post[20]; /*前序遍歷: GDAFEMHZ中序遍歷: ADEFGHMZ后序序列: AEFDHZMG */T ana(int p1,int p2,int i1,int i2){T p = (node*)malloc(sizeof(node));p->l=p->r = NULL;p->v = post[p2];int rt;char f = post[p2];for(rt = i1;rt<=i2;rt++)if(in[rt]==f)break;//注意這里找的是中序序列分割左右子樹 int l = rt-i1,r = i2-rt; if(l>0)p->l = ana(p1,p1+l-1,i1,rt-1);if(r>0)p->r = ana(p2-r,p2-1,rt+1,i2);return p; } void preOrder(T rt){if(rt){printf("%c",rt->v);preOrder(rt->l);preOrder(rt->r); } } int main() {gets(in);gets(post);T rt;rt = ana(0,strlen(in)-1,0,strlen(in)-1);preOrder(rt);return 0; }

給前序后序求中序序列

我們發現 由于沒有中序序列 前序我們可以知道根節點 后序也可以知道根節點
而左右子樹的界限無法劃分 存在不唯一解

總結

以上是生活随笔為你收集整理的三序遍历相互求法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。